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位!
— カスタネット (@zawakasu) 2024年6月29日
A: CleyL
B: CleyL
C: Abeshi
D: 僕が嘘解法で沼る -> Abeshi (ありがとう)
E: CleyL -> 実装僕。dp[i][j] := swapした / j th の { 回数, 残り座席 }
動き
CleyLがABを解いている間にC問題を読む。むっず!とりあえずSOSを出しておく。DがグラフとのことでAbeshiと担当を交代することにした。
D問題はグラフの連結成分を状態としたdpを考えた。CleyLがABを解き切っていたのでそのまま実装。サンプルが合わない。助けてくれ。
AbeshiがC問題の考察を終わらせていたので、AbeshiにPCを明け渡してD問題をCleyLに相談。
CleyL「例えばと操作が行われたとき、人
が過去問
を持っていないことは把握していますか?」私「把握していないですね。やっば。」
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が「
体目以降のスライムについて、現在左端にレベル
のスライムがいる状態から操作を始めたときの最適値 ができるといいなぁ」と発言。
それを聞いたら天啓が降ってきて、体目のスライムをレベル
にするために必要なスライムの区間がダブリングの要領で求まりそうだと思った。
PCが空いているので私ががちゃがちゃこのアイデアをコードに書き下してみることにした。この解法が嘘だったときに踏まえて二人にはFの考察を続けてもらう。
ちょっと時間かかったけど実装が終わってサンプルが通る。二人が作ってくれた様々な入力ケースもパスしたので投げてみる -> AC。きもちええ。
3人でG問題に挑戦。残り時間が少ない。見通しの良いsomethingも無い。の愚直を書いて6分以内に実行が終わることを祈ることにした。それすら実装が間に合わずタイムアップ。全然サンプルが揃わなかった。
問題毎の感想
- AB:
- C: Abeshiも
で通していた。中点を列挙すれば良いことに気づけなかった。
- D: 期待値の線形性... 苦手.... zawatin典型大臣解任
- E: 去年の国内予選のEに似ている
- F: ダブリングを使う問題あまり解いたことなくて不慣れだったけど、すっとでてきた
- G: 類題を解いたことがあったのに解けなかった。申し訳ない.....
模擬国G、何か既視感を感じていたんだけどこれだhttps://t.co/4vF4CTMiKY
— カスタネット (@zawakasu) 2024年6月29日
これも模擬国Gも配るDPでずっと考えてて破綻してた。学習しないなぁ。
総括
- 序盤うまく立ち回れなかった。私のせいすぎる。反省しています。
- 最終的には良い成績が取れた。
- AbeshiがC, DをCleyLがEをあまり時間をかけずに考察を終えていた。二人が考察強いことを再確認できた
- 私はポンコツだったが、F解いたから許して♡
当日
前日の練習でうまく立ち回れなくて本番始まるまでテンションだだ下がりでした。自分から負のオーラが出てなければ良いと思うけど、出てたかも。
リハが終わった後は16時まで各々でのんびりしていました。私はサークル室(競プロ部では無い)に行ってシャニマスで遊んでいました。摩美々のリバーシブル・トーストを読みました。シャニPが頑張っているコミュは面白いですね。超どうでも良いですね。
16時以降はPC前に集まって雑談したり、戦略の確認をしたり、持ち込み物の最終確認をしたり。
コンテスト
動き
ICPC2024国内予選@Linaria57315311 @luckYrat_ と出て6完!強い!
— カスタネット (@zawakasu) 2024年7月5日
A CleyL
B CleyL
C xy >= 0で場合分け
D (x, y, dir)をstackに積んで行って、同じ所に来たらstackをポップすることでサイクル長を取得
E CleyL → バクらせ →僕が実装強奪。
F Abeshi
CleyLがABを始める。当初の予定通りCを読む。
制約が小さいのでBFSで解けることを確認。CleyLがABを通すまで算数解を考えてみることに。
全探索お姉さんの休日のような邪悪な座標系では無いようだ。つらつらと考えているとクエリ毎で解けた。
CleyLがAB両方通しきった(2:41, 6:13)ので実装 -> AC(8:10)。
AbeshiからD問題が実装問題であると報告を受けて、そのまま私が担当することにした。問題読んで本当に実装問題だったので実装開始。入力受け取ったあたりでが
くらいまで取りうることに気づいて横転。がちゃがちゃ書くより一回しっかり考えることにした。
一直線に進み続けるような移動はまとめて行うことにする。そうするとサンプルのような複数回同じ(座標, 向き)を経由するようなケースは問題無いが、サンプル
のようなぐるぐるするケースが困る。
ぐるぐるする場合、同じ(座標, 向き)に来た時点でその「一周の長さ」を特定すれば良い。現在残っている移動距離を一周の長さで割ったあまりにまで短くすることができる。
一周の長さを特定する方法に少し悩んだ。stackにいままでの(座標, 向き)とこの状態における進む距離を計算して積んでおくことで、同じ状態に来た時にstackをポップして一周の長さを取得することにした。
後は気合気合と言いながら実装。100行くらいかかった.....。
ちょうど実装が終わったあたりでCleyLがEが解けてすり合わせもAbeshiとすませたと報告が来た。はっっや。実装変わりたいと主張してきたが、自分はサンプル試してデバッグするだけなので、ちょっと待ってもらうことに。
と思ったら一撃でサンプルが通る。ちょっと心配になりながら提出 -> AC(34:53)
喜びよりも困惑が強かった。100行も書いて一度もバグらないなんて経験競プロ初めて2年数ヶ月、一度も無かった。
AbeshiがFに集中していたので、私はCleyLのEの実装を後ろから突くことにした。E問題の概要と解法を聞く。解法が全然理解できなかったので、コードからわかる事実のみでサポートすることにした。
- この添字はテーブルのここにアクセスしているよ とか
- ここの実装が言っていることと違う気がするよ とか
数分後にAbeshiからFが解けたと報告を貰う。はっっや。私が解法を聞く。解法が完全に理解できなかったのと、数学色が強かった解法だったので実装はAbeshiがやることになった。
Fを相談している間にEの実装が大炎上したらしく、実装をFと交換することになった。
Eを手伝う前にGの問題を眺めた。構築やめて〜。E終わったらCleyLに投げることにする。
ひとまずEの解法を理解することから始めることにした。正当性はわからんがやろうとしていることは汲み取れた。自分でも図を書いてみて、必要な添字を把握。
Abeshiが実装終えたがサンプルが合わないらしい。ここで再度実装を交代。私がEを書き直す。
Eを書ききるがうまくいかない。まずい!。と思ったがCleyLから2箇所ほど指摘があってそこを直すとうまく動いた。模擬国のときといい指摘が美味いな。
提出を試みる。でassertに引っかかったが、6分以内に直せてそのままAC(2:05:10)
AbeshiがFのデバッグをしている間にCleyLにGを渡す。割当っぽいしフローなんじゃないかなとか今考えると超的外れなことをCleyLに言ってしまった。
自分はFを手伝うことに。すでに一回ペナを出していて、Abeshiはそこの修正をしていた。自分は構文エラーとかを突っつきながら後ろで応援。
修正が終わって提出 -> AC(2:40:15)
残り20分。最後Gに抗う。
の総和が奇数のときは明らか不可能。総和が偶数の場合を考えれば良い。
CleyLがが奇数なら可能であることを主張。それを聞いて書く。
が偶数のときは
を並び替えれば奇数の場合に帰着できる。並び替え方はdpをして復元すると言われた。それを書く。バグる。タイムアップ。ごめんなさい!!!
問題毎の感想
- AB: Bがだるそう。ABをいつもノーペナで通してくれるCleyLには頭があがりません。
- C: 思考停止せず算数解を考えて良かったと思う
- D: どう実装するのが楽なんだろう
- E: 構築は丸投げ定期
- F: Abeshiはコインとボールがぶつかる判定をextgcdに帰着させていた。
- G: 構築は丸投げ定期
総括
(https://icpc-replay.vercel.app/chart?contest=2024_domestic&team=Spinning-akabeko より)
- 良い成績。selected 25↑を達成できたのが特に嬉しい。
- 自分がGをバグらせなければギリギリ間に合って7完ありえたのかなぁ...。たられば言ってもしょうが無いか。
- 三人それぞれがチームに貢献できた3時間だったと思う。
- 難易度感が模擬国とほぼ同じだったと思う。JAGありがとう.....
- SkyBlaze(同学チーム)には届かなかった。9位って凄すぎる。誇らしいやら悔しいやら。
国内予選を終えて
良い成績を出せたのは確かだけど、戦略・コミュニケーションをもっと練ればさらに良い成績を目指せたと思う。横浜までもっと鍛える。
個人としては、典型大臣再就任できる様にABCやECRをがんばります。本当かな。口だけかもしれない。
*1: 箱根駅伝dp とか 分割統治でdpが高速化できるタイプの問題 に触れました。
*2:今年からライブラリがokになることも踏まえて、簡単目の幾何が出題されたら例年より多くのチームが通してくると予想していました。解けなかったら悲惨なので練習!