hogecoder

tsutaj 競技プログラミングの記録

CODE THANKS FESTIVAL 2017 参加記

大会参加記

CODE THANKS FESTIVAL 2017 に参加しました。今回が初参加です。

予選

予選の順位は

予選 順位
qual A 308th
qual B 454th
qual C 757th

予選 A は C 問題までそこそこ早解きできたけど、予選 B と C は D 問題が解けそうで解けなくて結構下の順位になってしまい悲しいね。

おそらく予選 A で THANKS ボーダーに引っかかって参加権を獲得しました。正直行けると思っていなかったので、参加のご案内メールが来たときはびっくりしました。

大会前日

空港に向かう前に、ちょっとヨドバシへ。ボドゲ会が予定されているのにボドゲをなにも持ってなくてアだったので、調達しに行きました。

東京に到着後、 らてあさん・TIke さん・こうきさん・竹雄さん・フェリンさん とボドゲをやるべく、カラオケ屋へ。

自分が持ってきたゲームと、フェリンさんが持ってきたゲーム (インサイダー・ゲーム) でワイワイやってました。ボドゲは久しぶりにやったけど、思考の読み合いがホントに面白かったな〜

その後ふーらくたるさんとも合流し、ご飯へ。ハンバーグおいしい！

ホテルに戻ってしばらくして、ボドゲ会第二弾！竹雄さん・ Treeone さん・らてあさん・こうきさん・やざてんさん とゲームをしました。やったのはギャンブラー・ギャンブルとクーだったはず。ゲーム中に Treeone さんが通知を破壊したり、らてあさんが雑リプを飛ばしたりしていて実質 TL で面白かったです。

大会当日

コンテスト開始前

竹雄さんと会場に向かう。ゆりかもめが今まで見たことない混み方しててヤバを感じた。混みすぎてて最初に来た電車を見送って、次に来たやつに乗ったりしてました。

そんなこんなで無事会場入り。交通費精算何度も WA してすいませんでした。T シャツをゲットしてテンションがめちゃくちゃ上がりました。

なんか誰もマスコット類出してないなあと思いつつ、せっかく持ってきたので †開封の儀† を行い設置。

このマスコットが本当に目印になったかどうかは、よくわかりません・・・

コンテスト

目標はパーカー獲得！がんばるぞいという気持ち。

最初に見たのは A 問題。FA 取るで！と思って流し読みして書いてコンパイルせず提出。

続いて B 問題へ。頭が死んでいたので解法が分からなかった (は？) とりあえず放置したら解けるようになるだろうと思って C 問題へ。

C の解法はすぐ生えた。その時刻で最も小さいものを取り続ける貪欲をすればよいため、 priority_queue で常勝。無事 AC (09:12)

A 問題が通っているかどうか確認したら WA でビビる。どうやら N 個の問題があるわけではなく、問題数は 8 で固定らしい。ちゃんと問題を見ようね。そんなこんなで AC (10:01)

D 問題でちょっと詰まる。最初変な方針を書いたら WA した。いろいろ紙で実験したら GCD を取れば良さそうなことに気づいたのでそれを書いて AC (47:02)

E 問題と F 問題両方見て、 F の方がすぐ書けそうだったのでとりかかる。和の制約があるため状態数は多くないのかなあと思って自明な bit DP を書いたら TLE、それはそう。

ここでちょっと考える。どうやら、この方法だと 1, 1, 1, ..., 1, 90000 みたいな、 1 がたくさんあって 1 個だけでかい数が出た時に全く節約できないことがわかる。これを節約するにはどうすればよいかを考えた結果、 bit を調べる範囲は 2^(今まで登場した数字の MSB 最大値) までで十分であるため、入力をソートして範囲を絞って bit DP をすれば良いことに気づく。これにはかなり早い段階で気づいていたんだけどなかなか通らない (Submission #1822207、開始 1 時間少しで想定解にはたどり着いているがある部分の実装が不適切であるため TLE)。つらい。つらいので一旦放置。

そういえば B を放置していたことを思い出す。これ書くだけやんけ！回文になる suffix の長さの最大値を全体の長さから引くだけ。 AC (104:49)。 F 問題であれこれやってたのもあって、D 問題の AC から 1 時間近く開いててつらい。

F がまだ通らないので E を考える。本物は奇数で偽物は偶数だから、偶奇でどうにかするのかなあと考えたけど、なかなかうまくいかない。コインが 5 種類しかないから取るコインの枚数を工夫して解くのかなあとも考えたけど (よく考えたらこれが想定解だったのね)、どんなふうに取っていけばいいのかわからなかった。

ついに F の実装のヤバイ点を見つける。 DP で配列を使いまわす時に、その配列を毎回 memset で 0 埋めしていた部分が重かったらしい。なんだそりゃ・・・。結局 vector を resize して swap して・・・みたいな意味不明な実装をして AC (134:28)。今思えば memset ではなく必要な範囲だけ for 文で初期化するとか、 map で DP するとかすればよかったですね。これのせいで 1 時間溶けているので悲しいなあ・・・。

E は頭の悪い自分には無理そうだったので G を書いてみる。自明な全探索を適当に刈る方向性で書いたけど TLE。今思えば辺が少ない時に枝刈りできていないので全然ダメでした。

結果は ABCDF の 5 完 62 位でした。F の実装でハマったのといい、 EGH が解けなかったのといい、完全に実力不足でした。来年はパーカー取れるように頑張ります。

ふーらくたるプロが 5 位になったので前で感想を語っていたのですが、あまりに感動的な内容で頭が真っ白になり、もう内容は覚えていません。

ちょくだいさんが解説をしてくれました。オンサイトコンテストで解説を聞いたのは今回が初めてでした。絶対解き直すぞー・・・

懇親会

CONNECTION HUNT が結構面白かった。いろんな人と話しましたねー。特に、念願の tourist じゃんけんをすることができて胸熱でした。

懇親会のご飯はどれもおいしくてリクルート最高という感じでした。懇親会も実質 TL だったので楽しかったです。

大会後

大会後に、もう少し遊びたい人 (TIke さん・Shinya Kato さん・Noimin さん・minaminao さん・こうきさん・A さん (Twitter やっていないようなので仮名で書かせていただきます)) で集まってボウリングをしに行ったりしてました。その後カラオケの流れもあったけど、こどふぉがあるのでホテルに戻りました。

ホテルで自宅番兵さんとこどふぉオンサイトをやりました！ やっぱりコンテスト後にあれこれ議論できるのはいいですね〜。

まとめ

ありがとう THANKS FESTIVAL！来年は本選にいきたいなあ・・・！