2023-01-06

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年ぶりのオンサイト楽しかったです。ありがとうございました。

2021-06-28

Codeforces Beta Round #49 (Div. 2) E - Dead Ends

問題概要

$$n$$ 頂点 $$ m $$ 辺の無向グラフ $$G$$ が与えられる。 $$G$$ の全域木であって、葉の個数が $$k$$ 個であるものは何通りか？

$$3 \le n \le 10$$
$$\displaystyle n-1 \le m \le \frac{n(n-1)}{2}$$
$$2 \le k \le n-1$$

https://codeforces.com/problemset/problem/53/E

解法

まず、頂点集合 $$S$$ を固定し、「$$S$$ に含まれる頂点は葉でなくてはならない」という条件を満たす全域木の個数 $$f(S)$$ をすべての $$S$$ について求めることを考えます。

$$n \ge 3$$ の条件から、葉の次数は1で、葉同士を結ぶ辺はありません。

また、全域木から $$S$$ を除いたグラフも木になるということを考えると、まず $$S$$ 以外の頂点を連結にしてから、葉を接続するとしてよいことがわかります。

$$S$$ 以外の頂点だけを考えたときの全域木の個数は、行列木定理を用いれば $$O(n^ 3)$$ で求まります。行列木定理を使わなくても、分割の方法を全通り試すDPを小さい方から計算すれば、 $$O(n^ 2 3^ n)$$ ですべての頂点集合について前計算できます。(この場合、マージの順番が違うだけの同じ木を重複して数えないように注意が必要です。)

次に葉を接続する方法の数ですが、これは各葉について独立なのでつなげられる辺を数えるだけでよく、簡単に求めることが出来ます。これで $$f(S)$$ をすべての $$S$$ について求められました。

この問題で求めたいのは、$$T$$のみが葉である全域木の個数 $$g(T)$$ です。これが求まれば、答えは $$|T|=k$$ となる $$g(T)$$ の総和として求められます。 $$f(S)$$ が $$S \subseteq T$$ となる $$g(T)$$ の総和であることを考えると、 $$g(T)$$ は包除原理から \[ g(T)=\sum_{T \subseteq S} (-1) ^ {|S|-|T|}f(S) \] と計算できます。これは部分集合をそのまま計算しても全体で $$O(3 ^ n)$$ で求められます。高速メビウス変換を用いることで $$O(n 2 ^ n)$$ で計算することもできます。

(この問題には不要ですが)これをさらに高速化することもできます。 $$f(S)$$ の寄与を考えると \[ \mathrm{ans} = \sum _ { |T| = k } \sum _ {T \subseteq S} (-1) ^ {|S|-|T|}f(S) = \sum _ {T} (-1) ^ {|S|-|T|} \binom{|S|}{k} f(S) \] となることを用いて、$$f$$ の配列から $$O(2 ^ n)$$ で直接答えを求めることができます。