コンテンツにスキップ

ABC484 C - Move One Card

サイト
AtCoder
コンテスト
ABC484
問題
C - Move One Card
難易度
480

長さ NN の数列 A,BA,B が与えられます。AA から要素を 11 つ取り出し、好きな位置に挿入する操作をちょうど 11 回行って、BB にできるか判定する問題です(N≤2×105N\le2\times10^5)。元の位置に戻しても構いません。

右の要素を左へ移す場合を調べる

Section titled “右の要素を左へ移す場合を調べる”

まず、AA のある要素を左へ移して BB にできるかを判定します。左から比較し、最初に一致しない位置を ll とします。この位置では、右のどこかから持ってきた値 BlB_l を挿入する必要があります。

挿入した値を f=Blf=B_l とし、その後は BiB_i と Ai−1A_{i-1} を比較します。挿入によって、間にあった要素が 11 つずつ右へずれるためです。

ずらした比較が初めて一致しなくなる位置を ii とすると、ここで元の位置から ff を取り出したと考えます。そのためには

Ai−1=f,Ai=BiA_{i-1}=f,\qquad A_i=B_i

が必要です。この条件を満たせば、以降は再び AiA_i と BiB_i を比較します。その後に不一致があれば、11 回の移動では作れません。

途中で元の比較に戻せないまま末尾まで一致した場合は、末尾の要素を取り出したと考えます。この場合は AN=fA_N=f なら成功です。

同じ値が続くと、実際に取り出す位置より後までずらした比較が一致することがあります。しかし、その間は移す値 ff と同じ値が続いているので、取り出す位置を後ろへずらしても結果は変わりません。よって、最初の不一致まで比較を続けて構いません。

左の要素を右へ移す操作の逆操作は、右の要素を左へ移す操作です。したがって、AA と BB を交換して同じ判定を行えば、右へ移す場合も調べられます。

もともと A=BA=B の場合も、取り出した要素を同じ位置に戻せるので Yes です。22 回の走査のどちらかが成功すれば Yes、両方失敗したら No を出力します。計算量は O(N)O(N) です。

コードの t は比較位置のずれ(00 または −1-1)、f は移す値、c は「挿入前」「挿入後・取り出し前」「取り出し後」の段階を表しています。

C++
#include "shogo-library/base/all"
void solve() {
LL(N);
VL(A, N);
VL(B, N);
rep(2) {
ll t = 0, c = 0, f = -1, ok = 1;
rep(i, N) {
if (A[i + t] == B[i])
continue;
if (c == 0) {
t = -1;
f = B[i];
c++;
} else if (c == 1) {
if (f != A[i + t]) {
ok = 0;
break;
} else if (A[i] != B[i]) {
ok = 0;
break;
} else {
f = -1;
t = 0;
c++;
}
} else {
ok = 0;
break;
}
}
if (c == 1) {
if (f != A.back()) {
ok = 0;
}
}
if (ok) {
print("Yes");
return;
}
std::swap(A, B);
}
print("No");
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}