18 E Flag 2

問題

nxmマスのグリッドがあり、それぞれの色が英小文字一文字で表されている。
このグリッドを、次の条件を満たすように塗り替えたい。

• 隣り合うマスの色は異なる
• 一行に使われる色は2色以下である（列に関しては関係ない）

この時、マスを書き換える数を最小にして、塗り替えたい。
そのような数および、出来上がるグリッドを出力せよ。

制約条件

n,m≦500

方針

条件から、出来上がるグリッドは、各行最初の2マスを決めれば一意に定まることがわかる。
したがって、
dp[行][1文字目][2文字目]を、そのような状態にするような最小の書き換え回数とするDPにより解ける。
出来上がるグリッドの出力も必要なので、経路復元も行う。

これは、ナイーブに実装するとO(n*m*26^4)となりTLEなので、
各行を、最初の2マスをa,bにするようなコストをあらかじめ計算しておくことにより
計算量をO(n*26^4)に落とす必要がある。

ソースコード

int h,w; char m[500][501], am[500][501];
int dp[501][30][30], prev[501][30][30];
int cost[500][30][30];

void run(){
  cin>>h>>w;
  rep(i,h)cin>>m[i];
  
  rep(i,h){
    rep(a,26)rep(b,26){
      int c=0;
      for(int j=0;j<w;j+=2)c+=m[i][j]-'a'!=a;
      for(int j=1;j<w;j+=2)c+=m[i][j]-'a'!=b;
      cost[i][a][b]=c;
    }
  }
  
  rep(i,h+1)rep(j,30)rep(k,30)dp[i][j][k]=1e9;
  dp[0][26][26]=0;
  
  rep(i,h)rep(j,27)rep(k,27)if(dp[i][j][k]!=1e9){
    rep(a,26)rep(b,26)if(a!=b&&a!=j&&b!=k){
      int nxt=dp[i][j][k]+cost[i][a][b];
      if(dp[i+1][a][b]>nxt)dp[i+1][a][b]=nxt, prev[i+1][a][b]=j*30+k;
    }
  }
  
  int ans=1e9, ai,aj;
  rep(i,26)rep(j,26)if(ans>dp[h][i][j])ans=dp[h][i][j], ai=i, aj=j;
  for(int i=h-1;i>=0;i--){
    for(int j=0;j<w;j+=2)am[i][j]=ai+'a';
    for(int j=1;j<w;j+=2)am[i][j]=aj+'a';
    
    int bi=prev[i+1][ai][aj]/30, bj=prev[i+1][ai][aj]%30;
    ai=bi; aj=bj;
  }
  cout<<ans<<endl;
  rep(i,h)cout<<am[i]<<endl;
}