B - Do Not Duplicate

[Q] https://atcoder.jp/contests/agc036/tasks/agc036_b

とても苦労した。ダブリングで解くことを考える。
1. 長さNの数列だけど、2つくっつけて、2N数列として扱う。
2. データ管理は、
DP[2^41][400010] = 次の2N要素のうち、どのindexまで飛ぶか。
3. ダブリングで(K^1)/2周を高速処理したら、最後の2N数列だけちゃんと調べる。

Q.
1 1 1 2

1. N の数列を 2N 数列として扱う
1 1 1 2 1 1 1 2
で1つとする。

2. doubling にあてはめる。
・DP[0][0] を求める。
A[0] = 1 からスタートした場合、次の 11121112 数列のどこまでスキップするかを知りたい。

 id: 0 1 2 3 4 5 6 7   0 1 2 3 4 5 6 7
A[]:<1>1 1 2 1 1 1 2 / 1 1 1 2 1 1 1 2
     --- ----- --- ----------- | ここ

DP[0][0] = 4 が求まる。

・DP[0][1] を求める。
 id: 0 1 2 3 4 5 6 7   0 1 2 3 4 5 6 7
A[]: 1<1>1 2 1 1 1 2 / 1 1 1 2 1 1 1 2
       --- ---------   | ここ

DP[0][1] = 0 が求まる。

Q. 全部探索すると多分間に合わない？
A.
・もういちどDP[0][0]を考える。

 id: 0 1 2 3 4 5 6 7   0 1 2 3 4 5 6 7
A[]: 1 1 1 2 1 1 1 2 / 1 1 1 2 1 1 1 2
     --- ----- --- ----------- | ここ
     |=> DP[0][0] = DP[0][2] と同じ値になるのがわかる。
         |=> DP[0][2] = DP[0][5] と同じ
               |=> DP[0][5] = DP[0][7] と同じ
                               |=> DP[0][7] = 4

よって、
DP[0][0] = DP[0][2] = DP[0][5] = DP[0][7] = 4
と定まる。
最初にDP[0][7] = 4を求めておきたいので、DP[0][2*N-1] ~ DP[0][0]の順番に探索。

DP[0][0] = 4
DP[0][1] = 0
DP[0][2] = 4
DP[0][3] = 0
DP[0][4] = 1
DP[0][5] = 4
DP[0][6] = 1
DP[0][7] = 4 

doubling は、DP[0] さえ求まったらテンプレートでDP[40]まで入れられる。
DP[1][0] = DP[0][ DP[0][0] ]
DP[2][0] = DP[1][ DP[1][0] ]
...
DP[40][0] = DP[39][ DP[39][0] ]

3. ダブリングで(K^1)/2周を高速処理したら、最後の 2N 数列だけちゃんと調べる。
bool used[200010]{} を用意。
・used[A] == false なら、Aをキープして used[A] = true
・used[A] == true なら、used[A] = false になるまで、キープから除き続ければいい。

残りカスが答え。

Q. なんで2N数列として扱うの？

A. 
大変おバグしたのが、

1 1 1 2

の場合。
DP[1][0] = 0 になってしまう。
DP[1]は、2^1 = 2週目から3週目への遷移を表す状態。
1 1 1 2 / 1 1 1 2 / 1 1 1 2 / 1
--- ------  --- -----------   |=> ここ。これ4週目

3週目ではなく、4週目の遷移をとってしまっている。

これは、A[3] = 2 が、奇数週目と偶数週目で、ペアの在り方が違うから。
区別するために、2N 数列として扱った。

実装

ll DP[42][400010];  // DP[2^j日後][i番目の町から]=到達する町
ll N, K;
ll NN;
ll pos[200010]; // 前回の処理id

vector<ll> G[200010];

void debug() {
 rep(i, 41) {
   rep(j, NN) cout << DP[i][j] << " ";
   cout << endl;
 }
}

int main() {
 cincout();

 cin >> N >> K;
 NN = N*2;
 vector<ll> A(NN);
 rep(i, N){
   ll a;
   cin >> a;
   A[i] = a;
   G[a].push_back(i);
 }
 // 2週目
 rep(i, N){
   ll a = A[i];
   A[i+N] = a;
   G[a].push_back(i+N);
 }
 
 // doubling
 for(ll i=NN-1; i>=0; --i){
   ll a = A[i];
   // pos==0なら、begin+1をとる
   // begin+1==Nなら0
   // pos!=0なら、pos+1をとる。
   // pos+1==Nなら、0をとる。
   if (pos[a] == 0){
     ll nx = (*G[a].begin())+1;
     nx %= NN;
     DP[0][i] = nx; // ペア+1にとぶ
   }
   else{
     ll nx = pos[a]+1; //1個次にとぶ
     nx %= NN;
     DP[0][i] = DP[0][nx];
   }
   pos[a] = i;
 }
 rep(k, 41) {
   rep(i, NN){
     ll nx = DP[k][DP[k][i]];
     DP[k + 1][i] = nx;
   }
 }
 
 ll k=(K-1)/2;
 ll now = 0;
 for(ll i=41; i>=0; --i){
   if (k >= (1LL<<i)){
     k -= (1LL<<i);
     now = DP[i][now];
   }
 }
 
 // K=5なら、2週回して頭からNまで
 // K=6なら、2週回して頭からNNまで
 
 deque<ll> ans;
 bool seen[200010]{};
 ll tail = N;
 if (K%2==0) tail = NN;
 for(ll i=now; i<tail; ++i){
   ll a = A[i];
   if (seen[a]){
     while(seen[a]){
       seen[ans.back()] = false;
       ans.pop_back();
     }
   }
   else{
     ans.push_back(a);
     seen[a] = true;
   }
 }

 while (!ans.empty()){
   cout << ans.front(); ans.pop_front();
   if (!ans.empty()) cout << " ";
 }
 cout << endl;

//  cout << "now:" << now << endl;
// debug();

}

Submission #26990750 - AtCoder Grand Contest 036