kazuma8128’s blog

競プロの面白い問題を解きます

ICPC Seoul Regional 2018 参加記

はじめに

ICPC ソウル地区大会に Zerokan_Sunshine というチームで参加してきました.
結果は 12 問中 7 完で 17 位でした.
10 完早解きじゃないと WF にいけないらしくてとてもつらい.

本番の流れ

うろ覚えで書いてるのでたまに時系列おかしいかも.

(0:00-1:00)
  • 開始直後に問題(なぜか1部しか配られなかった)をバラバラにして眺めるとDがタイピング問題っぽいのでsuibakaに投げる
  • suibakaと一緒に問題を眺めてるとサンプルがおかしいことに気付く
  • 問題文を読むと, サンプル output が間違っているという結論に至ったのでそのままsuibakaが書くとAC
  • えーなんだこれ

  • 次にCが見覚えのある問題っぽかったのでよく読まずに書き始める
  • 書き終えてサンプルが合わないのでちゃんと読み直すと, 順序を並び替えて良いことに気付く
  • 小大小大…みたいな感じでやると良いんでは?とか適当に嘘解法を生やしたけどサンプルすら合わないので一旦保留

  • nakanoから雑にH, E, Kの概要を聞く
  • Hは明らかに不可能かつ幾何なので後回し
  • Eはmaxの部分をなぜかsumだと勘違いする
  • 軽く考えたけど解けそうない
  • Kは条件が3つずつあるのと混乱して, 色も3つあると勘違いする
  • 2色なら2-SATだけどなあ・・・3色ならわからん, となる
(1:00-2:00)
  • suibaka に「書ける問題あったら投げて」と言われるけど無いと答える
  • PCが空いてることに耐えかねたsuibakaがFの構文解析を書くけどWA
  • 聞いた問題の中で解けそうな問題がなくて, ここから長時間虚無になる
  • 考察が全然進まないから昼ご飯食べてた気がする
  • nakanoがsuibakaにKを伝えてるのを聞いていると, 色が2色しかないことに気付いたので, 書き始める
  • 2-SATなのでSCCのライブラリをsuibakaに要求すると, 2-SATのライブラリ(復元付き)が渡されたので写経しまくる
  • 写経失敗したけどsuibakaに修正してもらう
  • やっと2個目のAC
(2:00-3:00)
  • nakanoにGを投げられて, できそうなので書き始める
  • 分数とIDをpairにしてsortするパートを書いて, のこりの確率計算パートをやるときにnakanoに確認したら値の範囲が整数じゃなくて実数だということに気付く
  • 適当にグラフを書きながら考えたら, 積分がかなりしんどそうなのでnakanoに投げておく
  • PCが空いてる間にsuibakaがLを書いて通していた
  • Iとかを考えていると, nakanoからGの完璧な場合分けと式が返ってきたのでAC すごい
  • 続けてsuibakaがFのデバッグに成功してAC
(3:00-4:00)
  • suibakaからAを聞いて一緒に考えると, 区間add区間maxの遅延セグ木で解けることがわかる
  • 順位表みてると異常に解かれててもっと簡単な方法あるのかな?とか考えたけど, 一応解けることに変わりはないので書き始める
  • ライブラリをめちゃくちゃ写経する
  • WAしたのでプリントアウトしてデバッグ
  • 交代してsuibakaがBを書き始める
  • Aのミスを見つけたので直してAC
  • その後すぐにBもAC
(4:00-5:00)
  • Cをnakanoに伝えると, 右端を全通り試して残りは左から小大小大…をするといけるかも?と言われたので書く
  • 嘘っぽいけど流石にサンプル1くらいは合うはずだが, バグりまくって全く合わないので絶望
  • この程度の処理でこんなにバグるのヤバくないか???
  • nakanoからEはにぶたんで解けると言われて, そもそもmaxをsumと勘違いしてることに気付く
  • それなら解けるじゃん・・・
  • suibakaがめちゃくちゃJを書いていたので, 交代交代で書くけどどっちも間に合わないまま終了

感想

いくらなんでも勘違いが多すぎるのでなんとかしたい.
でもうまくいってたとしても9完どまりくらいな気がするし, やっぱり韓国勢はヤバい.