DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選 : D - 石

グダグダでぴったり100位(ただし２名同着)。
https://beta.atcoder.jp/contests/ddcc2017-qual/tasks/ddcc2017_qual_d

問題

H*Wのグリッドがある。(H,Wは偶数)
一部のマスには石が置かれている。
石を1つずつ任意の順番で取り除くことを考える。

取り除いた後のグリッドの状態が上下対称ならA,左右対称ならBの得点を得る。
得られる総得点の最大値を求めよ。

解法

S(r,c)=1ならマス(r,c)に石が置かれているとする。
S(r,c), S(H-1-r,c), S(r,W-1-c), S(H-1-r,W-1-c)がすべて一致する場合、それらは左右対称かつ上下対称である。

まず、それ以外の石を処理してしまおう。
一旦左右対称にしてしまえば、以後はできるだけ左右対称を維持するように石を取り除けば２手ごとにB点が得られる。
逆に先に上下対称にしてしまえば、以後はできるだけ上下対称を維持するように石を取り除けば２手ごとにA点が得られる。

よって先に左右対称にしてから上下対称にするケースと、その逆のケースを両方ためし、得られる得点が多い方を採用しよう。

あとは上下左右対称なので、S(r,c), S(H-1-r,c), S(r,W-1-c), S(H-1-r,W-1-c)の４か所の石を取る場合、先に上下をそろえるか左右をそろえるか得点の大きな方の手段を取ればよい。

int H,W;
ll A,B;
string S[202],T[202];
int LR,UD;

void countmiss() {
	int i,j,k,l,r,x,y; string s;
	FOR(y,H) S[y]=T[y];
	LD=UD=0;
	FOR(y,H/2) FOR(x,W/2) {
		if(S[y][x]!=S[H-1-y][x]) UD++;
		if(S[y][W-1-x]!=S[H-1-y][W-1-x]) UD++;
		if(S[y][x]!=S[y][W-1-x]) LR++;
		if(S[H-1-y][x]!=S[H-1-y][W-1-x]) LR++;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>A>>B;
	FOR(y,H) cin>>T[y];
	
	ll ma=0;
	// first LR
	{
		countmiss();
		ll tmp=0;
		FOR(y,H) FOR(x,W) if(S[y][x]=='S' && S[y][W-1-x]=='.') {
			S[y][x]='.';
			LR--;
			if(LR==0) tmp+=B;
			if(S[H-1-y][x]=='S') UD++;
			else UD--;
			if(UD==0) tmp+=A;
		}
		FOR(y,H) FOR(i,W) {
			if(i%2==0) x=i/2;
			else x=W-1-(i/2);
			if(S[y][x]=='S' && S[H-1-y][x]=='.') {
				S[y][x]='.';
				UD--;
				if(UD==0) tmp+=A;
				if(S[y][W-1-x]=='S') LR++;
				else LR--;
				if(LR==0) tmp+=B;
			}
		}
		FOR(y,H/2) FOR(x,W/2) if(S[y][x]=='S') tmp+=max(2*A+B,2*B+A);
		ma=tmp;
	}
	{
		countmiss();
		ll tmp=0;
		FOR(y,H) FOR(x,W) if(S[y][x]=='S' && S[H-1-y][x]=='.') {
			S[y][x]='.';
			UD--;
			if(UD==0) tmp+=A;
			if(S[y][W-1-x]=='S') LR++;
			else LR--;
			if(LR==0) tmp+=B;
		}
		FOR(x,W) FOR(i,H) {
			if(i%2==0) y=i/2;
			else y=H-1-(i/2);
			
			if(S[y][x]=='S' && S[y][W-1-x]=='.') {
				S[y][x]='.';
				LR--;
				if(LR==0) tmp+=B;
				if(S[H-1-y][x]=='S') UD++;
				else UD--;
				if(UD==0) tmp+=A;
			}
		}
		FOR(y,H/2) FOR(x,W/2) if(S[y][x]=='S') tmp+=max(2*A+B,2*B+A);
		ma=max(ma,tmp);
	}
	
	cout<<ma<<endl;
	
}

まとめ

うーん、こういうのがぱっと発想できないのが弱み。