[AGC055] A - ABC Identity

[Q] https://atcoder.jp/contests/agc055/tasks/agc055_a

1. 範囲を3等分。この範囲内で塊をとることだけ考える。
2. 範囲内に、ABCがそれぞれ何個ずつあるか調べる。
3. ABCの組み合わせ6通りを探索して、一番効果的な組み合わせを選ぶ。
4. 2~3を6回やれば、必ず求まる。

Q 例2
4
AABCBCAACBCB

1. Nで3等分する。
AABC BCAA CBCB

2. それぞれの範囲において、ABC は何個ずつ？
A: 2 2 0
B: 1 1 2
C: 1 1 2

3. ABCの効果的な分配を考える。
ABC = min{2 1 2} = 1個ずつとれる
ACB = min{2 1 2} = 1
BAC = min{1 2 2} = 1
BCA = min{1 1 0} = 0
CAB = min{1 2 2} = 1
CBA = min{1 1 0} = 0

ABCを採用。

4. ABC を 1 個ずつ分ける。

  S:AABC BCAA CBCB
ans:1000 1000 1000

2. 何個ずつ残ってるか再調査。
A: 1 2 0
B: 1 0 2
C: 1 1 1

3. 
ABC = min{1 0 1} = 0
ACB = min{1 1 2} = 1
...

4. ACB を 1 個ずつとる。

  S:AABC BCAA CBCB
ans:1200 1200 1200


A. 123412341234

実装

ll DP[600010];
ll ans[600010];

ll part[3][3];
ll N;
string S;

void init_part(){
 rep(i, 3) rep(j, 3) part[i][j]=0;
 rep(i, 3){
   rep(j, N){
     ll now = i*N+j;
     if (ans[now]>0) continue;
     ++part[i][S[now]-'A'];
   }
 } 
}

void init_ans(vector<ll> &V, ll turn, ll cnts){
 rep(i, 3){
   ll c=cnts;
   rep(j, N){
     if(c==0) break;
     ll now=i*N+j;
     if (ans[now]>0) continue;
     ll n=S[now]-'A';
     if (n==V[i]){
       ans[now] = turn;
       --c;
     }
   }
 }
}

int main(){
 cincout();
 
 cin >> N >> S;
 
 rep(i, 6){
   init_part();
   vector<ll> V={0, 1, 2};
   vector<ll> U;
   ll cnts=0;
   do{
     ll cand=oo;
     chmin(cand, part[0][V[0]]);
     chmin(cand, part[1][V[1]]);
     chmin(cand, part[2][V[2]]);
     if (chmax(cnts, cand)) U=V;
   }while(next_permutation(all(V)));
   
   // Uが候補の取り方
   if (U.empty()) break;
   init_ans(U, i+1, cnts);
 }
 rep(i, N*3) cout << ans[i];
 cout << endl;
}

Q. RE?
A. 配列の大きさは、200000*3 = 600000までとりうる(1敗)

https://atcoder.jp/contests/agc055/submissions/26958226