これは アドベントカレンダー2024 23日目の記事です。
概要
2024/12/21-2024/12/22に横浜産貿ホール マリネリアで行われた ICPC 2024 Asia Yokohama Regional Contest に チーム WADATSUMI として参加し、8完9位でした。
Asia Pacific Championship に参加できそうです。嬉しいですね。
チーム紹介
traPでガッとレーティング順に組んだ3人です。
- のつじさん(Nzt3): 私です B2 C++を使う 環境構築・問題文読解担当
- そたつ(Sotatsu): B3 Pythonを使う 全担当
- こめだわら(Rice_tawara459): B3 Pythonを使う 考察担当
使用言語が統一されていないので言語特化エディタを使うと複数エディタ同時起動になって設定が面倒です。今回はVSCodiumを使うことにしました。
今年のCodiumは拡張機能が入っていて補完が効くのでコーディング速度の向上が見込めます。(これが邪魔なこともあります)
チームの立ち位置
東工大(現 Science Tokyo)でYokohamaに出ているチームの実力は
AMATSUKAZE=Bocchi The Tech>WADATSUMI=zer0shiki
という感じです。
playoffの進出ルールに「1つの大学からは3チーム以下しか出れない(同大学制限)」があり、東工大のどこか1チームはplayoffに進出できません。
チームの目標
Asia Pacific Championship (playoff)進出=高順位で、かつ東工大内3位以上を目指します。
zer0shikiに勝てば条件はほぼ達成する見込みですが、1つだけ例外があります。
Regional優勝チームは最上位大会である World Finals の参加権を得ます、このときWorld Finalsの強い同大学制限が発動し、優勝大学の他チームは今シーズンの上位大会の参加権を失います。
もしAMATSUKAZEかBocchi The TechがYokohamaで優勝すると、我々は順位に関係なくplayoff進出権を失います。これは困るので他大学に優勝してほしいです。 選抜ルール的には(我々より強いチームにできるだけ多くWF同大学制限がかかってほしいので)京大に勝ってほしいですね。
国内予選
参加記があります。ホスト校枠で通過しました。
Nzt3
横浜大会までの準備
チーム練習
Universal Cup に参加していました。検索あり(他人のICPC用ライブラリから窃盗するなど)、コピペなしのルールでやっていました。
他には毎週平日に1回対面でCodeforcesのGymから適当な5時間セットを選んで走るようにしていました。このときに去年のYokohamaでもらったキーボードが役立ちました。 LegalOn Technologiesありがとう……
大会が近づいてからは AMATSUKAZE(3人揃うことはない)、 Bocchi The Tech(3人揃うことはない)、 zer0shiki(開始時に3人揃っていることはない) との並走での対面練習もありました。
ライブラリ
とりあえず ICPC-notebook のリポジトリをクローンしてチームメンバーだけが入ったプライベートリポジトリを作ったのですが、全然準備を進めておらず、いつもkactlを使っていました。
その後に Speed Starのライブラリ が公開されたのでこれと kactlを持っていく方向になりました。
kactlとSpeedStarではマクロが一部異なりますが、ちょっと変えるだけで両対応にできます。
Yokohamaでは資料持ち込み数の制限がないのでより簡単なデータ構造も追加して持ち込みました。
tatyamさんの ICPC_notebook がベースになっていたのでコードの追加とPDF出力が非常に簡単でよかったです。
YokohamaのVSCodiumでは普段使っている拡張機能(Code Runner)が使えないのでコード実行用shellを書いて補うことにします。
本番のPCでは compilecpp や runcpp のような専用コマンドでコンパイル・実行ができるようになっているらしいので、これを順に呼び出すコードを書きます。配布されていた仮想環境での動作確認も行いました。
マスコット
During the contest, you may bring papers, drinks with closed caps, tissues, handkerchiefs, medicine, jackets, eyeglasses, and mascots ONLY.
mascotsの持ち込みが許可されていますね。これはラバーダック・デバッグで擬似ペアプロを行うためだと思います。どんなマスコットを持ち込んでも良いですが、言葉が通じて賢そうなやつの方がデバッグに役立ちそうですね。
私が用意したのはこちらの周央サンゴ(にじぱぺっと)です。
世怜音女学院中等部1年、演劇同好会所属、にじさんじも所属の周央サンゴさんは豊富な知識を持ちます。中学受験をして私立中高一貫校に入っているようなので多分中受算数とか競プロもできるんじゃないですかね。完璧な人選ですね。
Day 0
周央サンゴのオールナイトニッポンAの天気予報を聞き、服装を考えます。
どうやら寒いらしいので 長袖ヒートテック+トレーナー+フリース+ダウンジャケット+手袋 で対策することにします。
ライブラリは印刷し、念の為英和辞典と蟻本も持っていきます。
Day 1
会場最寄駅の馬車道駅から歩きます。
受付開始まで時間があったので赤レンガ倉庫の横を通るルートを選びました。
13:00受付開始で、私のチームは13:10くらいに入りました。
コーチがまだ来ていませんでしたが、問題なく入れました。
ルール説明(いつもの)、シャツの色分けの説明(よくわからなかった)、ジャッジシステムの説明(寸劇があり面白い)を終えたらリハーサルコンテストが始まります。
簡単な問題だけしかないので環境テストとして使いましょう。私はライブラリのハッシュが機能することと実行用shellが動くことを確認し、あとはジャッジステータスで遊びました。
拡張子でファイルの種類を判別しているらしく、言語を間違えて提出するミスは起こらなさそうです。
Snack Areaに大量のパンが置いてあったのでたくさん食べました。
巡回しているJAGスタッフに知っている先輩方がいてちょっと面白かったです。
真顔で巡回するebiさんとか名札を2つ付けているeiyaさんとか。
Day 2
飲み物の持ち込みが許可されているので好烏龍を持ち込みます。
最強の服装を着ていたので少しも寒くない！
問題なく受付をして09:30のコンテスト開始を待ちます。
→09:15に開始が繰り上がりました。受付前にトイレに行っておいたので問題なく対応できます。
ライブラリはクリアファイルにまとめていましたが、中身だけ出して使います。ホチキスで留めておくべきでしたね。
some tough programming が始まります。
以下問題のネタバレがあります。
コンテスト
開始の合図で封筒を破り、システムのログイン情報が書かれた紙を取り出す。
→封筒と一緒に中の紙まで破れていた。ログインに支障はなかったのでOK。
ログインし、VSCodiumを起動する。
Aを読むと家庭菜園+monotonic stackぽさがあったので考えると実際にそうだとわかる。実装はやるだけ。
A AC(0:07)
Bはこめだわらが解いたらしいので実行用shellだけ書いてからPCを渡す。
B AC(0:16)
その間にそたつがC,D,Eを、私がL,Kを読む。
(Lは誤読している)
そたつによればEがやるだけらしいので問題を共有する。実際にDFSやるだけなのでそたつが実装する。
E AC (0:29 FA!!)
compilecpp,runcppが想定通り動かなかったので実行用shellをちょっと変更する。
runpython3は問題なく動くので序盤の動きには関係ない。
Kが高速ゼータ変換(20次元累積和？)で解けそうなのでそう主張する。問題をよく読むとタイブレークの条件が面倒そう。こめだわらに共有すると立っているビットの数最大をとる貪欲に正当性があることがわかる。
私が実装をするけど、サンプルが合わない。印刷に回して再度考える。
L,C,Dを共有する。(Lは誤読している)
私がKをやっている間にそたつ、こめだわらがCがギャグであることに気づいたらしい。
C AC(1:35)
Kは今の方針だと全bitが立っているときに困ることがわかったのでtop2を持つことにする。(実は不要)
実装すると、サンプルが合わない。
印刷してミスを探す。
ミスを修正してみるとまだサンプルが合わない。
Iのsegment treeの実装にPCを渡して再度考える。
min_leftが想定通りに動かないらしい。わからない。
ンゴちゃんと話しながらKのコードを読んでいると、最後にペアの片方を全探索する部分が壊れていたことがわかる。PCを奪い修正する。
K AC(1:56)
Iの実装が終わったらしい。
I AC(2:03)
こめだわらがGの方針を立てたらしいので聞く。直線で切って出入りを数えるとゴール候補の領域を半分にできて、縦横交互に切るとクエリ回数が20000回くらいで間に合うらしい。
グリッド1列の出入りだけカウントしても答えが確定できないという話をすると、グリッド2列を調べれば境界での出入りがカウントできることを教えてもらえた。クエリ回数も28000回程度で大丈夫そう。
私が実装を考える。
N=2,3の適当なケースを回すと通ったので提出 WA
わからないね。
私とンゴちゃんがGのコードを眺めている間にそたつ、こめだわらがDを詰める。
D AC(3:22)
凍結前の順位表を見ると結構上位にいる。もう1問通せばplayoffには出られそう。
Gの良い実装方針として「長方形領域の入次数と出次数を数える」というものが思いつく。
実装するとかなり簡潔になった。
提出 WA
こめだわらがLを生やして実装する。サンプルが合いません。
ここでLの誤読に気づく。ごめん。
私がGのランダムテストを書く。
一部のケースで全然違う領域を探索し出すことが判明する。全ての変数を出力させると、明らかに探索にバグがある。ンゴちゃんの指摘で変数名のtypoがあることがわかる。
修正してN=2000のランダムケースを走らせると、too many stepsが返ってくる。こめだわらに実装方針を話すと、クエリ回数が 16N でちょっと足りてないことがわかる。自明な改善(実装量2倍)を入れるとクエリ回数が足りるという評価ができたので実装する。
無限バグをランダムテストで修正し、提出する。
G AC(4:40 +2)
ジャッジが長くて怖かった。
順位表を見ると、Screenwalkersが独走している。WFの同大学制限が発動することはなさそう。
Lを眺めてコンテスト終了。
コンテスト後-解説前
配られていた弁当を食べました。全完でもしないとコンテスト中に食べる時間はないです。
解説
今回は9階の部屋で解説をするらしいです。英語での案内だったので荷物の扱いがよくわからなかったですが、貴重品だけ回収して部屋を移動しました。
全チームがA,Bを通し、全チームが3完以上していたらしいです。すごい。
D parsing (笑) だけどグラフと区間の綺麗な対応があってすごい。
G Interactive-> Binary Search(そうだね) Implementation(そうだね)
L なんか謎の区間DPが出てきたように見えるけど、これを自然に出せるようになりたい。
J 幾何だったり幾何じゃなかったりするらしい。そうなんだ。
Yes/No
みんな大好き順位表解凍の時間です。
自分のチームの8完とペナルティで東工大内3位は確定しているので9完以上がどれだけ出るかが気になるところです。
tcknyoのときだけ Yes/No が Yes/nyo になるの面白くないですか？
Objective-KUB1の凍結後3提出が全て通ったり、Screenwalkersが11問目を通したりと盛り上がりました。
最後の問題をACしていない場合の全提出はあまり面白くないよ。
WADATSUMIは 凍結前10位→解凍後9位 でリクルート賞を獲得しました。
我々は「焼肉クーポン」を手に入れたけど、君は？
Closing Buffet Party
スポンサーブースを回ります。
賞を頂いたリクルートに挨拶をし、ちょっと知っている fixstars, Monoxer, HUAWEI, LegalOn Technologies を回り、 chokudaiさんと話しました。スポンサーのみなさまに「AtCoderのコンテスト経由で知りました！」と声をかけると良いらしいです。学生のみなさまは企業広報に「賞金付きARCを開いて！」という要求をしましょう。
freee と Geo Technologies のブースで話を聞き、AtCoderってすごいね〜ということを考え、すくさんに話しかけに行って物理好きさんとkeymoonさんに会うなどしました。
解散
みなとみらいのイルミネーションを見て帰ります。
これから
Asia Pacific Championship 2025に向けて準備をします。
対戦よろしくお願いします。
