ICPC2023 国内予選 参加記（chinerist視点）

チーム　The Raspberry Candies で出場しました。乱文許してください。

チームメンバー

rniya 最近調子よくてレート爆上がり中 そのせいかまったく緊張をみせない

tabr ありとあらゆるコンテストに出まくっている 環境構築のプロ

chinerist pythonistaなのをいいことに考察だけして実装丸投げする係 楽しい

チームメンバー間で得意不得意の差はあまりないと思う。ただ全員構築が苦手で去年は2h30m時点でEが解けず予選落ちしかけました。

チームの戦略としては自分が考察得意よりとされた（本当？？？？？？？？？）+普段pythonメインなので、実装にはかかわらず考察を投げまくるのに徹していた。

当日までの練習

おもに土曜ののUniversal Cupでチーム練習。去年は本郷にきて対面で練習していたが rniya が本郷に行きたくねえと駄々をこねたので1か月前まではオンラインでやっていた（まあ本郷遠いし気持ちはわかる）。2週間前には自前のパソコン禁止、プリンター持ち込み禁止などの制約に合わせた動きの確認とかやってた。

当日

自分は実習の試問が直前まであったので終わった後急いで浅野キャンパスへ向かった。遠い…。 到着した後は東大生チームの多さに改めてビビり、予選突破できるか不安になりながら動きの確認をした。 10チーム分の印刷を1台のプリンターでやる以上、紙で届くのは時間がかかるので

  • tabrが環境構築している横でrniya、chineristでA,Bざっと見、C以降の問題文をじっくり読む
  • 環境構築おわったらrniyaがA実装、chineristはこの段階でC,Dの考察を始める
  • rniyaがA倒したら tabr がB実装
  • この辺で問題文が届くだろう、以降は考察できた順に

っていう感じで決めて臨んだ。

他には練習中に問題文誤読したのを又聞きして2人で全く別の問題を考えて時間を浪費するのを何回かやってしまっていたので、問題文の又聞きは禁止してダブルチェックすることに。

コンテスト

開始後、tabrが環境構築している横で問題文を読む。

A,B:ぱっと見Bはめんどそうだけど自明ではありそう

C:構築 去年のトラウマがよみがえる　ICPCで構築出すの禁止してくれ

D:変な問題　答えが小さくなること以外はパッとはわからない

E:n<=6000で総和が105以下？変な問題ではなくて通さないとダメっぽい

とEぐらいまで読んだところでtabrが作業を終えrniyaがA開始。自分はCを考えてみる。左右をひっくり返したりしたがどうしても1個だけやばくなるなあ、ぐらいの考察でとまっているうちにrniyaがAを倒したのでrniyaにCを押し付けてDの考察を開始。

D

Cが構築で動揺していたが冷静になると部分和問題でまともな貪欲とかが成り立つ気は全くしない。じゃあ全探索路線で考えるか→6個以下に分けるのだけ探索すればいいしそんなに時間かからずにおわるだろうと考えtabrに伝える。

この辺で問題文が届いたのでF,Gも読んでみる。

F:ここで幾何か～　面白そうだけどこんなんできるか？

G:サイコロ！？ライブラリ持ってね～、と思いきやそういう問題ではないらしい　読み終えた段階でABC257Exが想起され難しそうな気がしてくる

そうこうしているうちにCできたかな？と思って聞いてみると、行けると思った解法に穴があったらしい。ということでいったんtabrがDを実装することに。途中総和がnを忘れていたり部分和問題の結果がsと完全一致判定になっていたりしたが、わりと早くに指摘できAC。

この後はrniya+tabrでCの修正、chineristがEの考察を行うことに。コンテスト開始1hぐらいでCの修正案がでてきてAC。この時点でわりと出遅れてそうだな～と思い焦る。

E

Eは片方だけならLISだな～と考えて以降はn2テーブル必要になってダメだな～と思ってしまいあまり進まず（Eは勝負枠になるだろうという心づもりだったので無意識にn2はダメとしてしまっていた）。以降しばらくEとFを行ったり来たりしていた。しかしrniya,tabrがCから帰ってきたところでこれを伝えるとn2でいいんだからこれでよくね？となったので詳しい考察と実装を2人にまかせてFの考察を再開した。

F

