メンバー紹介

全員24B (学士2年) で、水青青の3人チームです。3人とも昨年のICPCには出ていましたが、この3人でチームが成立したのは今回のICPCからです。

Oxojo

かなり昔から競技プログラミングをしているらしいです。メンバーの中で唯一(まともに)JOIの経験があり、AtCoderに限らず幅広い傾向の問題に対応してくれます。あとタイピングがめちゃくちゃ早い。traP内でも有数のはずです。

jupiter_68

もともとずっと数学とかパズルをやっていたらしく、昨年入学後に競技プログラミングを始めていました。ARCとかが得意な印象です。主に数学と構築を見かけたら任せることにしています。

zoi_dayo

筆者です。AtCoderは ZOIZOI で、最近あんまり出れていないけれど一応青コーダーをしています。AtCoder Beginner Contest以外の成績は悲惨です。

DP/SegmentTree/グラフ/木構造/再帰/環境構築 などが好きで、数学/パズル/構築/幾何/構文解析 が苦手です。

見て分かる通り、3人の得意分野がちょうど別れているので、問題ごとにほとんど自動的に担当を決めることができます。僕としては好きな問題だけを解けるので非常にありがたい。

前日まで

チーム練はかなりやりましたがあんまり成績は良くなかったです。寝坊しないように頑張りました。

当日

平日なので直前まで授業を受けていました。
計算機室のパソコンのセットアップはチームメンバーにやってもらっていたので、run a みたいな感じでa.cppをコンパイル→成功時に実行し、ファイル経由で標準入出力をするスクリプトを書いておきました。ICPC国内予選の多くの問題はマルチテストケース形式になっており、問題文で与えられるサンプルは1ファイル/問題として扱えることが多いので、事前に各問題のhoge.inファイルを作っておきました。

東京科学大学の計算機システムは(少なくとも僕が試してみた範囲では)WSLとの相性がいまいちで、MinGWのg++を利用することにしました。sanitizerあたりが使えないことが弱点ですが、-D _GLIBCXX_DEBUG くらいは利用可能なので、とりあえずこれを使いました。

考察用のデバイスとしては、シャープペンシル(0.3/0.5/0.7)、消しゴム、ノート、万年筆あたりを持っておきました。実際にはほとんど万年筆しか使っていなかった気がします。

国内予選

初動

ICPCの時間計測の仕組み上、(微々たる差かも知れませんが) 最初の問題を高速に解くことができればうれしいです。
画面を3分割し、左半分にエディタ(VSCode)、右上に問題pdf、左下にも問題pdfを置きました。
A,B問題にはそこまで考察に時間がかかる問題は配置されないという読みで、A,BをともにOxojoに実装してもらうことにしました。その間に右下の画面にC、続いてDを表示し、僕とjupiterで考えます。

jupiterと2人で覗きました。7で割ったあまりを考えつつ丁寧にやるんだな〜と思いましたが、そこの詳細を詰めるのはjupiterのほうが得意そうです。

D

jupiterにDを見てもらったところ、すこし面倒そうだということでzoiがDを実装することにしました。問題の主張自体は簡単ですが、細かいケースの考慮と実装にすこし時間がかかりそうです。

このタイミングでBのACが出たのでjupiterに代わり、僕はDを少し丁寧に詰めます。

まず「白黒の境界が規則正しく(間隔は問わず、格子状に)配置されているか」を調べ、その後で「間隔が条件を満たしているか」を調べる方針にするとよさそうです。

この間、Oxojoにはそれぞれの問題の雰囲気を把握しておいてもらいます。1問10sくらいで、

• Eがグラフ
• Fがグラフっぽい...? わからず
• Gが幾何
• Hが括弧列
• Iがなんか最小回数

くらいの粒度で確認しました。構文解析は無さそうだな、と思いつつDを詰めているとCが通ったようなのでPCを占有します。

このあたりで問題文の印刷が終わり、画面を左右2分割にします。

