kmjp's blog

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

CADDi 2018 : D - Harlequin

なんとか全完。
https://atcoder.jp/contests/caddi2018/tasks/caddi2018_b

問題

N個の整数列がある。
ここで2人でターン制のゲームを行う。
自分のターンでは、非ゼロの値を1個以上選び、デクリメントする。
デクリメントできない場合、負けとなる。

両者が最適手を取る場合、勝者は先手後手どちらか。

解法

奇数の要素が1個でもあると先手の勝ちである。
先手が奇数の要素をすべて偶数にすればよい。
後手は偶数の要素を1個以上奇数にしなければならないが、先手はそれらを再度指定することで全体を偶数に戻すことができる。
最終的に全要素ゼロになり、後手が負ける。

int N;
int A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(i,N) {
		cin>>A[i];
		if(A[i]%2) return _P("first\n");
	}
	_P("second\n");
	
}

まとめ

400ptでもいい気がした。