JAG の模擬国内予選 に参加しました。チーム結成 3 年目にしてようやく、初の全員揃っての参戦でした。
模擬予選の様子
自分は A の担当になっているので開始直後から読む。いけそう。一応オーバーフローとか入出力ミスとかそのへんに気をつけながら実装して AC。
B は rsk0315 君が、C は TAB 君が担当していた。C をチラ見していたけど自分がたくさん助けられそうな問題ではなさそうなのと、TAB 君なら解けそうなのとあって、一旦任せて D を読む。
D は編集距離とかなり似ている、というか Rotate がなければそのまんま。頑張れば解けそうなのでしばらく考える。しばらくすると B が AC されていたので rsk0315 君と解法を相談してみたところ、最初に考えたことが完全に嘘なことがわかる (これ早めに気づけたの結構良かった。危ない) Rotate は区間を任意にもってきてやるわけじゃなくて先頭から末尾へしかできません！
そんなこんなで色々考えたところ、最初考えていたものよりも楽そうなことが分かる。とりあえず気持ちを実装するもサンプルが微妙に合わない。ここでやっと、削除は Rotate 前にやって追加は Rotate 後にやるとお得なことがわかって、編集距離の遷移時のコストを変えないといけないなぁとなる。
rsk0315 君と TAB 君が相談してたら C の解法が生えたらしいので、バグっている D のソースコードを共有してもらいながら C を書いてもらう。rsk0315 君が実装している間に TAB 君に D の実装を説明しながらバグを探してみる。
説明してたらコストをミスってるのがすぐわかって、直すとサンプルが合う。出したら通る。やったね。
まだコンテスト時間が半分近く残っていたのでもう一問解きたいとなる。E を見たけど見た感じ不可能にしか見えないし一旦飛ばす。F は構文解析 (つらいらしい) で、G は幾何で、H は数え上げらしい。
H を考えてみた。三乗が許されるのであれば DP と重複組み合わせで行けるが、当然不可能なのでなんとか削減できないかずっと考えてた (でもわからなかった)
rsk0315 君と TAB 君で G を詰めていて、書けそうらしいので書いてもらう。ちょいちょい直していくとサンプルは合うも、出すと Wrong Answer になった。検出すべきものができていなさそうな挙動をしていたのでバグとかアルゴリズムの間違いとか色々考えたけどここで時間切れになった。
反省
前半に関しては担当の割り振りはあれが最適だとは思うし、チームメイトのおかげで D の考察や実装で過度に時間を消費しなくてよかった。
問題はその後で、まず E を TAB 君と相談した記憶がなく、相談する前に捨てモードにいったのが本当にもったいない。ちゃんと相談すべき。しかも模擬予選前日にこれを解くために必要なライブラリをわざわざ整備していたので割とショックだった (本番のときは本当に何もわからなかったのでしょうがないんですが・・・)
あと自分が G の問題文を読むのが遅すぎて G のデバッグのときに題意があやふやで申し訳なかった。手が止まってしまっているときにちゃんと読むべき。
さいごに
何かと反省は多いですが、本番もがんばりたいですね。いい結果にしたいです。
