ICPC 2022 Asia Yokohama Regional 参加記
2022/12/27,28 に開催された ICPC 2022 Asia Yokohama Regional に電気通信大学のチーム Kidamari Sketch として参加しました。チームメンバーは、 phocomさん、t98sliderさん、firiexpです。
コンテスト中の流れ
Aをみんなで読む。貪欲の問題。僕が実装した。$$O(n ^ 2)$$ が通るので簡単な実装を選んだ。CLionの設定は後でやろうと考えていたので、とりあえずVSCodiumを開いて実装した。for文の補完がなく苦労した。 AC(0:13)
Aを実装している間にBが解読されていた。問題概要を聞きながらCLionの設定を行った。インタラクティブだが簡単枠で、各桁でにぶたんするといいらしい。 引き続き僕が実装した。 AC(0:28)
C以降を流し読みする。DEFあたりが通されていたのでその当たりを中心に読むが、解法がすぐに思いつくものはない。開始1時間での各問題の印象は以下の通り。
- C: 問題文がいまいちつかめない。フローっぽい以外は何も分からない
- D 操作をしてAをBにできるか。よく分かっていない
- E: 二乗DPはすぐに思いつくが、高速化できない
- F: 見た目はとっつきやすいがいろんな繋げ方があって複雑。いい感じに並び替えてDPできそう
- G: 入力に癖があるので難しそう
- HIJK: 見た目がやばい
まずFを考えてみるが繋ぎ方などを考慮するとまともなDPにならない。結局何もつかめないまま時間を消費してしまった。
Eを考える。入力は文字列のためDPを高速化する方針であることは間違いない。I, C, Pの個数の累積和を取り、階差に変換するというのが良くある手法。ICPC文字列のIが一番多いとき、
\[ (Iの個数, Cの個数, Pの個数)=(x, y, y) \quad (x < y) \]
と表せるが、変数が2個あるためこのままでは解けない。
Dを考える。1個だけ動かすという点がポイントになっていそうだ。動かし方と回転方法を試し、合致するパターンが見つかればYesという問題。回転方法は4通り全部試せばよい。動かし方もそれほどパターンがなく、角の合わせ方を4通りくらい試せばよさそう。
t98sliderさんにDの実装を任せ、Eを考える。2つ変数があるのは辛いので、階差を取ってみる。
\[ (Iの個数-Cの個数, Cの個数-Pの個数, Pの個数-Iの個数)=(x-y, 0, y-x) \quad (x < y) \]
変数が$$ x-y $$だけになったので、問題は
\[ (P_i, Q_i, R_i) = (P_j+t, Q_j, R_j-t) \quad (t > 0) \]
となるような$$j$$について、$$ DP[j] $$の総和を求めていくようなDPになる。このDPの高速化を考えたが、この時点では解法が浮かばなかった。
考えている途中でDがWA。動かし方を角の合わせ方基準にしていたのがよくなかった。小さなずらし幅を何通りか試すという応急処置的な解法でAC (2:08)。
Eが詰まってしまったのでFを見る。部分和DPは使うんだろうなと勘づいてはいたが、解法にたどり着けないまま時間を消費してしまった。
Gの問題文を読んでみると、ダンジョンは木になっていることに気付いた。これならいい感じにするとできる。僕は実装が思いつかなかったのでphocomさんが実装した。 AC (3:00)
Eに戻る。tのみが変数でそれ以外は定数なのでmapに動的セグ木を載せればできる。TLが長いのでこれでも間に合いそう。しかしすぐに使える動的セグ木はなく、どうしようかという話になった。「BITの配列をmapで置き換えたもの」で代用できるという意見があり、それを採用することにした。
Eを実装するが合わない。残り30分くらいでバグの原因を探そうとするが、BITに原因があるのか考察に原因があるのかはたまたその他か、などいろいろ考え修正してみたがWAの連続。EをACできないままコンテストが終了。
結果は4完20位で実力相応という感じ。20位ということで企業賞のThinkPad トラックポイント・キーボードをいただきました。株式会社LegalOn Technologiesさんありがとうございます。
反省点
- A問題で普段使っているエディタでないVSCodium(拡張機能なし)を使ってしまったため、実装が遅くなってしまった。
- 前回のオンサイトの前はUS配列の練習をしていたが、今回はしなかったところ操作を忘れていた。本番の環境へは事前に慣れておくべきだった。
- 後から振り返ってみると問題文がきちんと読めていない。特に問題数が多いコンテストでは散らかりがちになるため慎重に読むべきだった。
- ある程度複雑な問題ではmodintを使うべきだった。
おわりに
僕はあと1回出場が可能なのですが、他の2人が今年で引退と言うこともあり来年については全くの未定です。新しいチームが見つかって都合が合えば出たいと思っています。
3年ぶりのオンサイト楽しかったです。ありがとうございました。