feature image

2023年11月29日 | ブログ記事

ICPC 2023/24 Asia Yokohama Regional Contest 参加記(noya2 視点)

noya2 です。AMATSUKAZE というチーム名で参加しました。結果は 13 位で、そこそこの順位でした。うーん、悔しいけど。

チームメイトの 2 人が既に詳しい参加記を書いてくれているので、こちらもぜひご覧ください!

自分はあっさりめに書こうと思います。

メンバー

王はおいておくとして、得意分野が分かれていそうだったので、チーム練習の時もそれぞれがといた問題の分野も自然と分担できているようでした。

コンテスト前

TTPC2023 の準備で忙しく、本格的に練習が始まったのは本番 1 ヶ月前です。

コンテスト時間が 5 時間ということもあり、授業がある平日には時間が取れなかったので、主に週末の昼間に練習の時間をとりました。やったこと :

day1

時間通りに全員集まり、会場近くで昼食を取りました。会場に着くと多くの参加者が既に集まっており、社会性であることだなぁ、という感じです。会場では公用語は English ONLY とのことなので、頑張って英語でスタッフとコミュニケーションを取ります。意外といけます、相手も日本人なので。

リハーサルでは初めて触る CLion というエディタを使いますが、補完の利き方が普段使っている VSCode と違う以外はそこまで気にならずにコーディングすることができそうな感じでした。リハーサル用の問題は

でした。D問題は自分が過去に解いたことがあったので、Cがそうであった shobon さんと交代して自分は C 問題を見ることにしました。 ebi さんには開始直後に環境構築とテンプレートタイピングをしてもらいました。

すべてのジャッジステータスを出し、 Clar を投げ、キーボードに慣れ、リハーサルは終了です。

day1 終了後はチーム tonosama と中華街で夕食、美味しかったが料理名を覚えておらずです。ルーロー飯のお友達っぽい名前でした。

ABC330 に 60 分だけ出てすぐに就寝。本番楽しみ〜!

day2

全員が起床成功、 会場入りを済ませたらすぐに競技が始まりました。

予定通り ebi さんが環境構築とテンプレート写経、 shobon さんが A 問題、 noya2 が B 問題を見ます。

臨場感が欲しいので、ここから常体

A はすぐに AC ですごい。

B はシュミレーションだが誤読しそうで怖い、実装するも頭がバグっているため、全然サンプルが合わない。

Dの考察が終わったようなので一旦交代、セグ木で落ち着いてやろうとなって頭の整理が終わる。Dの考察ミスが見つかってPCが空いたのでセグ木を書く。といっても、ライブラリはほぼすべて shobon さんに写経してもらっているため、 min_left まで必要ですと伝えてタイピングゲームをしてもらう。写経が終わりBの実装をし直したがまだ頭がバグっており、破滅。もう一度 D と交代。もう一度落ち着いて考えると min_left は必要なくなった、 shobon さんすいません。かなり実装を詰めて AC ! (30 分くらいバグらせていて、本当に良くない)

序盤で出遅れたので、とりあえず順位表に助けを乞う。 EFGK あたりが狙い目に見える、Fは解けているらしいのでまだ読まれていない E を見る。問題内容は単純で典型に見える。ただ を落としにきている制約に見えるので、なんとか にしたい。 shobon さんと相談して高速ゼータ変換で条件をうまくまとめられると言われる、良さそうなので実装を任せる。このあたりで D と F は解かれていた気がする。

ebi さんから K が幾何&インタラクティブですとは聞いていたので、概要を聞いて自分の担当だと判断して取り組む。 ebi さんは木の問題である J 問題とフロー・LPに見える H 問題と I 問題に取り組んでいた。

そもそも円との共有点を持つ線分を引き当てるのに 回はかかる気がする。 軸と 軸で独立に中心座標を計算するつもりになるとそれだけで 回の質問回数を消費してしまい残りは 回、そうなるとそこから定数回で中心座標を当てる必要がありそう。よく考えると、 線分が円と交わってくれていれば、円上の 点の相対位置がわかることになり、外接円を求める問題になる。そのためのライブラリを持ってきていたので慎重に実装して AC! インタラクティブ用のスクリプトが提供されていたので安心だった。

G はやばそうな見た目の で、FPS的解釈を試みるも失敗、そもそもまともに解ける気がしない。shobon さんに modint の写経を任せて考察する。操作毎にカードの枚数が になることに注目すると操作回数はそこまで多くないように見えるので、PCが空いたところで実験をすると 回程度になると分かる。それなら単純な DP をメモ化再帰で回せばすぐに間に合うんじゃないか? -> 実装すると間に合うっぽい。体感で TL の 5sec を下回っていたので提出し、一旦落ち着くために離席していると、全然TLEしていた。あほばか。 time コマンドで最大ケースに要する時間を測るとやや間に合っていない。 std::mapstd::unorderd_map にして再度測ると間に合うっぽいので提出、AC! こういうペナが一番勿体無い、すいません。

