ICPC国内予選2020参加記

ICPC2020国内予選にizryt，nayutaとチーム「Cutting Tree」として参加しました．結果は3完81位で，ギリギリ予選通過ならずでした...
本番の様子を書いていきます．

開始前

  • 起床後，ライブラリと参考になりそうな記事を片っ端からダウンロードする．
  • 大学に行って糖分補給用にラムネとチョコレートを買う．なゆたさんと合流後，ライブラリを入れたUSBを家においてきたことに気づく（は？）

  • 急いで取りに帰って再び大学に戻り，いずらいと君とも合流する．
  • PCをセットアップしてるといつの間にか14:30くらいになっていたので，リハーサルをする．最後の問題が普通に解けなくてびっくりした．
  • その後は最初の問題の担当を決めたり，ツイッターを見ていたりして過ごした．

開始後

  • ログインしたらいきなりエラーになってめっちゃ焦る．運営の方に電話をかけようとした瞬間に問題が見えるようになる．
  • いずらいと君がAを，なゆたさんがBを，自分がCをみる．Aが爆速（3:17）で通されていてビビった．
  • Cをみて，Pの約数2つを全探索しか思いつかなくて辛くなる．とりあえず実装してテストケースを回すと無限時間かかる（それはそう）．このあたりでBが解かれる（32:34）．
  • 他に方針が思いつきそうにないので，頑張って高速化をする→実行する→遅すぎて止めるというループを繰り返す．
  • これ以上高速化できそうにない...となり，しばらく頭を抱えたあと，ふとターミナルを見ると実行が終了していることに気づく（は？）．
  • 慌てて提出してCorrectをもらったので，もう一つのテストケースもぶん回して，ACをもらう（59:35）
  • Cの実装中にDが構文解析だということを聞いていたので，自信満々にDを読む．
  • 最初N<=8だと誤読していて，「O(N!)で常勝！ｗ」となっていた．その後N<=16なのに気づき顔面蒼白になる．
  • 構文解析パートを実装して，とりあえずO(N!)解法（各変数に対して1～Nの順列を割り当てる）を書く．テストケースの実行が終わらない．
  • 「いくつかの変数に値を割り振ると，残りの変数への割り振り方によらず各式の値が一定になる」という場合があるということに気づき，その場合をまとめて計算するようにするも実行は終わらず．
  • この時点で枝刈りによる高速化に固執してしまい．残りの時間はずっとこれを考えていた．
  • 途中Fをみて「フローでは？」みたいなことを言うが嘘だった（は？？）
  • その後も，高速化を試みる→テストケースで無限時間かかるを繰り返し，Dが解けないままコンテストが終わった．

個人的な反省点

  • Cを高速に通そうとして時間を食い，Dを枝刈りで通そうとして他の解法を捨てるという，本当に良くないムーブをしました．
  • 特にDは途中でいずらいと君が「bitDPでは？」と言っていたため，その時点で解法を考え直すべきでした．
  • チーム名のCutting Treeは「枝刈りをしてでも問題を通したい」という気持ちがこもっているのですが，実際には枝刈りで問題を通すには実力が必要（高速化の知識や現実的な時間内に終わるかの見積もりが必要なため）だと痛感しました．