ICPC2018国内予選参加記(仮原稿)

ICPC2018国内予選参加記(仮原稿)

ICPC2018国内予選の参加記です。本当は別の場所にまともなのを書こうと思っていたんですが、どうも時間が無さそうなのでここで雑に書いてしまいます。

60°(sixty_deg)さん、baton(goodbaton)さんとeiyaで60odnightとして参加しました。

当日までの様子

traP(デジタル創作同好会)と言うサークルに所属しているので、サークル内でチームを組んでもらいました。 どうもその段階でチームが決まっていなかった人の中で上から3人選んだっぽい?

模擬予選の前後に一回ずつ集まってバチャコンをやりました。

一回目は僕がバグらせたのを何とか直して5完+F惜しい 模擬予選は僕が盛大にDをバグらせて4完(ちなみにこれだと学内予選落ち)2018/Practice/模擬国内予選/順位 - ACM-ICPC Japanese Alumni Group 二回目は三人が三人ともバグらせて遅解き5完+F証明出来ないので書かなかったんですが解説を見たら正解だった+H制約見落としで解けなくなってた

チームの動きは、始めに60°さんがAを、僕がDEを、batonさんが全体を読み、A(60°さん)->C(batonさん)->B(60°さん)->D(eiya)という動きがなんとなく出来上がっていました。

当日の様子

僕の目標は(練習のときにバグらせまくっていたので)「バグらせない」ということでした。 本番機にはVisualStudioもマイスニペットも入っていないのでなかなか落ち着かない。 水曜日の練習でbatonさんからVSCodeでデバッガが使えるという事を聞いて設定したので模擬予選での失態を繰り返さないようにと意気込む。 (普段の環境がVisualStudioなのでデバッガが無いと生きていけない) 以下回想なんですが、記憶が無いので時系列が入れ替わってたり飛んでたりしそう。

まず予定通りeiyaがDを読むんですが、解けない(は?) 仕方が無いのでEを見る。 解けない。愚直に足すとTLEするのでダブリングが必要となりそうとなる。 この時点でbatonさんが圧倒的目力でBがヤバそうと見抜き、batonさんがBを解き、60°さんにCを解いてもらうことに。 僕はEもDも解けないのでDを考察。

60°さんが順当にAを通し(有難い)、batonさんのBの実装に取り掛かる。 とりあえずDPをしようとして計算量を確認する。
8C4* 7C4以下 * 6C3以下 * ... *1C1以下
8C4==70だしこれギリギリ行けるのでは???(今計算したら17640000なので普通に間に合う)

この段階でBの実装が変っぽいので交代してDを書いていく。 そのままいい感じに再帰を書こうとしていると、普通に書くと計算量がCじゃなくてPになることに気が付き冷える(後で話を聞くにどうもPでも刈れるので通るらしい) 僕が冷えたのでBの誤読に気が付いたbatonさんに交代。確かこのころ60°さんもCの考察が終わっていた気がするので暫く二人にコンピュータを預けて紙コーディング。 BC通る。凄い。batonさんがE,F,G、60°さんがFを読む。

紙コーディングが終わったので計算量をCにする為の三関数経由の闇再帰を書くとCE(は?) 「lamdaうんちゃらは有効な型ではありません」(みたいな感じだった気がする) 印刷してbatonさんにEを書いてもらう。 ミス一か所見つけたので一旦代わってもらって修正するもまだエラー。テンプレート関数特有の長ったらしいエラーに悪態をついてコードの末尾にエラーメッセージをコピペして再印刷という†悪魔的行為†

batonさんがEの実装の続きをしている間に60°さんに自分のコードの状況を説明したところ、注目していた行の下に原因が書いてあるのに気が付く。 「関数の引数が一致しません」 これやんけ!wとなって交代して修正。

実行したら初期化ミスとかしてたのでそこは直したがまだ無限ループっぽい挙動。 模擬予選ならここで冷えるものの今回はデバッガがあるので一時停止からのステップ実行で洗うとforを無限に回していることが分かる。 原因がオーバーフローなのは明らかなんですが、そもそもオーバーフローするはずが無いので他の個所がヤバそうと主張して印刷して交代。

印刷したコードを睨むとオーバーフローするはずなので該当箇所がやばい(完) batonさんが順調に書いていたのでそのまま紙デバッグ。ちゃんと睡眠をとった頭だったので脳内ステップ実行が出来てバグがめっちゃ見つかる。

一通り紙デバッグが終わって自信を持ったところで交代してもらって書き終わる。 通った!!

batonさんがEを解けそうなので60°さんとFを解くことに。とりあえず今まで出来たFの考察を聞くと三角形の底辺は木を含んでいるはずとのこと。なんかDPっぽいなとか検討違いの事を言いながら考察したところ3辺全て木を含んでいるはずということに気が付く。 これ二辺決めればあと一辺はO(logN)で求められるしギリギリ109で勝ちでは。

batonさんがEを通して(プロ)、コンピュータが空いたのでeiyaが書く。 書き終わるんですがサンプルが通らない。 ここでbatonさんが僕の実装だと三角形の二辺の外の木もカウントしていることに気が付く。(悲しい) 上下は底辺をスライドさせて消していけば良いとして、もう一辺は削除と二分探索を両方やらないといけない。険しい。この時点で残り30~45分くらいだった気がするのでGの実装を諦めてFの実装を続けることにする。 間に合わないとは思いつつもbatonさんに書いてもらい、最後書き終わるもバグらせててサンプルが合わない。悲しい。

コンテスト終了

結果

順位表:LiveSite

全体13位、学内3位でした。 公式な発表は出ていないけれども恐らくアジア地区予選に行けそう!嬉しい! 層が厚すぎるうちの大学で勝ち残れるか微妙だったのでとても良かった。 当日までに黄色復帰にとどまらず橙までもっていきたいなぁ...

今は構築,構文解析,データ構造,アルゴリズムを全部batonさんに投げているのでどれかは出来るようにならないとないけない。 せめてダイクストラ,ワーシャルフロイド,二分探索,BITくらいは空で書けるようになりたい。