雑記

魔法少女になりたい

ICPC2020 国内予選 参加記

出ました

コンテスト前

延長ケーブルと充電器、手の乾燥対策にハンドクリームを持ってきた。12時くらいに現地について、食堂でご飯を食べてから12:30くらいに演習室についた。人がいるかと思ったけど一人しか居なかった。

開始までかなり時間があって暇だったので、もくもくとMatrix Calculatorや他の500程度の問題を解いたり、初級者の一年生にダイクストラ法を教えるなどしていた。

今年は自PCで事前準備ありだったので、いろいろとコンテスト前にできた/する必要があった。具体的には、

  • Discord/LINEを落とした,PCも含めた全端末の通知を切った
  • ライブラリの検索/貼付用にhttps://beet-aizu.github.io/library/リポジトリをローカルに落とした
  • 事前にテンプレートが入ったクリーンなディレクトリ(a/a.cpp,b/b.cpp,c/c.cpp...) を問題分作るシェルスクリプトを書いてコンテスト前に回す運用をした(コンテスト中にまわして消し飛ばしたらかなり嫌なので、回し終わったらrmした)
  • 拡張とかがいろいろあって間違って変なものをクリックしたら嫌だったので、chromeのプロファイルを新規作成した
  • VSCodeのデバッガが狂うので、CTF用に改造されたgdbをデフォルトに戻した
  • ID/passをローカルファイルに落とした

等をした。これは2週間前くらいから持ち物等と一緒にリストアップしていた。

10分前くらいに喉が痛かったのでのど飴を買った。そこそこ効いたと思う。

それと打ち上げがコンテスト終了後20分で開始らしく、かなり慌ただしくなることが予想されたので事前にある程度出れるようにはしておいた。

コンテスト中

始まった。と同時にDBが壊れているとのエラー。リロードしなおせば治ってるだろとか思いながら何回かリロードしても駄目で、シークレットブラウズでログインし直すも駄目みたいだった。さようなら……

こどふぉった後に開始時刻のアナウンスがまたあるだろうとか言いながら、突然繋がったら嫌なので5秒間隔くらいでF5を押していると突如繋がる。も、practice前の様子。

打ち上げの開始時刻の心配や運営チームの心労の心配とかをしながら引き続きリロードをしていると、状態がpracticeになっていた。今ならFA取れるぞとか冗談をいいつつ順位表をリロードすると、問題が8個くらいあることに気がつく。始まってね?

Aを見る stringにしてsubstrとかをすることが頭を過るも、Aなので何も考えずa[i-3],a[i-2],a[i-1],a[i]を比較するコードを書く。通る。4分

Bは読解が秒ではなかったので僕がBをやることに。らずひるどが問題概要を予め把握していてくれたので、やるだけだった。やる。通す。8分

Cはかなり難しそうで、すくなくともサラッと通せる問題ではなさそう。とりあえず目を通し、105くらいまで列挙すると残りが簡単に定まるのではないか?と思うも1010くらいなので駄目っぽい。最初108くらいになると思って解けたとか言っちゃった、ごめん。Dが構文解析っぽいのでそっちをやったほうが良いとのことで回ってくる。

Dは構文解析はあるにはあるも本質ではなさそう(BNFが1行とか2行とか) 。とりあえず出てくる変数を決め打ちそう→全変数間の大小関係を2-SATの変数として持ち、それぞれの式と推移性について条件式を作れば良さそうだなあとか思う。が、数えられないので終わり。

頭を捻っているとCが通る。(40分) この時点で学内2位/全体31位とかでbeetさんがかなり動揺していた。Dが全く解けなかったので聞くと、秒でn<=16なのでbit全探索と言われる。なににbitを建てるのかさっぱりだったので聞くが、決め打ったら後必要な情報がそれより大きいか小さいかだけと言いながら震える手で図を書いていた。ボロボロになりつつも秒で解法を出してきていて凄いし、それを30分出せなかったのは素直にかなり反省。???「これができないのは、ヤバいよ」

