[ARC136] B - Triple Shift

[Q] https://atcoder.jp/contests/arc136/tasks/arc136_b

屈辱のバブルソートした。O(N^2)で通す。

考察する。
1. shiftしまくったら、最後の2要素だけ差分が出るはず。
たとえば
5 1 2 4 3
を昇順shiftすれば、
1 2 3 4 5 か 1 2 3 5 4のどちらかになるだろう、と思う。

2. A[]とB[]の互換の積をそれぞれとったときに、偶奇が一緒かどうかを見ればいいんだ、と思う。

Q. さて、なんの偶奇？
A. わ か ら な い ！
全然法則が見つからず1時間が経過する。
解説によると転倒数のようだ。調べた気がしたんだけど・・・。きっとなんか勘違い。

3. N=5000なので、O(N^2)がいける。
昇順Shiftをできる＝バブルソートしちゃえばいいと思って、甘んじて実装した。
Q. バブルソート？
1. 末端から3要素ずつ見ていく。
2. 見ている3要素のうち、最小値が一番左側にくるまで、Shift操作をする。
3.これを、index N-1 ~ 2まで操作をN-2回繰り返す。

Q. 
5 1 2 4 3
をsortする。

1週目。
1. index 2,3,4
5 1 2 4 3
    ~~~~~ 最小値2が左に来ているのでこのまま
2. index 1,2,3
5 1 2 4 3
  ~~~~~ 最小値1が左に来ているのでこのまま

3. index 0,1,2
5 1 2 4 3
~~~~~ 最小値1が左じゃないのでShift
1 2 5 4 3 になる。

1 週目は 1 までがソートされていることが保証される。

2週目。
1. index 2,3,4
1 2 5 4 3
    ~~~~~ 最小値3が左じゃないのでShift
1 2 3 5 4 になる
2. index 1,2,3
1 2 3 5 4
  ~~~~~ 最小値2が左に来ているのでこのまま

3. index 0,1,2
1 2 3 5 4
~~~~~ 最小値1が左なのでこのまま


2 週目は 2 までがソート済みであることが保証される。

3 週目
1 2 3 5 4
になる。
3 週目は 3 までがソート済みであることが保証される。

4 5 はいじれないので、
1 2 3 5 4
が最終系のようだ。

実装

vector<ll> G[5010];
vector<ll> H[5010];
ll N;

void do_shift(vector<ll> &A) {
 rep(i, N - 2) {                      // N-2回繰り返す
   for (ll j = N - 1; j >= 2; --j) {  // 末端から3要素をshiftする
     ll low = oo;                     // 2e18
     // 3要素の最小値を入れる
     rep(k, 3) { chmin(low, A[j - k]); }
     while (A[j - 2] != low) {  // 一番左が最小値じゃないならshift
       // 1 2 3 を
       // 2 3 1 にするには、swap(1,2) swap(2,3)
       swap(A[j - 2], A[j - 1]);
       swap(A[j - 1], A[j]);
     }
   }
 }
}

int main() {
 cincout();

 cin >> N;
 vector<ll> A(N), B(N);

 // 入力
 rep(i, N) {
   ll a;
   cin >> a;
   A[i] = a;
   // 値ごとに個数を管理。前提チェックに使う
   G[a].push_back(i);
 }
 rep(i, N) {
   ll b;
   cin >> b;
   B[i] = b;
   // 値ごとに個数を管理。前提チェックに使う
   H[b].push_back(i);
 }
 
 bool dup = false;
 rep(i, 5001) {
   // 数字の構成要素AとBで違うならNo
   if (G[i].size() != H[i].size()) {
     cout << "No" << endl;
     return 0;
   }
   // 重複した数があるなら、絶対並び替えられる
   if (G[i].size() > 1) dup = true;
 }
 // 構成要素が同じで、何か同じ数字があるなら順番を入れ替えられるからYes
 if (dup){
   cout << "Yes" << endl;
   return 0;
 }
 // 昇順にしちゃう
 do_shift(A);
 do_shift(B);
 // 最後の要素だけ逆転していないか確認。
 if (A[N-1] != B[N-1]){
   cout << "No" << endl;
 } else {
   cout << "Yes" << endl;
 }
}

https://atcoder.jp/contests/arc136/submissions/29760964