AGC 001 F Wide Swap

まず転置をします。

すると、数列が与えられます。隣あう要素の差がK以上ならswap出来ます。転置した時に辞書順最小になるようにしてください。となる。この数列をa_iとします。

ここで、abs(a_i - a_j) < kならこの2つの位置関係がひっくり返ることはない。逆に考えると、この関係を満たすペアすべての間に有向辺を貼ると、このグラフでのトポロジカル順を考えれば良いことがわかる。

実は、後ろから考える(Nから確定させていく)と非常に見通しが良くなり、priority_queueを使用すればO(N² logN)で解ける。

辺の貼り方を考えると、a_iについて、"a_iより左側で、値が(a_i - k, a_i + k)の中にあるもの"全てについて辺を貼れば良い。

だが、実はO(N²)本も辺を貼る必要はない。a_iについて、"a_iより左側で、値が(a_i - k, a_i)であるもののうち最も右側"と"a_iより左側で、値が(a_i, a_i + k)であるもののうち最も右側"の高々2つにのみ辺を貼れば十分。これでO(N)本になる。