ICPC2024国内予選参加記 (Spinning-akabeko zawatin)

ICPC2024 国内予選にチームSpinning-akabekoの一員として参加しました。6完23位！

チーム
練習(~模擬国内)
模擬国内
当日
コンテスト
国内予選を終えて

チーム

(敬称略)

Abeshi2002: 考察、数学大臣。

CleyL: 考察、簡単枠の掃除、パズル大臣。

zawatin: 実装、典型大臣。

練習(~模擬国内)

チーム練習

ICPC-Japan Problemsから問題を選んでバチャを走っていました。週3。

Universal Cup Season3 Stage2も走りました。めちゃくちゃ難しかったけど、知見も多かった。*1

バチャを走る中でチームの戦略を固めていって、

CleyL -> AB
zawatin -> C
Abeshi -> D以降を読む。できそうなやつから解く。
あとはよしなに、得意分野と相談しながら。重い実装はzawatinがやる。

という感じになりました。

個人的な練習

1 幾何問題の対策

後半に置かれるような難しい幾何問題は最初から捨てるとして、前半に幾何が出ると困るので対策しました。*2

2 バチャの解き直し

解けなかった問題は解説AC。実装に苦戦した問題は特に苦戦したパートをライブラリ化しました。

3 悪あがき

本番数日前に重心分解を履修しました。kotatsugameさんの動画で重心を求めるコードを写真記憶 -> 重心分解使う問題を何問か通しました。付け焼き刃だったけど、当時は「この世の木上のパスの数え上げ全部解けるぜ〜」みたいな自信で溢れていました。

模擬国内

ICPC模擬国内2024@luckYrat_ @Linaria57315311 とSpinning-akabekoとして出ました。selected20位！

A: CleyL
B: CleyL
C: Abeshi
D: 僕が嘘解法で沼る -> Abeshi (ありがとう)
E: CleyL -> 実装僕。dp[i][j] := swapした / j th の { 回数, 残り座席 }
— カスタネット (@zawakasu) 2024年6月29日

動き

CleyLがABを解いている間にC問題を読む。むっず！とりあえずSOSを出しておく。DがグラフとのことでAbeshiと担当を交代することにした。

D問題はグラフの連結成分を状態としたdpを考えた。CleyLがABを解き切っていたのでそのまま実装。サンプルが合わない。助けてくれ。

AbeshiがC問題の考察を終わらせていたので、AbeshiにPCを明け渡してD問題をCleyLに相談。

CleyL「例えば $(2, 3) \rightarrow (1, 2) \rightarrow (2, 4)$ と操作が行われたとき、人 $1$ が過去問 $4$ を持っていないことは把握していますか？」私「把握していないですね。やっば。」

D問題が普通に解けていないことが判明。改めて考察しなおすが、全然わからない。困り果ててくねくねしているとCleyLが「実は既にEが解けている」と報告が来た。問題概要と考察を聞いた。あってそう以外に言うことが無かった。

程なくしてCをAbeshiが通す。自分はD問題で貢献できそうにないので、E問題の実装をもらって二人にD問題を任せた。

5~10分くらいでE問題の実装が終わる。一箇所バグらせたがCleyLの指摘により修正が秒で終わる。 -> AC

AbeshiがD問題解けたらしく、解法の確認もCleyLが済ませていた。そのままAbeshiが実装開始。私とCleyLでFの考察を始める。

二人でアイデアを出し合っている間にAbeshiがDを通す。G以降のAC数も少なかったのでそのまま3人でFを考えることにした。

各々で10分程度考えたあと、アイデア共有。Abeshiが「 $\text{dp}_{i, j} :=$ $i$ 体目以降のスライムについて、現在左端にレベル $j$ のスライムがいる状態から操作を始めたときの最適値ができるといいなぁ」と発言。

それを聞いたら天啓が降ってきて、 $i$ 体目のスライムをレベル $j$ にするために必要なスライムの区間がダブリングの要領で求まりそうだと思った。

PCが空いているので私ががちゃがちゃこのアイデアをコードに書き下してみることにした。この解法が嘘だったときに踏まえて二人にはFの考察を続けてもらう。

ちょっと時間かかったけど実装が終わってサンプルが通る。二人が作ってくれた様々な入力ケースもパスしたので投げてみる -> AC。きもちええ。

3人でG問題に挑戦。残り時間が少ない。見通しの良いsomethingも無い。 $O(N^{2}K \log (\text{hoge}))$ の愚直を書いて6分以内に実行が終わることを祈ることにした。それすら実装が間に合わずタイムアップ。全然サンプルが揃わなかった。

問題毎の感想

AB:
C: Abeshiも $O(N^{3})$ で通していた。中点を列挙すれば良いことに気づけなかった。
D: 期待値の線形性... 苦手.... zawatin典型大臣解任
E: 去年の国内予選のEに似ている
F: ダブリングを使う問題あまり解いたことなくて不慣れだったけど、すっとでてきた
G: 類題を解いたことがあったのに解けなかった。申し訳ない.....

模擬国G、何か既視感を感じていたんだけどこれだhttps://t.co/4vF4CTMiKY

これも模擬国Gも配るDPでずっと考えてて破綻してた。学習しないなぁ。
— カスタネット (@zawakasu) 2024年6月29日

総括

序盤うまく立ち回れなかった。私のせいすぎる。反省しています。
最終的には良い成績が取れた。
AbeshiがC, DをCleyLがEをあまり時間をかけずに考察を終えていた。二人が考察強いことを再確認できた
私はポンコツだったが、F解いたから許して♡

当日

前日の練習でうまく立ち回れなくて本番始まるまでテンションだだ下がりでした。自分から負のオーラが出てなければ良いと思うけど、出てたかも。

リハが終わった後は16時まで各々でのんびりしていました。私はサークル室(競プロ部では無い)に行ってシャニマスで遊んでいました。摩美々のリバーシブル・トーストを読みました。シャニPが頑張っているコミュは面白いですね。超どうでも良いですね。

16時以降はPC前に集まって雑談したり、戦略の確認をしたり、持ち込み物の最終確認をしたり。

コンテスト

動き

ICPC2024国内予選@Linaria57315311 @luckYrat_ と出て6完！強い！

A CleyL
B CleyL
C xy >= 0で場合分け
D (x, y, dir)をstackに積んで行って、同じ所に来たらstackをポップすることでサイクル長を取得
E CleyL → バクらせ →僕が実装強奪。
F Abeshi
— カスタネット (@zawakasu) 2024年7月5日

CleyLがABを始める。当初の予定通りCを読む。

制約が小さいのでBFSで解けることを確認。CleyLがABを通すまで算数解を考えてみることに。

全探索お姉さんの休日のような邪悪な座標系では無いようだ。つらつらと考えているとクエリ毎 $O(1)$ で解けた。