ICPC2017国内予選

きゅうりが消えたため、たこの友人を新しくチームメイトに加えた。

なお彼は競プロ初心者らしいのだが、頭が良いのでアジア地区では化けてくれると信じている。

僕らのチームはどちらかというと考察が得意で実装が苦手なため、初動で遅れることは予想していた。その為焦らずに正答数を伸ばすことを心がけていた。

結局ペナルティ差で後輩チームに負けてしまったが、阪大で2チーム突破は多分初なのでめでたい。

f:id:aki33524:20170715173602p:plain

A, B, Cはそれぞれが並列で解いてあとは流れでやろうという話をしていた。僕がC。やるだけ。

A, Bがそれぞれちょっと詰まっていたけど当初の目標であった3問1時間以内は達成された(遅すぎる……)。

その後、僕がDを読む。最初はmod 2における行列の一次独立とかrankとかそういう話なのかなぁと思いそれにハマってしまった。行列計算はちょうどO(NM)が出現するのでそれもハマりの補助となった。 DPと全探索はすぐに見えていたので、冷静に計算量を書いたら分かった。去年の筑波のI問題を彷彿とさせる問題だと思う。考察に時間がかかり過ぎた上にDPフェイズで結構バグらせた。この程度は一発で通せるようになりたい。

たこらがEを読む。最小積和形にすればいいんじゃないかとかなんとか言っていた気がする。結局文字数の制約に気がついて考察は立った。

とは言えこの時点でまだ4完。残り時間は1時間を切っていた。普通に落ちる未来が見えて焦った。

多分僕はEよりFが得意だろうと判断して考察する。紙で色々書いていると方針が立つ。残り30分。Eはバグったらしい。

Eのバグを取りつつ紙で詰める。indexが厄介なので実際に各操作を手で試してみて両端と真ん中が整合性が取れていたらOK!という経験上バグりにくく且つ高速な方法を取った。

残り15分。僕がFを実装しながらEを紙でデバッグ。Fもバグる。印刷。

残り10分。Eのバグが分かったらしい。書いてもらう。僕もFのバグを見つける。条件やら操作は全て合っていて一箇所typoが合った。これを見つけたのは奇跡だった(経験上typoのバグは焦るとマジで見つからない)。

残り4分。Eが通る。僕に代わる。

typo修正してサンプルが通る。実行して出力を確認せずに投げる(時間がなかったため)。手が震えてコマンドめっちゃtypoしてた。

残り2分。Fが通る。皆でワイワイしていた。

終了後後輩チームらと飯を食べながら解法議論していた。彼らのF問題の解き方はイミフ過ぎたし、彼ら自身も全く証明していないらしい(サンプルが強いためサンプルが通ればまずOKという見立ては非常に正しいと思う)。Gはフローじゃないかなぁということを話してご帰宅。

経験上僕は焦った時のパフォーマンスが著しく落ちるので、Fを実装するときは努めて落ち着くようにした。結果かなり良いパフォーマンスが出せたと思う。良い経験ではあったが、二度とやりたくない。