はじめに
駆け出し茶コーダーです。初投稿。ARC120に出場して、解けなかった問題の復習をしていたが、ちょうど良い解説記事が見つからなかったので自分で解説する。
問題のリンク ARC120 C-Swaps2
[C++での解答]
(https://atcoder.jp/contests/arc120/submissions/22952457)
[Pythonでの解答]
(https://atcoder.jp/contests/arc120/submissions/22957759)
#問題を簡単に言い換える1
このまま考えるのは難しいから、問題を簡略化していこう。
本問題では1つ後ろにずれた数字は1が減算され、1つ前にずれた数字は1が加算される。この加減算処理は複雑でイヤだなぁということで、数列の中身をA1を基準として変換していく。
例えば数列A=[3,1,4]のときは下図のように処理する。
この操作だけでは本来一致すべき数列B=[3,1,4]であっても一致しない。ゆえに、数列Bにも同様の操作をする。
数列B=[6,2,0]のときは下図のような処理をする。
変換後の数列Aと数列Bを見比べると、要素を並び替えたら一致することがわかる。逆に変換後の配列の要素が一致しなかったらどのように並び替えても数列は一致しない。
よってこの問題は、変換後の数列Aを最小何回の入れ替えで変換後の数列Bに一致させられるかという問題に置き換えられる。
#問題を簡単に言い換える2
配列に入っている数字は大小バラバラでこのままでは扱いづらい。昇順に並び替えるなら楽じゃね？ということでさらに数列を変換する。
数列Bは1から始まる順列にして数列Aはそれに対応した数字を入れる。
これで数列[2,3,1]を数列[1,2,3]に並び替える問題になった。つまり昇順に並び替えるというわけだ。これで下準備は完了。
#並び替え問題を解く
さて、いよいよ本題。
数列A[2,3,1]は最小何回の入れ替えで昇順になるか。
昇順は自分より小さい数が自分より後にあったらダメだから、数列Aのi番目の要素をAiとすると、Aiより後ろにあるAiより小さい数字を全て前に持ってこないといけない。
ゆえにAiより後ろにあるAiより小さい数の合計が入れ替える最小の数になる。
#標準入力の読み込み
コードに落とし込んでいく。まずは標準入力を読み込む。
int N;
cin >> N;
vector<int>A(N);
vector<int>B(N);
for (int i=0; i<N; i++) cin >> A.at(i);
for (int i=0; i<N; i++) cin >> B.at(i);
#問題を簡単に言い換える1(加減算処理)
i番目の要素にiを足す。
for (int i=0; i<N; i++) A.at(i) += i;
for (int i=0; i<N; i++) B.at(i) += i;
#問題を簡単に言い換える2(数列Bを昇順に置き換え)
数列Aと数列Bの要素が一致しているかを調べ、数列Bを昇順に置き換えそれに対応するAを作るのにmapを使う(Pythonでいうdict)。
数列Bに同じ大きさの要素があった時順番を入れ替えられてしまうとWAなのでqueueを組み合わせる。
例えば数列A=[2,2,1]で数列B=[2,1,2]のとき数列B=[1,2,3]に変換する際数列Aは[1,3,2]と[3,1,2]の両方に変換できるが、前者は並び替えが1回、後者は2回なので、前者でないとWAである。
つまり、変換後の数列Aは変換前の要素が同じときは昇順で数字を対応させていけばよい。このときqueueの出番である。
まず変換前の数列Bの要素をキーとしたqueueに変換後の数列Bの要素を入れる。
次に変換前の数列Aの要素をキーとしたqueueにアクセスして先頭の要素を取り出して変換後の数列Aの要素とする。これで数列Aの変換完了。
map<int,queue<int>> q;
for(int i=0;i<N;i++) q[B.at(i)].push(i+1);
for(int i=0;i<N;i++){
if(q[A.at(i)].empty()){ //Aの要素がBになかった時
cout<< -1 <<endl;
return 0;
}
int a=q[A.at(i)].front();
q[A.at(i)].pop();
A.at(i)=a;
}
#並び替え問題を解く(コード)
Binary Indexed Tree (BIT)を使って解く。BITってなんぞやって人はググれば出てきます。
BIT配列を作り、数列Aの後ろから要素を一つずつ取り出し(取り出した要素をiとする)、BITの場所iの値を1増やし、0からiまでの区間和をansに加算することを繰り返す。
数列A=[1,3,2]を例に取り上げる。
long long ans=0;
vector<int>BIT(N+1,0);
for(int i=N-1;i>=0;i--){
for(int j=A.at(i);j>0;j-=(j&-j)) ans+=BIT.at(j);
for(int j=A.at(i);j<=N;j+=(j&-j)) BIT.at(j)++;
}
水diff難しい、、、
#参考
公式解説