Dをガリガリと書いている間に残りの問題を確認してもらいます。Dがサンプルで実行エラーになるので印刷に回し、その間jupiterに思いついたらしいFをやってもらいます。

DのコードをOxojoと2人で確認したところ、vectorの.size()がunsignedを返すことに起因するミス (rep(i, v.size()-1) みたいなもの) を発見し、一瞬コンピュータを借りて出します。がWAです。

jupiterに書いてもらっている間に再度確認すると、単純なnとmの取り違えを2箇所発見しました。と同時にFが通ったようなので修正してACします。

E

残っている問題のうちEが木らしいのでこれを見ます。制約が小さめで木なので適当にDPすればいいかな〜と思い考えてみると、「その頂点にいつまでに到着する必要があるか」を記録しつつ木DPをすれば解けそうに見えたので、いったんサンプルを手動実行します。2人に正当そうかどうかだけ確認してもらい、実装します。

実装の間に他の問題を考えてもらいます。どうやらHが解けそうらしいです。

実装してテストしてみるとなぜか答えの個数がズレます。出力サンプルを見ると、頂点数nに対し経路をn-1要素しか出力しなくて良いらしいです。スタート地点が指定されているのを忘れて rep(start, n) {} とすべて試すコードを書いていたので、適当にrepを解除して int start = 0; で解決しました。提出してACです。

G

jupiterがHを解けたそうなので実装をしてもらいつつ、残っているG/Iについて、Oxojoに概要を教えてもらいます。
Gは幾何っぽい図が書いてあって面倒そう、Iは区間DPなどかと思ったのですがシンプルな設定の上に2乗が通らないので厳しそうです。
いったんGをOxojoにまかせてIを考えていたのですが、Oxojoがサンプルを試しているのを見ているうちにGが解けそうな香りがしてきます。

答えはmin(n, m) + 2 <= ans <= n + m + 2 に収まることに気づき、ここからどれだけ減らすか考えます。Blenderを脳内に召喚しつつサンプルを見ると、上下で平行な辺があれば一つづつ減っていきそうです。n, mも小さいので、適当な全探索→累積→共通要素探索 が通りそうです。

すこしシンプルすぎるかと思いましたが、順位表を見るとGがそれなりに通されていたので見掛け倒しだろうと実装に入ります。REが出て困っているHを印刷に回し、ガっと実装です。ただし今回の問題では「厳密に平行かどうか」を判定する必要があり、小数をそのまま浮動小数で扱うのは怖かったので、stringで受取り、すべてを10^9倍したlong longで扱うことにしました。

サンプルが合わず一瞬だけHに交代しましたが、HはWAになったらしく席を強奪します。Gを修正したもののまだサンプルが合わなかったのですが、与えられるのが外角でなく内角であることを忘れていただけだったので修正し、ACします。

残り

この時点で残っているのは後ろ2問でした。が、Hはペナが2つになってしまっていて、その瞬間に通しても校内4位になれなさそうということで、3人でIを考察する流れになりました。

時間が残り60分程度しかなく、Iはほとんど考察ができていなかったため、いったん「左右の2ブロックに分けてそのあと一致するようにswapする」など非自明な仮定を大量において方針を定めることにしました。が、正しくなかったらしいです。

コンテスト終了

あまり考察を詰められないままコンテストが終了しました。順位表を見たところ予選突破ボーダーが全完となっており、Iが通っていたとしても厳しかったようです。

結果

全体では19位/355チーム、校内では6位/28チームでした。

得意分野がバラけているのが功を奏したのか、メンバーのAtCoderレートを基準に考えるとかなり良い成績だと思いますが、やはり科学大の上位の壁は厚いなという気持ちです。
(詳しいルールを無視すると、科学大からはおおむね4チームほどが国内予選を突破できます。)

リプレイを見てみると、一度も20位以下にはなっていないようです。ので前半の「解けるレベル」の問題に関しては良いということでしょう。来年はちゃんと解ける問題を増やして再度挑戦したいですね。

他のチームメンバーも参加記を書くようなので、ぜひ読んでみてください。