この時点で ABDEFGK が解かれていて、残っている問題の中で勝ち目がありそうなのは HJ だろう、となり H は shobon さんに進めてもらい、 J は ebi さんと一緒に考えた。 H は正しそうな解法は既に生えており、実装もほぼ終わっているようだったが、解法が微妙に間違っているようでデバッグや再考察を要求されている。燃やす埋めるに帰着するらしいが、ここは shobon さんに任せることにする。

J は素直な木DPが 2 乗になって、全然嬉しくない。仕事の割り当てを考えると、いつもの条件(部分木内の仕事の個数が部分木サイズ以下)が浮かぶ。これを満たしながら貪欲に何かできれば嬉しい。そこでふと二日前の yukicoder で同じような考察をしたことがある気がしてきた。同じ操作を繰り返し行うとき、行う度にコストが増えていくという特別な制約がついていれば、できる操作のうちコストが小さい順に取っていけば良い、というものである。 に直してこの形式に当てはめれば、部分木の条件を満たしながら貪欲に取っていく問題になるのでは?となる。証明はしていない。

とりあえずこの方針を ebi さんに伝える。HLDを書きたくないのでなんとか部分木クエリだけで済ませようと頑張る(後から思えばこれは悪手だった)が、実装しては考察ミスが見つかるを繰り返してしまう。部分木の条件を動的に管理する方法が正確にわからず(HLDと遅延セグ木を使えばできることはぼんやりと分かっていた)瞑想してしまって時間をロス、よくない話。なんとかサンプルを合わせて投げると TLE で、実験をするとまだ考察ミスがあった。残り 40 分程度で実装は重いが確実な方法を取ろうということで HLD と遅延セグ木を書いてもらった。HLD は ebi さんに、遅延セグ木は shobon さんに書いてもらった。その後の実装を全て ebi さんに任せ、自分はライブラリタイピングにミスがないかをチェックする。

ライブラリタイピングをするのは shobon さんがやってくれることがほとんどで、タイピングミスは書いた人がチェックするのが普通だったので、自分は全然慣れていなかった。結果として、「あっています」と宣言した部分に 2 つもチェック漏れがあった。目が節穴。すべてのミスを修正するのに 20 分くらいかかってしまい、提出がギリギリになってしまった。AC が返ってくるのにものすごく時間がかかったように思えた。まぁ通ったのでよし!

H は結局通せなかった。帰宅後に shobon さんが upsolve してくれた。

結果として 8 完 13 位。チームレートで言えば悪くない成績ではありそうだが、もっと上を目指していただけに悔しい結果に。完数はあっても解くのが遅かったりペナを出したりして、同じ完数の中で下の方になりがちで、今後があれば大きな反省点です。

ここまで臨場感

コンテスト後

コンテスト後は解説があったのですが、J問題の正当性をマトロイドで説明することができるようで、興味が湧きました。それから、YesNoはかなりの盛り上がりを見せ、特にSpeedStarの4時間ノーペナ全完は本当に感動しました。

表彰が終わると、その後はビュッフェパーティーということで隣の会場に移り、食事をしたり他チームや企業との交流を楽しみました。

終始 tonosama の potato167 さんと会場をうろついていました。慶応のチームや優勝したSpeedStarのSSRSさんと少しお話をさせていただくなどして時間を過ごしました。東工大がホスト校だったため traP のメンバーが数人アルバイトとして会場の整備や受付などをしてくれていたので、大大感謝を伝えました。本当にありがとうございます。帰り際に SpeedStar の Segtree さんに話しかけてもらい、競プロの精進方法について盛り上がりました。 traP には traQ という closed でありながらサークル内では open なコミュニケーションツールがあるおかげで、オンラインでの交流が盛んで、これは競プロの精進においても便利なんです〜という話をしました。

上位チームに感化されて、もっと精進しなければ...!という気持ちになりました。今週は期末試験、え〜。

プレーオフ出場チームの発表はいつですか?

今後について

プレーオフに進出できれば、まだ先があるということになります。楽しみです。

ebi さんが今年で引退なので AMATSUKAZE は一旦解散か、 shobon さんと組ませていただけることになれば来年に向けて新メンバーを探すということになります。誰かいませんか〜。

さいごに

大会の運営陣の方、JAGスタッフの方、ありがとうございました! 本当に楽しかったです!

noya2 icon
この記事を書いた人
noya2

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2018年12月16日
ICPCアジア地区横浜大会参加記【アドベントカレンダー2018 52日目】
eiya icon eiya
2024年9月9日
ICPC World Finals 2024 in ASTANA に出場します!
potato167 icon potato167
2024年3月6日
The 2024 ICPC Asia Pacific Championship 参加記(Shobon視点, コンテスト編)
shobon icon shobon
2023年7月8日
ICPC 2023/24 国内予選参加記 (Series_205 視点)
Series_205 icon Series_205
2021年11月21日
ICPC2021国内予選参加記
ebi icon ebi
2020年11月19日
ICPC国内予選2020参加記【AdC6日目】
tatyam icon tatyam
記事一覧 タグ一覧 Google アナリティクスについて 特定商取引法に基づく表記