最終更新: 2021-03-12T19:59+0900
まだ AC してない。(←その後 AC)
前回の日記(20200905p01)で解いた問題と構造は同じ。一番大きな違いはグリッドの大きさで、こちらは制約上の上限が 200000×200000 だから１マスずつの処理では間に合わない。
そこは何とかなって今は上限20万回のループの中で、上限20万要素からの二分探索が２回と、上限20万要素からの最小値検索を１回行っている。配列からの最小値検索が線形時間なのが明らかにまずいんだよなあ。実はループの中で配列のスプライシングをやってるのもまずくて、まずいのが２つ組み合わさって手がつけられないんだなあ。
問題のイメージが掴めてきた(今です)。H 枚の板が上から順にやや右下がりで設置されていて、最上段では横一列に並んだ W 個の蛇口から水が流れている。k 段目で注目すべきは水が落下している位置(複数)と、そこに流れ込む水流のうち落下点に最も近い蛇口がどれか。蛇口と落下点を結ぶ線はどれも交わらない。
蛇口と落下点の距離が最小となるものを効率的に見つけるデータ構造がわからんのだよなあ。
あ、TLE が２つ減ったのは nmin, rmin の導入効果。「蛇口と落下点の距離」ごとに数を数えておいて、数がゼロではない距離を小さい順に検索する。距離は増加する一方だから検索範囲は狭まっていく。
今回のポイントは r を可変長から固定長にしたこと。可変長のときの r のサイズは W から減っていく一方だったのだけど、固定長だと最初から最後まで W(+1)。それでどうして速くなるのか。
r の中身について。これまでは落下点と落下点までの横移動コストを記録していた。今回は落下点は(固定長)配列の添字となり、配列の中身に蛇口の位置を記録した。落下点までの移動コストは計算で求まる。
ここでトリック。落下点と蛇口の位置関係は「蛇口<=落下点」で決まってるので、「添字<中身」の場合を、落下点を見落とさずに配列のスキャンを安全にスキップするための情報とした。
Ruby で提出してると AtCoder Problems で確認できる Shortest Code の数がいつの間にか増えている現象がある。この提出が(いまのところ)そうだし、巨大企業(20200607p01)もそう。
AC 一番乗りである。C++ は甘え。まあ、Python は普通に AC がいくつもあるんだけど>「Python によるすべての提出」
見事なまでに変わらず。スキップ情報を UnionFind と同じように深さ優先探索で貪欲に求めて書き込むようにしても、やっぱり変わらないだろうなと思ってる。