読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

AtCoder ARC #064 : D - An Ordinary Game

ARC

うーん、いまいち。
http://arc064.contest.atcoder.jp/tasks/arc064_b

問題

文字列に対し2人で交互に手番が来るゲームを行う。
各人の手番では、文字列中両端以外の文字を1つ取り除く。
その際、取り除いた結果同じ文字が連続するようなことがあってはならない。
自分の手番で条件を満たす取り除き方ができない場合、負けとなる。

両者最適手を取った場合、勝者はどちらか。

解法

自分の手番で負けとなるのは、2種類の文字が交互に並ぶ場合である。
この場合どこを取り除いても前後が同じ文字になってしまう。

この問題で両端の文字はずっと変化しないため、そのような状況になる場合の正確な文字列長はわからないが、文字列長の偶奇は確定する。
あとは各自の手番の残り文字数の偶奇と、上記偶奇が一致する方が負けとなる。

string S;
int L;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	L=S.size();
	
	if((S[0]==S[L-1]) ^ (L%2)) _P("First\n");
	else _P("Second\n");
	
}

まとめ

本番かなり勘で通してしまった。

広告を非表示にする