ICPC2021国内予選参加記

全体 2 位/学内 2 位でした！！ 去年落ちて悔しかったので今年は無事通過出来て良かったです。

折角なので本番中の動きについてメモっておきます。

• 本番前

  • 作戦を説明。のいみが BC, jell が A, シャーペンに DEF を読んでもらうことに。

• 本番

  • ページが繋がらない。キレる。去年もやってたやんこれ～～と言いながら F5 してたらつながったので B を読む。
• B
  • 問題文を読むと解けてたので書いた。しっかりと問題選択を忘れて missing problem! を出しつつ AC
• C
  • 読む。めちゃくちゃ読みづらいし読めても解法がわからない。
  • 回転が怠いけどこれ形変わらないし実質根の取り換えだけだな。C だし実は自明な上界が達成可能？→すぐに嘘がわかる。
  • 全方位か～？んなわけあるか！ｗ
  • こうしてる間に A が通ったのと D が解けたのを聞く
• D
  • D のいみが実装した方が早いといわれパスを受け取る。
  • 代わりに C を jell に考えてもらう。
  • 話聞くとマジで DP 書くだけだったのですぐに AC。
• 再び C
  • やっぱこれ全方位しかなくね？と言われる。
  • ほかに解けてる問題もなかったので仕方ないから書きます！と言って書き始める。
  • 構文解析パートでバグらせるも子の数が少ないのもあって木 DP パートが結構サボれたのでそこまで苦労せず AC。
• EF
  • 一旦落ち着いたので順位表を見る。→BD FA だし余裕の一位じゃん！
  • E も F も多分解けてるといわれたが、F が嘘っぽいらしいので E を jell に書いてもらい F の聞き役に回る。
  • 基本的にはあってそうだが、有向グラフに辺を貼って強連結にするパートがダルそう/嘘多そう
  • 多種多様な嘘を生やしては撃墜を二人で繰り返しているうちに E が沼る。
  • 2 ペナ出したところで手伝いに行く。コード読んでもよくわからない

のいみ「とりあえず #define int long long でもしてみたら？ｗ」

jell「うーん、流石に変わらんと思うんだけどなぁ」

jell「え、めちゃくちゃ変わったんだけど」

のいみ「草」 → 無事 AC

• F

  • その間に考えた F の解法の一つが正しそうなことをシャーペンに検証/証明してもらったので実装に取り掛かる。
  • こういうのは証明ベースで考えた方がいいね(入次数0/出次数0がともに減るような操作だけしないといけない)
  • 多種多様な罠、罠、罠、バグ、嘘に困らされる。
  • 一応書きあがるがサンプルは i -> i がマッチングになってるやつしかなくて不安なのでチェッカーを書いて assert を入れる。
  • 走らせる！→ assertion failed →マジで殺すぞ
  • failed している小さいケースを出力させて検証を手伝ってもらってる途中でチェッカーが間違ってることが判明(は？)
  • 直して投げると assert が通る
  • そのまま投げると AC！チェッカー書かなければよかったじゃん…

• GH

  • 余った時間で GH を読む
  • なんか G は木幅 2 っぽい→マジでそうじゃん→時間ないわバカ
  • H は反転効きそうじゃね？式の形的に→マジで効くらしい→時間ないわバカ

というわけでコンテスト終了です。WF 目指してアジアも頑張ります！

追記

応援してくださった方ありがとうございました！あとでツイッターを見返したんですが、序盤と F 通したときに結構言及されてて嬉しかったです。