3/13(水)12:30~17:30でやった
27+30+15=72pt
日程内5位
参加者のレベルと難易度が高い年だし妥当な結果っぽい
本番のフロー
0:00-0pt
問題1(誘拐2)を見る
2ファクタのグラフを圧縮するタイプの問題
問題を理解するのに時間がかかり、その上考察上の飛躍をして解釈してしまった
23点の部分点を取るつもりだったが、正しく実装すると満点が取れる解法を思いついてしまっていて、当然実装が重いので飛ばすことにする
1:25-0pt(+0)
問題2(都市)を見る
木の順序関係を数値から復元する問題
セグ木の気持ちになると区間の内包外包関係で表すと良さそうなことがわかるので、それを実装する
1:55-22pt(+22)
桁数を一桁だけ減らすと8点がもらえるらしいので、もらう
まともな考察をせずに雰囲気でやったので、時間をロスする
2:15-30pt(+8)
問題3(ドラゴン2)を見る
部分点1の15点を取る
オーバーフロー対策のベクトルの式変形に時間がかかる
3:00-45pt(+15)
問題1(誘拐2)を考える
頭を冷やしてもう一度問題を見ると、自分が飛躍をしていたことがわかる
飛躍を解くと実装が楽な問題になり、それを実装する
3:55-72pt(+27)
問題1(誘拐2)を考える
この問題は最初に考えていた解法で通るが、計算量解析が非自明なタイプの問題で、通ることに気づかなかった
貪欲などを考えていたら人生が終了した
反省
・良い問題の表現だったとしても実装が楽とは限らない。部分点を取るためには言葉の通りの表現が使いやすいことがある。
・限定表現があったらそれを使ってより良い上界があることを疑う