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問題、本番は無駄に総当たりなんてしちゃったなぁ。