kmjp's blog

競技プログラミング参加記です

AtCoder ARC #041 : A - コインの反転、B - アメーバ

ARC#041に参加。
ABC早解きだけでこの順位でいいのだろうか。
http://arc041.contest.atcoder.jp/tasks/arc041_a
http://arc041.contest.atcoder.jp/tasks/arc041_b

A - コインの反転

表のコインがX枚、裏のコインがY枚ある。
このうちK枚のコインをひっくり返すとき、最大何枚のコインを表にできるか。

ひっくり返すパターンを総当たりしても良いし、できるだけ裏のコインをひっくり返しても良い。
以下の解は前者。

int X,Y,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	int ma=0;
	cin>>X>>Y>>K;
	for(x=max(0,K-Y);x<=min(X,K);x++) {
		y=K-x;
		ma=max(ma,X-x+y);
	}
	cout<<ma<<endl;
	
}

B - アメーバ

二次元のグリッドに対し、各セルにいるアメーバの数が与えられる。
各アメーバは1回の行動で上下左右の隣接マスにそれぞれ分裂する(元いたセルからはいなくなる)。
与えられたグリッドが行動後の状態を示すとき、行動前のアメーバのパターンを示せ。

入力状態にたいし、上の行から順にアメーバを走査する。
今見ている行より上のアメーバが処理済みなので、(r,c)のセルにアメーバがいる場合、それは行動前に(r+1,c)にいたと判断できる。
また、行動前に(r+1,c)にアメーバがいたということは、行動後に(r+1,c-1)、(r+1,c+1)、(r+2,c)にも分裂したことになるので、その分入力状態からアメーバを減算すればよい。

int H,W;
string S[1010];
string T[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		T[y]=S[y];
		FOR(x,W) T[y][x]='0';
	}
	FOR(y,H) FOR(x,W) if(S[y][x]>'0') {
		i=S[y][x]-'0';
		T[y+1][x] += i;
		S[y+2][x] -= i;
		S[y+1][x+1] -= i;
		S[y+1][x-1] -= i;
	}
	
	FOR(y,H) cout<<T[y]<<endl;
	
}

まとめ

A問題、本番は無駄に総当たりなんてしちゃったなぁ。