2/1 日記
ねむねむにゃんこ
PASTを進めていました
単純に親を辿ることを考えると、子が1つの頂点が連なっていた場合にO(N^2)とかになって難しいことが分かる。aとbのLCAがbであればいいので、これで解ける。
時間かかってしまって反省。
グリッドの左下をP, 右下をQ, 右上をRとし、グリッド上のある点Ｘに対し、
D(X) = PX + QX + RXを考える。D(X)の最小値が求める値であることが分かる ( XからP, Q, R への道がX以外で交わっているとすると、その点をYとしたときにXからYへの道が2つ以上存在することになり、どちらかの道を整備しなくても条件を満たすことから、最小性に反することが証明できる）。
なので、グリッド上の点Xを全探索し、この点からbfsによってD(X)を求めていけばいい。
考え中。これみたいにk=1~Mについて求めよという問題は①こないだのABC-F - Shift and Inversions (atcoder.jp)みたいに、k=1の値（または以前に求めた値）を元に順々に求めていけるやつ、➁クエリを何かでソートしていい感じになるやつ③並列二分探索
くらいをまず考えたくて、これは③ではないかと思ってる（並列二分探索とUnion-Findは相性がいい気がしている）。
でも単純にUFを使おうとすると、使わなければいけない辺が異なるためにUFをM個用意するはめになって困る。なので、辺を重みでソートして小さい順に使っていき、ok or ngの判定をするときにa と bを辺でつないで、判定が終わったら辺を切るというのでどうかと考えている。
実装する気力はないので明日かな。
おやすみなさい。
