コンテンツにスキップ

ABC484 D - Move One Card Left

サイト
AtCoder
コンテスト
ABC484
問題
D - Move One Card Left
難易度
938

長さ NN の数列 AA から要素を 11 つ取り出し、元の位置かそれより左へ挿入します。この操作をちょうど 11 回行って作れる異なる数列の個数を求める問題です(N≤2×105N\le2\times10^5)。操作で選んだ位置が違っても、結果の数列が同じなら 11 通りと数えます。

同じ結果になる操作をまとめる

Section titled “同じ結果になる操作をまとめる”

元の位置に戻す操作では数列が変わらないので、まず元の数列を 11 通りとして数えます。

位置 ii の値 a=Aia=A_i を左へ移すことを考えます(以下、位置は 0 始まり)。直前も同じ値、つまり Ai−1=aA_{i-1}=a なら、位置 ii から移す代わりに位置 i−1i-1 の aa を移しても同じ結果になります。よって、同じ値が連続する区間では先頭の位置だけを移動元として数えれば十分です。

また、挿入先の値も aa なら、その aa の直後へ挿入しても同じ結果です。これを繰り返し、挿入先が aa と異なる位置になるまで右へずらします。最後まで同じ値しかなければ、元の数列と同じなので追加で数えません。

したがって、新しく数える操作は次の条件に絞れます。

  • 移動元 ii は同じ値が連続する区間の先頭。
  • 挿入先 jj は j<ij<i かつ Aj≠AiA_j\ne A_i を満たす位置。

この条件では、操作後に元の数列と初めて異なる位置が jj、最後に異なる位置が ii です。よって、異なる (i,j)(i,j) が同じ数列を作ることはなく、重複せずに数えられます。

左から走査し、それまでに現れた値 aa の個数を c[a] に持ちます。位置 ii より前には ii 個の要素があり、そのうち aa と異なるものは

i−c[a]i-c[a]

個です。直前の値と異なるときだけ、この個数を答えに加えます。

コードでは前の値を p に保持し、p != a で連続区間の先頭かを判定しています。走査自体は O(N)O(N) 回で、使っている Counter は平衡二分探索木で個数を管理するため、計算量は O(Nlog⁡N)O(N\log N)、空間計算量は O(N)O(N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/counter.hpp"
void solve() {
LL(N);
VL(A, N);
Counter<ll> c;
ll ans = 1;
ll p = -1;
rep(i, N) {
ll a = A[i];
if (p != a) {
ans += i - c[a];
}
c.inc(a);
p = a;
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

自作ライブラリの Counter で値ごとの出現回数を管理しています。