ei1333の日記

ぺこい

天下一プログラマーコンテスト2016本戦

予選Bで15位をとって本戦に出場できたのでしてきた。
最下位かな?

本戦

そもそも方向が分からないので会場に到達するまでに  {N} 回迷った。都会の人は凄いなぁ。 T シャツは 10||1。てん(10) か(OR) いち(1) なのね。天才。

C

一回 RollingHash 書いていたけど log がかかって大変そうかなぁって思ってた。

そしたら途中で Trie 木で明快じゃんって気づいたので昔書いたやつをコピペしてくる。

これだけでいいはずなんだけど, サンプルが合わないのでDPがバグってるのかなって思って 無限時間消費する。でもどうもおかしいと思ったら Trie木がバグっていた。ここまで55分。 これくらいの Trie 木なら普通に書いたほうがはやいね。

B

次に B をやろうかなぁという気持ちになる。

ここで普通に DFS 書けばいいのに bitDP を書く(ダメ 頂点数が 10 より大きくなるととけないので, やっぱりダメ

D

その次に D。苦手そうだけど, 流石に 3 完みたいな成績で終わってはいけないとおもった。

あまりに分からないので迷走しながら全探索っぽいものを書いていると, そのうちオーダーが重そうな  {O(2^N N^2)} の bitDP が現れるのでそれに書き換えて提出。 どうみても重いのでジャッジに時間がかかっていて諦めていたけど, 4847 ms / 5000 ms で通る。

 {N} を一個外せるのかなぁとか思ってた。 残り 25 分。緊張しているとはいえ、もうちょっと早く解けてもいいよね。

E

問題は読んであったけど, 流石に残り 25 分で解けるようなアレではないのではなかった。

A

A が 「1 0 1 1」 しか提出していなことに気づいたので適当に 1000 頂点くらい + ちょっと辺を張ったやつを出す。

Text 提出しか出来なかったので, 出力が流れてしまってコピペできなくて焦る。

頑張ってファイル出力して 2 分前くらいに提出。

結果

4 完しただけね。

E は頑張れば解けそう。 F は僕が生きている間には解けなさそう。

来年また奇跡的に本戦に行けたりするのかなぁ

懇親会

ピザ 5 個。