競プロ勉強メモ

ABC214Eを経路圧縮で解く

Union-Findなどでお馴染みの、「経路圧縮」のテクニックを利用して解いた問題を紹介。

経路圧縮とは

森のグラフで、ある頂点の根を知りたいとき、初めは愚直に親を辿っていき、帰りがけに各頂点の辺を直接その根に繋げなおすことでそれ以降の探索を高速化する手法。

何を言ってるんだ？って方は下記サイトに書かれた図を参照してみてください。

経路圧縮 | アルゴリズムビジュアル大事典

これを行うとUnion-Find中に $amortized \ O(\log N)$ で根を見つけられるんだそう。なんでかはわからん…（勉強しろ）

解いた問題：ABC214-E問題

問題概要

$T$ 個のテストケースが与えられる。各テストケースは以下の通り：

1列に並んだ $10^9$ 個の箱と $N$ 個のボールがある。以下の条件を満たすように全てのボールを箱に入れられるか判定せよ。

1個の箱に入れるボールは高々1個。
ボール $i$ は閉区間 $[L_i, R_i]$ 内の箱に入れる。

制約

$1 \le T \le 2\times 2\times 10^5$
$1 \le N \le 2\times 10^5$
$1 \le L_i \le R_i \le 10^9$
$(各テストケースでのNの合計) \le 2 \times 10^5$

考えたこと

区間スケジューリング問題 | アルゴ式

のような見た目をしている。こういうときは右端でソートするのが定番。（要出典）

具体的には、ボールをRについて昇順ソートして、その順に「入れられる最も左の箱」に貪欲に入れていけばよさそう。

右端でソート+貪欲

では、入れられる最も左の箱はどのように求めればいいだろう？

単純な方法としては、

箱Lを見る　→　埋まっていたら箱L+1を見る　→　埋まっていたら箱L+2を見る　→…

とLから順に試していくというもの。しかしこれは例えば以下のようなケースで $O(N^2)$ となりTLE。

200000

1 10000000

1 10000000

1 10000000

...

ボール1つあたり箱を探すのに $O(N)$ かかる。

O(N) — ボール1つあたり箱を探すのに $O(N)$ かかる。

これを経路圧縮で解決する。

解法

ボールをRについて昇順にソート
箱を頂点としたグラフを考える。初めは辺がなく、箱 $i$ にボールを入れるときに頂点 $i$ から $i+1$ に辺を張る。ボール $i$ は、頂点 $L_i$ から辺を辿れるだけ辿り、行き先のなくなったときその箱に入れる。この際、経路圧縮を並行して行う。
2.で入れた箱が $R_i$ より大きければ"No"。そうならず無事に全てのボールを入れられたら"Yes"。

実装の際は、グラフはそのまま持たず、連想配列を使って登場した頂点だけ記録する。

ACコード

Python（3.8.2）（655ms）

再帰関数で実装しているので、PyPy3だと遅い。（900msちょっと）

PyPy3（7.3.0）（644ms）

スタックdfsで書きなおしたコード。iをスタックに追加する前に~i（iのbit反転）を追加することで帰りがけの処理を実現している。

もっと速い実装がありそうな気もする…（実装力の欠如）

経路圧縮で解ける類題