KUPC 2015
KUPCに個人で参加してきました．
結果は48位でした．
以下，コンテストの詳細
銀座に向かう．
ATNDのトラップを回避して会場に着く．
開始が20分遅れたので，自己紹介タイムが設けられる．
0:00 Start!
A問題に取り組む．
貪欲すれば良さそう．
書くけど，1WA
テンプレートが悪さをしていた．
修正して提出する．
0:06 A AC
B問題が面倒くさそうだからC問題を見る．
与えられたグラフに対して，WFしてから元のグラフと一致しているかどうかを見る．
0:13 C AC
B問題に取り掛かる．
頭を働かても，答えが思いつかないで全探索する．
テーブルのマス数N=100に対して，計算量O(N^5)だから答え出るのだろうかとプログラム動かす．
すぐに解答がでてくる．textで提出
1:18 B AC
D問題に取り掛かる．
ある地点に移動した時の最大金額を求めるようなコードを書く．
最後のサンプルが通らなくて，しばらく放置する．
変数ミスだった．修正して提出
2:30 D AC
E問題に取り掛かる．
正方形に内接する正三角形とか調べる．
長方形の長い方の辺の2点と向かいの中点の三角形が最大になるとか気づく
サンプルは通る．でも，WA
H問題に切り替える．
X=Nの時が答えの上限になるから-1にはならない．
LSBの方から貪欲に見るコードを書く．
WA
シミュレーション解と合わせて調べてみて，無理そうと放置
F問題に取り掛かる．
スタックとキューの違いをどうするかが思いつかない．
そこで，構文木を書いてみる．
スタックとキューからDFSとBFSの関係を考えてみる．
構文木の深い方から，同じ深さのものを計算していく．
また，右・左の順にQueueにPushする．
構文木の生成をスタックで書く．
サンプル通る．提出する．
4:04 D AC
E問題に再び取り掛かる．
三角形をパラメータで決められると考える?
凸関数の最大値を求める問題になりそう? (たぶん，嘘まじっている)
長方形に内接する三角形の1辺の最小値を返す関数fを作る．
関数fに対して，三分探索する．
サンプル通る．良さそうと思い，提出する．WA多発する．
バグ修正する．提出する．
4:41 E AC
G問題に取り掛かる．
各人がBi以下の人にマッチングして良いというインデックスiを求める?
この配列に対して，バブルソートの交換回数を求める．
サンプル通る. WA
5:00 Finish!
G問題の解法はうまくマッチングだったみたい...
去年に比べると解いた問題数が3問から6問に増えて，驚いた．
G,H,I問題まで復習かな...
F問題はDFSとBFSの概念を比較して，解くという問題で楽しかった．
最後に，KUPCのスタッフの方々お疲れ様でした．
(あと，ケータリング・お菓子美味しかった．)
