SRM 663 div2

Easy

問題文

N × Nのボードにそれぞれ英小文字が書いてある.
ある英小文字を好きな英小文字に書き換えることができる.

ボードをチェック模様(ある文字を見たとき、上下左右に隣接する文字が全て異なり、ボードを2つの文字で表現することができる)
にするためには、最小で何回書き換える必要があるか.

制約

• 2 ≤ N ≤ 20

解法

全探索.
ボード上のマスを(x,y)とすると、(x+y)が奇数になるマスと(x+y)が偶数になるマスに異なる文字を割り当てることがわかる.
その割り当てる文字を全通り試す. ただし、同じ文字を割り当ててはならない.

コード

class ChessFloor {
public:
    int minimumChanges(vector<string> floor) {
	int res = 114514;
	int N = floor.size();
	for(char a = 'a' ; a <= 'z' ; a++){
	    for(char b = 'a' ; b <= 'z' ; b++){
		if(a == b) continue;
		int cnt = 0;
		for(int i = 0 ; i < N ; i++){
		    for(int j = 0 ; j < N ; j++){
			if((i+j)%2 == 0){
			    if(a != floor[i][j]){
				cnt++;
			    }
			}else{
			    if(b != floor[i][j]){
				cnt++;
			    }
			}
		    }
		}
		res = min(res,cnt);
	    }
	}
	return res;
    }
}

Med

問題文

スタートの文字列initialとゴールの文字列targetが与えられる.
この文字列は'A'と'B'で構成されている.

以下の2つの操作ができる.

• 文字列の末尾に'A'という文字を連結する.
• 文字列を反転し、末尾に'B'という文字を連結する.

この操作を任意の回数行い、initialからtargetにすることが可能かどうか.

制約

• 1 ≤ |initial| ≤ 999
• 2 ≤ |target| ≤ 1000
• |initial| < |target|

解法

区間DP.

dp[左の区間][右の区間][文字列が逆順かどうか] := 可能かどうか.
targetの状態から、initialの状態へと遷移させる.

余談

実は、targetの状態から、initialの状態へと遷移させるのであれば、
遷移が一意に定まるのでシミュレーションするだけになる.

明らかにこれに気づかないのはヤバいよなぁ…
まぁ区間DPの練習になったしいいか.

コード

int dp[1010][1010][2];

class ABBA {
public:
    int len;
    bool check(int L,int R,int d,string &a,string &b){
	if(d == 0){
	    for(int i = L ; i <= R ; i++){
		if(a[i-L] != b[i]) return false;
	    }
	}else{	    
	    for(int i = R ; i >= L ; i--){
		if(a[R-i] != b[i]) return false;
	    }
	}
	return true;
    }
    
    int solve(int L,int R,int d,string &a,string &b){
	if(R-L+1 == len){
	    return (check(L,R,d,a,b) ? 1 : 2);
	}
	int &res = dp[L][R][d];
	if(res > 0) return res;
	res = 2;
	if(d == 0){
	    if(b[R] == 'A') res = min(res,solve(L,R-1,d,a,b));
	    if(b[R] == 'B') res = min(res,solve(L,R-1,1-d,a,b));
	}else{
	    if(b[L] == 'A') res = min(res,solve(L+1,R,d,a,b));
	    if(b[L] == 'B') res = min(res,solve(L+1,R,1-d,a,b));
	}
	return res;
    }

    string canObtain(string initial, string target) {
	int L = 0,R = target.size()-1;
	memset(dp,0,sizeof(dp));
	len = initial.size();
	return (solve(L,R,0,initial,target) == 1 ?
		"Possible" : "Impossible");
    }
}