ということで書く。構文解析パートは関数一つだけでなんとかなるレベルのゆるい奴。正直僕もかなり動揺していたので、文字からindexへの変換をmap持って終わらせればいいものをわざわざ式内に登場するシンボルを置換したりしていて本当によくない。20分くらいで書き終わる。サンプルが合わん、何がいけなかったんでしょうねぇ…… 15分くらい唸るも、原因は

if (op=='<') return a < b ? a : b;
else return a > b ? a : b;

if(op=='<') swap(a,b);
return a > b : a : b;

を等価だと思っていたことだと判明。コンテスト中には何故これが等価でないのか分からずに納得できずも、とりあえずサンプル合うからヨシ!をした。(それぞれのreturnはminとmaxということにすら気がついていなかった)出す。通る。80分

そうこうしているうちに、Eがなんかギャグらしくて解けたらしい。なのでF読むかをしてらずひるどの考察を聞いているうちにEが通る。85分

ここで状況確認。とりあえず5~6位くらいで、早めに5完はしたので通過はしそう?FGHを読むも、GHは1時間半で0完なので捨てて良さそう(Gは見込みはなくはないが、Hは完全にヤバい幾何なのでさようならという感じ)。残りはFということで、Fの考察をすることに。

少ししてFが方針が生えたらしく、聞くと合っていそう。ただ、計算量が壊れそうなケースを見つけたのでそれを提示するもいい感じの方法が帰ってくる。あと70分くらいしかないので、とりあえず並列で実装をしてどっちかが通したらいいね作戦をすることに。

かなり後に気がついたんですが、ここで壮大なアンジャッシュが起きていたらしい。というのも、サンプルを試して解法を共有する際に両者の解法に少しズレがあったにも関わらず偶然同じステップを踏んでいた。嫌なケース等で合意が取れたので、把握している解法が違うなどとは思いもしない。

かなり辛い実装だったが、なんとか書き上がる、15分前。出す。合わない。解をソートしていないことに気がつく。ソートする。出す。合わない、10分前。 サンプルを試してステップ実行すると怪しい動きをしていそうだと気がつく。条件式が間違っていたので直す。出す。合わない、5分前。考察自体に致命的なミスがあることにチームメイトが気がつく、1分前。

終了 全体8位

ふりかえり・反省

ABは文句のない動きができた。Dで迷走したのは本当に頭が備わっていないせいで、高難度の練習を実装偏重にしていたのもあってよくなかった。頭を使おう。

Fでは、サンプルをチームで試して共有した上に生成した最悪ケースの出力が一致することを確認した。そのうえでのこれなので、今回はほぼ不幸な事故だったと思ったほうが良さそう。強いて言うなら、手で試せる範囲で一番強いサンプルを試すべきだった。

ただ、ある考察を否定する時に言っていることが全く分からなかったが、考察を投げた人が納得したので渋々納得したのは戦犯ポイント。ここで指摘していれば気がつけたかもしれない。言っていることの意味が分からず、かつ意味がわからないことに確信が持てるならば、ratismをぶっ壊して相手を疑うことをしたほうが良さそう。

ということで、チームとしての自分の動きも、個人としての自分の動きとしてもそこまで納得がいくものではなかった。結果はそこそこ良くはあったが、olpheチームに負けたなどもあってかなり悔しいのは確か。

なお、Fは自分のコンテスト中のコードを2byte書き換えたら正解チームのoutputと一致した。本当に下らないミスでとても悔いが残る上、思い違いをした解法が合っているとなるともう気がつきようがない気がする。ただ、終わったことなので今悔やんでもしょうがない。これを回避するには強くなるしか方法はないので、強くなる。  

コード

a.cpp · GitHub

b.cpp · GitHub

d.cpp · GitHub

Revisions · f.cpp · GitHub (初版がコンテスト中のコードで、その後が修正後のおそらくACコード)