kmjp's blog

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

Codeforces #666 Div1 B. Stoned Game

なんだこの問題。
https://codeforces.com/contest/1396/problem/B

問題

2人で行うターン制のゲームを考える。
N要素の整数列Aが与えられる。
各ターン、正の値を持つ要素を選び、デクリメントする。
その際、相手が直前に選んだものと同じ要素は選べない。

自ターンでデクリメントができない場合負けとなる。
両者最適手を取るとき、勝者はどちらか。

解法

両者最大値を取る要素を選ぶのが最適。
sum(A)は小さいので愚直にシミュレートしても間に合う。

int T;
int N;
int A[101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		int sum=0;
		FOR(i,N) {
			cin>>A[i];
		}
		
		i=0;
		int pre=-1;
		while(1) {
			x=-1;
			int p=0;
			FOR(j,N) if(j!=pre&&A[j]>p) x=j, p=A[j];
			if(x==-1) break;
			A[x]--;
			pre=x;
			i^=2;
		}
		if(i==0) cout<<"HL"<<endl;
		else cout<<"T"<<endl;
		
	}
}

まとめ

sum(A)が大きければもう少し難しいか?