AtCoder Grand Contest 001 - F (Wide Swap)

2016-07-17 | [Competitive programming]

コンテスト中には解けなかったけど後で解いてみた．感動した．すぬけは天才．

概要

解法

(位置 -> 値) の列で並び替えを行うかわりに，(値 -> 位置) の列で並び替えを行うことを考える．つまり，Q[P[i]] := i として作った列 Q を考える． P での入れ替え操作の条件は，Q においては「列上隣り合っていて，値の差の絶対値が K 以上」と言い換えられる．また，「P で辞書順最小」という要求は，Q においては「1 をできるだけ左に持ってきて，その条件のもと 2 をできるだけ左に持ってきて，…」になる．以後，基本的に Q だけを考える．

入れ替え操作の条件は，言い換えると「値の差の絶対値が K 未満な 2 つの数は，その位置関係を決して入れ替えることはできない」とできる．逆に，この制限を守っている限りはどのような列にでもできる．（証明略）すると，「必ず a は b の右にある」とき「a -> b の辺を持つ」ようなグラフを考えた時，得られる Q はそのグラフにおけるあるトポロジカルソートの結果になる．

ここで実際に解を構成することを考える．まず 1 をできるだけ左に持っていくのだが，グラフ上 1 から到達できる値たちは 1 より左にないといけないため，これにより 1 の位置が制限される．逆に，そのような値しか 1 の左にはないようにできるため，最も左という条件からそのような列を構成する必要が生じる．これで 1 の位置は決まり，その左と右に置かれる値の集合も決まる．問題はその集合の中での並べ方であるが，今度は「各集合の中で，最小のものをできるだけ左にし，そのもとで 2 番目に小さいものをできるだけ左にし，…」というように並べればよいことがわかる．

これを単純に実装すると計算量が大きすぎるため，高速化の必要がある．「1 を左に寄せる」操作を考えるとき，「1 から到達できる値の中で最小」のものは，Q 上 1 の左にある値最小のものであることが確かめられる．なので，1 を置くときには「とりあえずその最小のものをできるだけ左に寄せる」とすればよい．それを行った後でも 1 が置けるとは限らないが，今度は「まだ置いてないものの中で，1 の左にあって最小のものを選んで左に寄せる」とすればよい．これを，もはや 1 を左に寄せるのを阻害するものがなくなるまで繰り返し，1 を置く位置を決定する．

この操作は再帰的に行うことができる．ここで，最初は値が 1 (最小の値) だったからよいが，より大きい値の場合は「自分より左に，より小さい値がある」懸念がありそうに見える．しかし，実際には再帰の際に「現在，自分より左に残っている最小のもの」を選んでいるので，そのようなことは起きない．よって，この方法で破綻せずに， 1 をできるだけ左に寄せつつ，1 の左にあるものについても最適な列を構成できることがわかる．他の値についても，小さい方から順に，「まだ置いていないなら，その値について，上に述べたことを行う」をやるとよい．

「まだ置いてないものの中で，自分より左にあって最小のもの」を見つける操作は Segment Tree を使う（値を置いた際には Segment Tree の対応する位置の値を inf に差し替える）ことで効率よく行える．また，「まだ，この値を左に寄せるのを阻む値はあるのか？」を判定するのも，自分より左にある値の中で最小のものを求め，それと自分との差の絶対値が K 未満かを見れば行える．

このアルゴリズムは O(N log N) で動作するため，制限時間内に問題を解くことができる．

コード

ここにあります．本質 (decide 関数) たった 10 行．

上の解法で「再帰的に行う」と書いたものが decide 関数です． seg がだいたい Q になっています． decide 関数は「P での位置」すなわち「Q での値」 idxを受け取り，seg を通じて「Q において，idx がある場所より左にあるもののうち，まだ使っていない最小のもの」を探し，それが idx を左に寄せる邪魔になっているなら再帰的にそれについて左寄せ処理を行っています．