ABC484 D - Move One Card Left
- サイト
- AtCoder
- コンテスト
- ABC484
- 問題
- D - Move One Card Left
- 難易度
- 938
長さ の数列 から要素を つ取り出し、元の位置かそれより左へ挿入します。この操作をちょうど 回行って作れる異なる数列の個数を求める問題です()。操作で選んだ位置が違っても、結果の数列が同じなら 通りと数えます。
同じ結果になる操作をまとめる
Section titled “同じ結果になる操作をまとめる”元の位置に戻す操作では数列が変わらないので、まず元の数列を 通りとして数えます。
位置 の値 を左へ移すことを考えます(以下、位置は 0 始まり)。直前も同じ値、つまり なら、位置 から移す代わりに位置 の を移しても同じ結果になります。よって、同じ値が連続する区間では先頭の位置だけを移動元として数えれば十分です。
また、挿入先の値も なら、その の直後へ挿入しても同じ結果です。これを繰り返し、挿入先が と異なる位置になるまで右へずらします。最後まで同じ値しかなければ、元の数列と同じなので追加で数えません。
したがって、新しく数える操作は次の条件に絞れます。
- 移動元 は同じ値が連続する区間の先頭。
- 挿入先 は かつ を満たす位置。
この条件では、操作後に元の数列と初めて異なる位置が 、最後に異なる位置が です。よって、異なる が同じ数列を作ることはなく、重複せずに数えられます。
挿入先の個数を数える
Section titled “挿入先の個数を数える”左から走査し、それまでに現れた値 の個数を c[a] に持ちます。位置 より前には 個の要素があり、そのうち と異なるものは
個です。直前の値と異なるときだけ、この個数を答えに加えます。
コードでは前の値を p に保持し、p != a で連続区間の先頭かを判定しています。走査自体は 回で、使っている Counter は平衡二分探索木で個数を管理するため、計算量は 、空間計算量は です。
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 で値ごとの出現回数を管理しています。