早稲田大学プログラミングコンテスト2019にチーム参加した

早稲田大学プログラミングコンテスト2019 - AtCoder に参加しました。

開催2日前

レート2000未満なら3人までチームが組めると書いてあった & RUPC参加者のTwitterを見ててチーム戦楽しそうだなぁと思ったので、競プロやってる大学の頃の音ゲーの友人(@UminchuR、以下うみんちゅ)と、競プロやってる高校の同級生(@tatt61880、以下tatt)に声をかけたらあっさりチームを組めてしまった。青3人でも赤には勝てないだろうけど、そこそこいけるのではないかと考えていた。

開催前日

チーム名が決まる。全員32歳なので、team_0x20となる。

当日、開始前

Wi-Fiがあって何時間でも無料で使えるコワーキングスペースとして知られるLODGEに集合するも、席を確保するのに苦労する。チーム用のアカウントを作る。レート順にAをtatt、Bを自分、Cをうみんちゅが担当することにする。

コンテスト中

Bを考察している間にAをtattがAC(8:40)

Bの考察ができたのでBを実装し始める。その間にCの考察が終わる。Bを実装し終わる直前にH=1, W=1のコーナーケースに気づいて考え直し、その間にCの実装をうみんちゅに任せる。Bの考察が今度こそ終わったのでうみんちゅに実装を止めてもらってAC(25:17)

D, E, F, Gあたりを眺めてる間にCをうみんちゅがAC(35:40)。なんとこの時点で3位。凄い。

HはFFTか？ わからん。Dも問題が難しい。Fを検討していたら木DPで解けるんじゃないかと思ったが結局フローだった。FはフローのF。フローは以前に1回解いたのにDinicをライブラリ化してなくて詰んだ。気づいたらGをうみんちゅが通していた(82:11, 1WA)。

Eでtattとうみんちゅから回文という話が出てきて、自分も読んだところ確かに回文だったので、最近こどふぉでこういうのはZ-Algorithmで解けたよなぁと思いながらいろいろググってたら

文字列の頭良い感じの線形アルゴリズムたち２ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

が見つかったので、Manacherを貼ってAC(110:44)。偶数長の回文検出も必要なことに後から気づいてダミーを入れたりするのに手こずってる間にうみんちゅがFとDの考察を終える。

そしてFがAC(127:56)される。DではRange Maximum Queryのライブラリが必要だけど持ってない、って言われたので自分のRange Minimum Query のリンクを教えてあげたらハマりながらも改造してACしていた(161:41)。この時点だとまだ1ページ目(20位以内)にいて、このまま1ページ目に残れたらいいなぁ、とか言っていた。

この頃から自分はIを検討していて、セグ木にCHTを貼る的な何か、って思っていたがよくわからず終了して、結果的には22位で1ページ目からも追い出されていた。結果的にはうみんちゅがほとんど通してくれて凄かったし、チーム組んだ中では優勝できてよかった。

感想

• とりあえず1問以上解けたのでよかった。大虐殺が起こったBでWAしなかったので褒めてください。
• 近くにずっと大声で話し込んでる人たちがいてつらかった。次チームを組んで出るときがあれば、もっと静かな場所でやりたい。
• チーム戦たのしい。
• 現時点で自分でFまで解いたけど、Dがむずすぎると思った。Gは落ち着いて考えると、解かれてしまう前に自分で解けたなぁと思った。

追記

Hまで解いた。Hは計算結果をメモ化しておけばなんとか間に合う、という発想にまったくならなかったな・・・