自己紹介
東京理科大学のチームOSMAです。読み方はオスマです。 去年まではja君と別のチームで出てたのですが、今年は野田キャンパスの白椿さんを誘ってチームを結成しました。 白椿さんは横浜に出場するのは2回目で僕とja君は初です。
- srtubaki
- atcoder青色 知識が豊富 実装が早い MA学科
- pres1dent
- atcoder水色 グラフやクエリの問題が得意 OS学科
- ja14378
- atcoder水色 数学系の問題が得意 OS学科
コンテスト開始まで
起床に成功し朝ごはんを食べました、ちょっと量が少なめだったけど大会中の昼食に期待してホテルを後にしました。
会場に到着し、駆けつけてくれたコーチのヘキサさんに挨拶をしたり、記念撮影をして入場しました。 写像12相の記事を印刷してきてくれて渡してくれました。本当にありがたかったです。
入場してからはリュックや電子端末ををビニール袋に入れたり、ライブラリをファイルから取り出したりと、何だかんだ準備をしていたら開始まで残り２分になっており、あっという間に始まりました。
本番
リハーサルではもたついてしまったので、素早く封筒を開封し、パソコンの環境を整え、サンプルの入力をja君に変わってもらいます。 （終わってから知ったのですがサンプルってダウンロードできたんですね）
Bの考察をします。早く解かないとという焦りから問題文を流し読みしてしまい、最も小さいものを出力するという条件を見落としていました。白椿さんがAを通してくれた(0:18)ので、実装をしました。
結局実装もバグらせて、嘘解法のため２ペナしてしまいました(0:40ぐらい?)。冷静ではなかったのでデバッグをja君に変わってもらいました。解法が思いついてから実装するまでは紙でコーディングをしていたのですが、もっと条件やサンプルを確認すれば良かったとめちゃくちゃ後悔しました。
Eが解かれていたので読んでみるとdfsでできそうとわかったので白椿さんに問題と解法を伝えて実装してもらいます。 もう自分では実装なんてする気になれず、実装の強いチームメイトがいるのは本当にありがたかったです。 Bはプリントデバッグに交代です。
解かれていたKを読んだのですが、誤読して変数mとnを逆だと思っていて、愚直が通るとかbitset高速化とか嘘解法を生やしていました。白椿さんがEを無事通して(1:19)くれたので、Kの嘘解法を共有すると、サンプルが合わないことを指摘され、嘘に気づきます。もしかしたら英語を読むのが下手くそなのかもしれません。いや日本語でもよく誤読してるから関係ないか。 その後、二人で考察を進め、大体の方針が立ち、残りを白椿さんが考察&実装をしてくれました。
実装が終わり提出するとWAが出てしまいます。 話を聞いて条件を整理すると、2つの会議に出席できる人数が多いほど良いという条件が抜けていることが判明… ２人で考察をしていた時に抜け落ちてしまっていました… 反省を生かして、条件が抜け落ちないように問題文をja君とあらかじめ読み合わせ、問題文にメモまで書いてあるのですが、解法を思いついた時には忘れていてしまったのです。馬鹿すぎる〜〜〜。
そして再提出するとまたWAでした。 Bで２ペナをすでに出してしまっているのでむしろ開き直っており、デバッグすれば絶対通るよ的なことを言った気がします。 そんなことをしている間にja君のデバッグが終了し、再実装して無事ACを取ってくれました(1:27)。本当にありがとう…。
その後、順位表の情報により、ja君がCを読解し解けそうということを共有してくれます。 問題概要を聞くと、割とすぐ解法と証明のようなものが思い付きました。 証明のようなものは、あとで整理してみると主客転倒の式変形で正しいのですが、その時点ではだいぶ直感的で自信がありませんでした。しかし、PCが空いていたので、解法を伝え実装してもらいます。
その後、Kの問題文を読むと2つの日付はdistinctという部分があり念の為確認すると、WAの原因になっていそうでした。 原因がわかったとはいえ修正するのは大変そうでした。
この時点で自分達が解いていない問題の中ではKやIがかなり解かれていて、Iは解かなければいけない問題だと思い諦めずに粘りました。Iはセグ木やMoのような考え方では全然歯が立ちませんでした。想定解はセグ木の二分探索なのですが。 結局クエリを先読みし座標順に処理することを考え、単調性を保持しながら値を更新することで、計算量を減らすことができました。
考察している途中でja君がCの実装で寄与を求める部分で苦戦していたので、実装を交代しCを通しました。(2:56) その後Kのデバッグを白椿さんがやりきり、こちらもACが出ました。(3:00) 自分は無限にIの考察をしていて行き詰まっていましたが、そんな時でもチームメンバーがACを取ってくれるのがチーム戦のいいところだと思いました。
Iの解法はチームメイトに話したりして正当性には自信がありましたが、Bの実装で2ペナもしてしまったので、実装はやりたくありませんでした。しかし、そこまで自信があるなら自分で実装するのがいい的なことを言われてしまい、Iの実装をやることになりました。蓋を開けてみると、データ構造が不要で場合分けなどもシンプルだったので実装はそこまで苦労せず無事ACを取ることができました。(3:44)（本大会１番の偉いポイント）
残り2時間ほどで6完しており、ペナが多いことを考えるとplayoffに進出するためにはあと２問解く必要がありそうです。 この時点ではまだ希望はギリギリあるかなという気持ちでした。 少なくともDは解く必要があると判断し、Dにで3人取り組むことにしました。
チームで少しずつ考察を出し合い、少しずつ考察は進んでいきますが、本質的な数え上げに帰着できず、ただ時間が過ぎ去っていきました。結論から言うと２時間以上取り組んでいましたが、競技中に正解することはできず、終了五分前ほどに、白椿さんが正しい解法を思い付いてはいたのですが、実装は間に合いませんでした。
最終的には６完で、凍結前順位は26位で最終的な順位は32位でした。最後の数時間で１問も解けず悔しかったです。 そして、Dやその他の問題を時間内に解いている上位チームとの実力の差を痛感しました。 playoffに進出できなかったのは残念ですが、そもそも４年目にして最終年でようやく横浜に参加できたので、この場にいるだけで嬉しかったです。
解説会 & 懇親会
解説会ではGの解説が面白かったです。また、目を通さなかった問題が結構あったので、ちょっと後悔しました。
懇親会ではkotatsugameさんにお会いしAA Quineの話をしました。AAに埋め込んだチーム情報などに気づいてくれていて嬉しかったです。また、「チーム紹介スライドに何で実行エラーのリンク載せたんですか」と聞かれてしまいました。直前までpaizaで実行確認をしていたのですが、コードを共有すると編集できてしまう問題があり、直前にideoneに提出して「なんか動いてそう」と思ってしまいました（実行結果ぐらいちゃんと確認してくれ…）。ICPCのTwitterにもスライド付きで写真が載ってしまっていて困っています…。ICPCの関係者には申し訳ありません。ideoneの実行環境ではevalがdangerousという理由で実行エラーになるので、他の実行環境を教えてもらいました。 あとで、AA Quineの記事を書く予定なのでその際にきちんと動くリンクを用意しようと思います。
あとハイパーロボット対戦が楽しかったです。４連勝ぐらいしてシールをたくさんもらいました。 他にもいろんな人と話せて良かったです。懇親会は会場全体が盛り上がっていて楽しかったです。
おわりに
良い子のみんなは問題文を正確に読もう！
