ARC038に参加。
Dは部分点すら取れなかったけど、Cまでは満点取れて幸い良い順位。
http://arc038.contest.atcoder.jp/tasks/arc038_a
http://arc038.contest.atcoder.jp/tasks/arc038_b
A - カードと兄妹
N枚のカードがあり、各カードには数値A[i]が書かれている。
ここで、2人で交互にN枚のカードを1枚ずつ取り合う。
各人の得点は、取ったカードの数値の総和となる。
両者最適手を取ったとき、先手の得点を求めよ。
カードを数値降順にソートして、先手・後手と順に取っていけば良い。
int N; int A[1010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i]; sort(A,A+N); reverse(A,A+N); int S[2]={}; FOR(i,N) S[i%2]+=A[i]; cout<<S[0]<<endl; }
B - マス目と駒
2次元グリッドがあり、一部のマスは移動不可能である。
最初コマは左上端のセルにいる。
この1つのコマを先手後手交互に動かす。
自分の順番では、駒を右・右下・下の何れかの(移動可能な)隣接マスに移動できる。
移動可能な隣接マスがない場合、負けとなる。
両者最適手を取った場合、勝者はどちらか。
典型的な2人完全情報ゲーム問題。
メモ化再帰やDP等で右下から順に、以下の要領で勝ち負けを決めていく。
- 右・右下・左どこに移動しても(相手が)勝つようなセルは負けセル。
- 右・右下・左どこか1か所でも(相手が)負けるようなセルは勝ちセル。
int H,W; string S[1010]; int memo[200][200]; int win(int Y,int X){ int& ret=memo[Y][X]; if(ret>=0) return ret; ret=0; if(Y<H-1 && S[Y+1][X]=='.' && win(Y+1,X)==0) ret=1; if(X<W-1 && S[Y][X+1]=='.' && win(Y,X+1)==0) ret=1; if(Y<H-1 && X<W-1 && S[Y+1][X+1]=='.' && win(Y+1,X+1)==0) ret=1; return ret; } void solve() { int i,j,k,l,r,x,y; string s; MINUS(memo); cin>>H>>W; FOR(y,H) cin>>S[y]; if(win(0,0)) cout<<"First"<<endl; else cout<<"Second"<<endl; }
まとめ
Aは同着ながらもFirst Acceptでした。