tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

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!