サンプル1ができてサンプル2ができない理由を考えてみる。サンプル1はスライドで埋めれているからサンプル2はスライドしても無理なのか？と考えてみる。しかしサンプル2の図にいろいろ書き込むと凸にできる気がしてあれ？となる。考え直してみると配置する個数有限個になってないですね。じゃあサンプル1はなんで有限個でスライドみたいなことができるのか？と考えてみるとどうもへこみの前後の線分のおかげでできてるっぽいことがわかる。ここまで考察した段階で合流したtabrが

tabr「サンプル2Yesじゃね？？？」

と自分と同じ勘違いをしていたので考察を伝えると

tabr「じゃあ前後の線分が同じ直線ならいけてそれ以外無理なんじゃね？」

といわれる。他に条件がある気もしたが言われてみればたしかにそれで必要十分になってそう。ということで実装をtabrに任せてGの考察を開始。たしかこのぐらいにrniyaがEを通してくれた。

G

Gは不公平さへの各さいころの正確な寄与を把握しないと始まらないのでとりあえず式を展開してゴリゴリ計算していくと、結局サイコロの出目の期待値の総和2人分をkeyにしてdpで最小化すればよさそうというところまで行く。これだけだと606ぐらいだが

rniya「手元ならそれでぶん回そう」

と言われたのでとりあえず考察中にぶん回してもらうか、となり詳しい計算を説明…している最中に自分が書いた式をみるとどう見ても差だけでいいです（バカ1） まあでもこれでも7200n2mだからもうちょい改善考えようかな～

rniya「いや…これで間に合ってない？」

と言いたげだったのであれ？と思い見直すと7200にnが入っているのでn1個余計で7200 * 3600です。余裕やんけ（バカ2） ここまで話したところでtabrのFの進捗をみるとどうも凸包ライブラリが他のいろんなライブラリに依存してて思ったより大変そう、となったのでGを先に実装してもらうことになった。 途中2乗の期待値の36倍が2乗和になると勘違いしているのになかなか気づかず、答えが負になって首をかしげていたがなんとか気づいてAC

ハプニング

その後 Fの実装を再開したが、他のいろんなライブラリに依存してて思ったより大変そうというのを聞いて

chinerist「凸包ぐらいなら自力実装したほうがはやいんちゃう？」

と言ってしまった。結果的にこれで凸包構築の段階でバグらせてしまい、たぶん普通に写すより時間がかかってしまった。デバッグ出力をしまくりどうも外積の符号で余計な場合分けしているのがヤバそう、と特定しさあ直すぞ！とパソコンに向かうと

プツン…

PCが落ちてしまった。自分らだけかと思いきや周りの東大生チームのパソコンも全部落ちている。どうやら教室のパソコンは19時になると全部電源落とされるらしい。19時とか一番大事な時間帯に落とさないでくれ～～～～～～～～～～～～～～～～～～～～～～～

5分後くらいに再起動できたので修正。Yes,Noしかないので不安になりつつ見守るとそこにはCongulaturation!の文字が! というわけで7完に成功しさすがに通っただろうということで大喜び。

H

順位表を見るとまだ誰もH解いていなかったので時間内では無理やろな～と思いつつ一応Hに取り組んでみる。1個以外固定して最適化するとバス停は4辺上とか言えないか？とか思ったが、いろんなパターンを考えるとどうもあまり単純なことは言えなさそうな雰囲気。というかそもそもコスト関数がヤバくてこれをどうにかしないと意味なさそう。フローじゃね？と考え、双対問題とかに直した後 |x_i-a_i|+|y_i-b_i| <= r_i ってどうすればいいんだっけとなったところで終了。

感想+反省

7完4位でした。最近の練習だと失敗多めだったので不安だったが事故らず地区予選進出できて本当に良かったです。MCDigital賞うれしい。

反省点はありまくりで

  • 凸包自力で書いたほうが早いんじゃね？とかいってバグらせて結果的に遅くなった。本番で突飛な行動をするべきではなかったしライブラリももうちょい整備+把握してるべきだった
  • EGあたりで勝手に難しい問題だろうと思い込み解けていることに気づかなかった 難しいと勝手に思い込んでやらかすのは去年の横浜でもやっていたはずなのに…

地区予選までにはなおしてWF狙いて～ 頑張ります