kmjp's blog

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

AtCoder ARC #038 : A - カードと兄妹、B - マス目と駒

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でした。