Code Jam to I/O for Women 2021　に出場しました。

Code Jam to I/O for Women 2021で優勝しました。

あまりコンテストの参加記は書いたことがなかったのですが、優勝は気持ちいいので忘れないように記録しておきます(あくまでも記録用なので、見せる用ではないです)。

過去問や順位表を確認し、戦略を立てていました。

Dのmediumまで早解きするか、満点を取るかで優勝できることがわかりました。

Dは「AtCoderの黄～橙前半diffくらいの実装重め」という雰囲気だったので、「largeを狙いつつ明らかに辛そうだったらmediumを取りに行く」という気持ちで臨みました。

優勝したかったので、出ることはTwitterで黙っていました(ごめんなさい)。

問題文の速読は練習していたので、落ち着いて題意を理解することができました。

座圧が頭をよぎりましたが、mapを思い出したのでよかったです。出力形式の準備を忘れていたのでそこに手間取り5分近くかかってしましました。(4:44 0WA)

AGCで以前類題がありました(A - ><)。

AGCの問題では入力のランレングス圧縮が要求されるので実装が厄介ですが、今回はランレングス圧縮された状態で入力が与えられるので、前から見るだけで実装することができました。(11:44 0WA)

C以降は「見た瞬間解き方がわかる問題」ではないという認識でしたが、実際この問題もそれなりに考察が必要でした。

サンプル2を手で試すと、1度のsessionで頂点間の距離が1短くなることがわかったので、最短路問題に帰着できることがわかりました。(実際は、Managerの頂点のみが使える最短路問題)

実装ではbfsなども検討しましたが、事前にManager間でワーシャルフロイドを回しておき、あとはクエリごとに端点とつながるManagerを全探索しました。(38:33 1WA)

Cが解き終わった時点で順位表を見たのですが、もうDのvisible(small,med)を通している人がいてかなり焦りました。

ゲームの必勝法の問題だったのですが、奇抜な発想は必要ではない気がしたのでlargeを解きに行くことにしました。

medium解のDPが線形に落ちないことはそれはそうという感じだったので、必勝法をまじめに分析しました。とれる戦略がそんなに多くなかったので、細かく場合分けをして必勝法のようなものに至りました。

実装ですが、かなり筋が悪く手間取ってしまいました(必要のないdequeを使ったり、先手後手で2倍場合分けしたり)。(1:38:12 1WA)

順位表を見たら45位あたりで「終わった…」となっていました。

ただ、D largeが隠されておりmediumとの難易度に崖があったので、ちゃんと通れば1桁順位に入れるだろうと思っていました。

D largeは自信ありでしたが、C largeはsmallで通っていても普通に落ちる可能性のある解法だったので、「愚直書いてチェックしようかな、面倒だな」とずっとぐだぐだしていました。

最終的に終了5分前くらいに愚直を書いて、軽めにチェックをしていました(ここで間違いに気が付いても今更なのですが…)。

あとは歯を磨いたり、順位表を観戦したりしていました。(はますさん強いな―ももはらさんたぶんDlarge解いてるなーなど)

コンテスト時間が終了し、順位表を更新したら「1」がでてきて爆笑しました。

うしし

優勝できたので良かったですが、2位の人との差が10秒だったのでかなり危なかったです。Dの実装をもうちょっと効率的に進められれば、20分くらいは詰められたなと思います(ペナを出してからACするのに15分くらいかかっていました)。

強くなるまでの道は長いですが、がんばりたいです。