ICPC2019国内予選参加記
ICPC2019国内予選に参加しました 結果は5完最速で4位でした 模擬国内予選がチームブン回って5位で、実際には模擬国内予選に参加していない同格クラスのチームも多くかなり心配していたので、本当に安心しました・・・
前日まで
模擬国内予選で構文解析が弊チームの圧倒的弱点であることが判明した為、ここから当日までこんなバチャも立てつつひたすら構文解析やってました
前夜
去年の国内予選の構文解析問題「数式探し」の誤読(各数字1桁とは限らないと思っていた)に気付く これなら出来そうだなあと言いながらやる 2時間程かかって絶望する 「明日の構文解析、Cあたりに自明で出るか、Hあたりに不可能で出てくれ〜〜」とか言いながら布団に入る
ところで僕はイベント前夜は全然寝られない人なんですよね。2時間ほど寝付けず布団を温めていました。
当日
1限があるせいで4時間くらいしか寝られなかった 休講にしろ
東大の国内予選では、プリンターは会場にあるものを他チームと共有するか、或いはチームの私物を持ち込んで使用するということになっていました 20チーム近くいるこの会場ではプリンターの使用待ち時間も痛く、ちょうどボーダー上にいるであろう我々は少しの時間も惜しむ為、プリンターを僕が持ち込むことになりました
プリンターを持って駒場着 マジで重かった 腕が破壊された
プリンターを起動して無線LANに繋ごうとする
あれ？eduroam繋げられないんだけど
どうやらこのプリンターはeduroamやUTokyo-Wifiを拾うことが出来ないらしい(なんか通信規格とかの問題？らしい) この辺から顔が引きつり始める
idsigmaさんが生協にUSBケーブルを買いにいく その間に適当にリハ通す
戻ってくる 繋ぐ プリンターが認識されない...
この辺からいよいよヤバいという空気が流れ始める
色々やるとPCがプリンターを認識してくれる 問題ページの印刷ジョブを投げるとプリンターが印刷を始める
「あー良かった！」
「何とかなったね！」
「じゃあ他の準備しよう」
などと笑いあっていると、明らかに問題文ではない謎の文字列が印刷されて出てくる は？
いよいよチームから完全に感情が消えておきもちになる コーチにチェックを貰う為の準備も必要なので、この辺で私物プリンターの使用を諦める 何で持ってきたんですか...?
意地が汚いので、部屋内唯一のプリンターまで徒歩2秒の席を確保する その後も他ユーザーアカウントのファイルが見られるようになっている等のトラブルを皆で必死こいて調べながら何とか対処してギリギリチェックが間に合う 確かこの時点で16:20くらいだった
本番
開始直後は各チーム問題を印刷するので当然プリンターが混む 一番最初に問題文の印刷権を手に入れる為、問題データをpdfファイルに変換してUSBファイルに突っ込むムーブを無限回イメトレしてた 後ろ見てなかったけど多分うちが一番速かったと思います
Aは流石に無なのでそのまま実装してAC なんとFAだったようで2つの企業賞を頂けました やったね
直後にBをidsigmaさんが実装に入り、Cをrisujirohが考察する とりあえず後ろを読むことに
Dはすぐには分からないけど暫く考えれば分かりそう
このEやりたくないですね 誰がやるんですか？ 絶対僕がやることになるやつですね？
F難しそう 何だこれ
Gよく分かんない これもゴリゴリシミュレーション系？でもそんなのGに来るか？(まだ構文解析ということに気付いていない 流し読みが過ぎる)
幾何がHだと分かる (risujirohが)幾何が強く、FGあたりに(うちがギリギリ通せるくらいの)難問で来ると爆アドだったので少し悲しくなる
しかしその直後にGが構文解析だと気付く 明らかに見た目ヤバそうだしこれそんなに解かれないだろ やったね
idsigmaさんがBをAC 全体5番目だったらしい 速い
Cが少し実装を詰める必要がある問題だったらしいので、Dが出来た気になった自分が実装に入る
この時点では「押す必要のある回数が最も少ない場所の必要回数を+m回する これをnループやればok」とかいう今思い返すと完全に狂ってる解法を生やしていた よくこれで実装しようと思ったな
実装残り2行くらいになったところで、「いやこれ候補2箇所あったらやり方によってはおかしくならない？てかそもそもこの解法おかしくない？」と気付く 明らかに反例は作れそうなのだが、反例を頑張って考えるより20分のペナを差し引いてもジャッジくんに今すぐ教えてもらった方がプラスになると考えて投げる 当然WA
ここ生きててごめんなさいペナ pic.twitter.com/ea41Uhzs1Y
— こるとん (@kyort0n) 2019年7月12日
恥です。
明らかにやべー解法だったので、ソースコードと入力と出力を印刷してPCをrisujirohに譲ることにする
これを印刷するとこうなります
バカか？
これで印刷代500円くらい取られました 金返してくれ...
そしてこんな入力見せられても当然何も分かりませんでした 何で印刷したんですか...?
考えるとO(N^3)のdp解法が降ってくる risujirohがCを通したので実装に入る 実行にそこそこ時間掛かったけど無事AC
僕がDをやっていた間に他の2人がEの考察を詰めていてくれたらしくて、やるべきことを伝えられる 「じゃあよろしくね」と言われる
3箇所くらい途中でバグらせつつも、40分くらいで実装+デバッグ完了 実行に10分くらい掛かるも無事AC ここ完全に神懸かっていた...
その後は全員でFを考えて始める 誰も良い解法が思い浮かばない
PCが空いているのも勿体無いので、小さいケースでの実験コードを書き始める
これを無限にバグらせる 本当にE実装したんですか...?
実験コード書き終わった頃には終了10分前 流石にもう不可能なので、国内予選突破ほぼ確定を喜び合いながら雑談していた
合同バチャや模擬国内予選等々で全敗のheno_worldより上にいたのでへへーんとか言ってたら残り40秒でE通されて逆転された 犯罪だろ
アジア地区予選へ向けて
そういう訳で、無事アジア地区予選に進めることになりました
WFに進むためには学内1位になる必要がある訳ですが、圧倒的格上のチームが2つ存在するのは厳しいですね
1チームだけなら何らかのアクシデントで運良く勝てることも無くは無いと思うんですが、2チームあると...参ったなぁ...
今年はセミファイナルというステージが存在するという噂もあるらしい？これは情報を待つしか無いですね
来年以降出る人へ
プリンターはちゃんと家で動作確認しろ
