SRM 589 Div1Hard
解法が面白かったのでメモ
問題:
1つのバイナリ列(長さ300以下)と整数Mが与えられる。
たとえばM=4のとき、
....suffix
prefix...
こういうふうに2通りで見て、suffixとprefixが同じになるようにしたい。
できる変換は、ある1箇所だけ反転させることと、先頭からk*M個まとめて全部反転させるのの2種類ある。
条件を満たすようにする最小の変換回数は?
解法:
Step 1. 文字列のパターン考察
M=2だとどうなるんだろう
..abcdefgh
ijklmnop..
まず、対応してるところは同じ。
..abcdefgh
ijabcdef..
i=a,j=b.
..abcdefgh
ababcdef..
c=a,d=b.
..ababefgh
ababcdef..
対応は同じ。
..ababefgh
abababef
a=e,b=f. 対応は同じ。
..abababgh
abababab..
g=a,h=b.
..abababab
abababab..
ということで周期2になっていればいいのか。
さらに考えるとMの値によらず周期Mであることがこの条件と同値であると分かる。
Step 2. この制約下で文字列を考えると
(M=3とする)
abcabcabcabc...みたいになっていればよい
↓ 変なかたちに書き換える
abc
abc
abc 各列ごとにすべて同じ文字が出てくればよいっぽい。かなり単純になった。
abc しかも変な操作が上からk段flipと単純になった。すばらしい。
でもぜんぜん解けそうな多項式アルゴリズムないよなぁ…?
Step 3. 計算する
さきほどの長方形を考えてみると、
面積は文字列の長さ すなわち300以下
ということは行数または列数は17以下であることがわかる。(18*18>300だから)
ということで17以下のほうを全探索すればいいのではなかろうか
行数>列数のとき(列を全探索)
各列ごとに目的のゴールが0か1かを全探索。
各行ごとにあってる個数、間違っている個数を数える。
ここで行ごとに塗りつぶしの割り当てを決める。DPをする。結構ここが複雑。
列数>行数のとき(行を全探索)
行まとめた反転の情報が全部わかっているので、個別に変えないといけない個数が簡単に求められる。
各列ごとに行反転後の0の個数1の個数を求めて、少ないほうを多いほうに変えるのが最適。
例によって行の反転状況からコストを求めるのが複雑。
以上。
// I like wolves!! import java.util.*; import java.util.regex.*; import java.text.*; import java.math.*; import java.awt.geom.*; public class FlippingBitsDiv1{ public int getmin(String[] S, int m){ String str=""; for(int i=0;i<S.length;i++)str+=S[i]; int n=str.length(); int row=n/m; int a[][]=new int[(n+m-1)/m][m]; for(int i=0;i<(row+m-1)/m;i++) for(int j=0;j<m;j++) a[i][j]=-1; for(int i=0;i<n;i++){ if(str.charAt(i)=='1')a[i/m][i%m]=1; else a[i/m][i%m]=0; } if(row<=17){ int ret=999999999; for(int i=0;i<(1<<row);i++){ int val=0; int last=0; if(i%2==1)last=1; for(int j=0;j<row;j++){ if(last==0){ if((i&(1<<j))>0) {last=1;val++;} }else{ if((i&(1<<j))==0){last=0;val++;} } } if(last==1)val++; for(int j=0;j<m;j++){ int v1=0; int v0=0; for(int k=0;k*m+j<n;k++){ if((i&(1<<k))>0){ if(a[k][j]==0)v1++; else v0++; }else{ if(a[k][j]==0)v0++; else v1++; } } val+=Math.min(v1,v0); } ret=Math.min(ret,val); } return ret; }else{ int ret=999999999; for(int i=0;i<(1<<m);i++){ int val=0; int ac[]=new int[row]; int wa[]=new int[row]; for(int j=0;j<row;j++){ //int ac=0; //int wa=0; for(int k=0;k<m;k++){ if((i&(1<<k))>0){ if(a[j][k]==1)ac[j]++; else wa[j]++; }else{ if(a[j][k]==0)ac[j]++; else wa[j]++; } } } // 最難所 int dp[][]=new int[row+1][2]; for(int j=0;j<row+1;j++) dp[j][0]=dp[j][1]=999999999; dp[0][0]=dp[0][1]=0; for(int j=0;j<row;j++){ dp[j+1][0]=Math.min(dp[j+1][0],Math.min(dp[j][0]+wa[j],dp[j][1]+ac[j]+1)); dp[j+1][1]=Math.min(dp[j+1][1],Math.min(dp[j][1]+ac[j],dp[j][0]+wa[j]+1)); } val=Math.min(dp[row][0],dp[row][1]+1); for(int j=row*m;j<n;j++){ if((i&(1<<(j-row*m)))>0){ if(a[row][j-row*m]==0)val++; }else{ if(a[row][j-row*m]==1)val++; } } ret=Math.min(ret,val); } return ret; } } } //Powered by [KawigiEdit] 2.0!