ICPC2018国内予選参加記

チーム紹介

 ICPC2018国内予選に、CatKOderというチームの一員として参加しました。メンバーは次の通りです。

 CatKOderのt担当、tokumini(@kaitei_shogi)です。基本的には将棋ソフトの開発をメインでやっており、競技プログラミングは毎週AtCoderのコンテストにだけ出ています。

 AtCoderのレートはチームの中では僕が一番高くて1556。一度偶然にも青コーダーになったことはありますが、実力は1500中盤くらいだと思っています。

f:id:tokumini:20180707082411p:plain

 あと二人は僕の少し下くらいですかね?(よく知らない) そこまで大きな差はなく、バランスの取れたチームという感じです。

結果

 4完1WAで52位でした。

f:id:tokumini:20180706233252p:plain

 大した順位ではありませんが、学内ではトップということで予選抜けらしいです。嬉しい。

当日まで

 そもそも僕はほぼAtCoderしかやってない人間で、ICPCは存在を認識している程度でした。後にチームを組むことになるalbicilla氏に声をかけられたのが2か月くらい前のことで、そこから学内で行われている競技プログラミングの練習会等に参加しICPC対策を始めました。ICPCの問題はAtCoderとは毛色が違う印象があり、2か月という付け焼き刃的なものでしたが効果は大きかったと思います。

本番

 方針としては二人がA,Bを解いて、僕はCと残りからどれか簡単そうなの一つを解くという完全分業制。考察/実装という分け方をしているチームもあるみたいだけど、日頃やってた練習会でうまく考えを伝えられないことがあったのでこういう感じに。

 開始してすぐに僕はC問題へ。20分くらいで解法に気づく。Aはもう通してくれてて、Bも通してくれるのを待とうと思っていたけど、どうも手こずっているようだったので機を見て先にCを書かせてもらった。最初に考えていた式が間違っていて一瞬焦ったけどすぐ修正できてAC。Bは読んでないのでよくわからないけど、Cよりも実装が重い感じだったらしいのでもっと早めに書きにいっても良かったかもしれない。

 D以降をサラッと眺めて第一感で解きやすそうなのはDかEかなという印象で、ちょくちょく順位表をチラ見してもDを解いているところが多かったので本格的にDを考え始める。

  2^{81}は通らないよなーということで、何かしら状態を上手く持つタイプの問題だと思った。しかしさっぱり思いつかずしばらく時間が経つ。チームメンバーもB問題に結構手間取っていて、ここら辺はちょっと暗雲が立ち込めているという感じだった。

 しばらくして状態を減らせばなんかメモ化再帰っぽいことがやれそうと思いついた。後から振り返ると意味不明なんだけど、この時はそれで通ると勘違いしたのでメンバーがBを通してからDを書き始める。

 しかしどうもサンプルの最後の3つあたり、数が大きくなると答えが合わず、うんうん唸っているうちに残り40分くらいになる。同じ状態に2回以上訪問しない全探索なのでメモ化しているのが無駄で、途中でなんとなく入れた枝刈りが本質だったみたい。しかし解いているときはそんなことには気づかない。

 もうD以外に行く時間はないと思ったので他の問題を考えていたチームメンバーにもDへの救援を要求し、サンプルを作ってもらったりコードを読んでもらったりした中で、メモ化がバグってそうなんだよねーとメモを調べて返す部分をコメントアウトすると上手くいくことに気づく。ここで残り15分くらい。しかしこれでは時間がかかって間に合わない……とか思いながらプログラムを放置していたらなんかそれなりな時間で計算が終わっていた。「じゃあそれで出してみりゃいいんじゃね?」というチームメンバーの一声でとりあえずデータ落として回したらそこそこの時間で計算が終わる。1個目のデータが無事通ったので2番目のデータも同様に数分待ってAC。メモ化に思考が囚われていたので愚直な全探索っていうのは完全に自分では思いつかなかった。チームに救われたACだった。

 改めて順位表を見るとDを通したのが2:51:10でかなりぎりぎり。本当に危なかった。

反省

 始める前は基本的に4完早解きを目指していて、あわよくば5完を、という感じだった。本番だとDを解けるかどうかすら怪しかったわけで目標は目標にすぎなかった。

 しかしDで詰まっていたところで、いいタイミングでチームメンバーに助言を求めることができたのは良かったと思う。一人でやっていたら確実にハマっていた。チーム戦の良さを存分に活かすことができた。

 個人としてはやはりD問題で苦しんでしまったのが反省点。意味のないメモ化をしていたり、計算量を全く把握できていなかったり、冷静さが足りなかった。自分がどういうコードを書いているのかはっきりとわかっていないまま書いていた感じもあって、通せたのは本当に運が良かっただけだった。

 次の機会も貰えそうだということで、また頑張ります。