昨日、ACM-ICPC 国際大学対抗プログラミングコンテストの国内予選 が行われました。自分が所属する北海道大学からは 4 チームが参加し、3 チームが 4 完・1 チームが 3 完しました。このうち 2 チームはアジア地区に行けそうで、弊学サークル全体のレベルの高まりを感じています。
チーム情報
今年も four-t として参加しました。メンバーは構文解析のプロ・ rsk0315 ( @rsk0315_h4x ) と幾何のプロ・ TAB ( @_____TAB_____ ) と数え上げが解けたり解けなかったりする趣味・自分 (tsutaj) の 3 人で、結成 2 年目です*1 。お茶汲み要員にならないようにがんばりました。
本番前
去年 Practice 1 位だったし*2 、今年も目指すか！例の数字をライブラリとして印刷して Practice も常勝！！！
・・・と思っていたけど、開いてみたら最後の問題が 500 円玉貯金 (2015 年国内予選 D) で草。まあこういう系統はかなり解いてきたし自分の担当分野でもあるので肩慣らしに解く。なんやかんやで今年も Practice 1 位になれました。
その後順位表のリセットが 2 回くらいあったけどその都度即座に提出して 1 位を防衛した (謎) (結果的にサブミットの練習になりまくった)
本番
本番の序盤の戦略は、TAB 君・えび君が A を読みつつ印刷クエリを投げ、自分は印刷されたものを眺めながら解けそうな人に問題を投げるという感じ。紙を届ける頃には A が終わっていたので (4:54)、実装ゲーっぽい B をえび君に、ちょっとした数学っぽい C を TAB 君に、そして自分は数え上げっぽい D をやることに。
D は見た目がアレなので (？) C を TAB 君と一緒に考えてみると、少し数学をして探索範囲を小さくすればよいことに気づく (割とすぐに気づいた)。 TAB 君と自分とで相談してみて方針が良さそうだったので TAB 君に実装してもらう。すぐ通してもらった (21:10) (ありがとう)
F は幾何で G が構文解析っぽいので、ここらへんで F を TAB 君に・G をえび君に投げて、解くべきかどうか判定してもらうことに。G はなんか無理そうで F は頑張れば行けそうな感じだったので、F を TAB 君に考えてもらう。
B はなんかつらそうにしていたので先に D を詰める。よく見るとサンプルの最後のケースが最悪ケースだが場合の数が少ないし、そもそも全チームの勝敗数が同じなら全チーム 勝
敗しているはずなので、枝刈り全探索で良さそうなことに気づく。
ここで F を考えていた TAB 君が解法を思いついたらしいので、D と F を並行して実装していく。やがて D が書き終わったので実行するも、やはりサンプルの最後の実行にはそれなりに時間がかかる。「D は書けたけどテストケースの実行にそれなりに時間かかりそうだし、F の実装してる間に並行して D を実行させるか〜」とか言ってたんだけど、最適化オプションつけたら爆速で終わって草。並行してやる必要ないやんけ！そんなこんなで D を通す (53:12)
B は書けたらしいが提出すると WA が返ってきたので、えび君がソースコードを印刷してバグを探す段階に入っていた。また F は途中まで書けたがその後の実装方針を詰めなければならないらしい。自分は他の問題を眺めるもすぐ解けそうなものはない。ここで取れる戦略としては色々あったと思うけど、自分は順位表と残りの問題の感触からまず B を優先すべきと判断し、F を引き続き TAB 君に考察してもらいながら、自分とえび君で B のソースコードを読むことに。
B のソースコードの問題点はしばらくしたら見つかった。PC を使っていた TAB 君に交代してもらって B を直して提出するもまたもや WA が返ってくる。操作中の配列を visualize しても挙動は間違ってなさそうなので、悶々とするなどした。
こういうときは「実装方針を変えれば良い」ということを去年のアジア地区で身をもって知っていた*3 ため、B の楽な実装方針を考えてみる。すると今まで考えていた場合分けが不要な実装方針を思いついたので、それを自分が書くことにした。
問題文を読みながら、入力を受け取ってここはこう処理して〜と書いてるうちに、実は誤読しているのでは？ということにここでようやく気づく。どうやら縦に折るときは紙の下から何番目の線で折るかが指定されるらしい (今までの実装は上から何番目かで考えていた)。ということでそこを直して提出すると、やっと通る！！！ (2:13:31, 2 penalties)
次にどの問題を優先すべきかを考えてみる。順位表を見ると F が全然解かれていないし、F の解法を説明されても完全な理解ができない (申し訳ない・・・) ので、E をやることに。この判断は大反省です (後述)
E は残り 15 分でそれっぽいものは思いついたので書くも、そこで時間切れ。よくよく考えたら桁落ちを考えていない解法だったためどちらにしろダメでした。
B で割と詰まったけど、ACD の早解きが効いて 39 位で終了。今年もアジア地区に行けそうで嬉しいです。
反省
序盤の立ち回りはアレが正解だったと思う。事実、開始 1 時間時点では 1 桁順位だったらしい (あんまり見てないけど)
問題はその後で、まず B を助けに行くのはおそらく間違っていなかったと思う。ただし助け方にもいろいろあって、今回は既にあるものを直すか新しく書きなおすかがあったと思うけど、結果論にはなるが新しく書きなおしたほうがもしかしたらよかったのかもしれない。新しく書きなおそうとしてみて思ったけど、複数人が「問題文を読む」だけでなく「実際に実装する」と、読むだけでは気づかなかった欠陥を発見できるので、詰まったらとりあえず別の人が書いてみるというのは有効だと思う (ただし 1 から書きなおすほうがタイムロスが大きい場合も当然あるので、既にあるものを直してどうにかなるならそれに越したことはない)。
B を助けるタイミングおよびその速度は、いろいろ改善の余地があるけどあれは仕方ないと思う。自分は他の人のソースコードを見るのがそれほど苦に感じないし、どちらかというとバグ直しが得意な方ではあるけど、あれよりも速くバグ直しができるようになるのかはよくわからない。
チームの指令塔的役割として最大のミスはやはり 4 完後の立ち回りだったと思う。F は解法がある程度見えているにも関わらず、順位表の感触から E に行ってしまって申し訳ない気持ち・・・。これは完全に自分のミスです。F をもう少し詰めていればもう 1 問解けていたのかもしれないです。結果的に F がうまくいってもいかなくても反省すべき。
さいごに
やっぱりチーム戦は奥が深くて楽しいですね。ずっとやっていたいけど今年と来年しかできないの悲しいなあ・・・ (早生まれだし来年があるだけでも幸運なんだけどね)
もっと強くなって横浜でも存分に戦いたいです！！！
*1:去年の様子はこちら → ICPC 国内予選 2017 参加記 - hogecoder
*2:例の数字を暗記していたため
*3:当時のガチ反省記 → ACM-ICPC 2017 Asia Tsukuba Regional Contest 反省記 (コンテスト部分のみ) - hogecoder
