joi春合宿2015 day1-2:En-JOI-able Logo Design

問題文

http://www.ioi-jp.org/camp/2015/2015-sp-tasks/2015-sp-d1.pdf

解法

円環の問題なので引き伸ばして2*Nの列にして、適当に累積和取ったら通った。

コード

#include<bits/stdc++.h>
using namespace std;

int K,N;
char str[1<<21];
int S[1<<21];
int sum[3][1<<23];
int main(){
    scanf("%d%s",&K,str);
    int N=1<<(2*K);

    for(int i=0;i<N;i++){
        switch(str[i]){
            case 'J':S[i]=0;break;
            case 'O':S[i]=1;break;
            case 'I':S[i]=2;break;
        }
    }

    for(int i=0;i<N;i++){
        sum[S[i]][i+1]++;
        sum[S[i]][N+i+1]++;
    }

    for(int k=0;k<3;k++){
        for(int i=0;i<2*N;i++){
            sum[k][i+1]+=sum[k][i];
        }
    }

    int mi=1001001001;

    for(int i=0;i<N;i++){
        int prev=i;
        int cost=0;
        for(int j=K-1;j>=0;j--){
            for(int k=0;k<3;k++){
                cost+=(1<<(2*j))-(sum[k][prev+(1<<(2*j))]-sum[k][prev]);
                prev+=(1<<(2*j));
            }
        }
        mi=min(mi,cost);
    }

    printf("%d\n",mi);
    return 0;
}