[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;
}
}