kmjp's blog

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

Codeforces Global Round 8 : F. Lamps on a Circle

問題文長いな…。
https://codeforces.com/contest/1368/problem/F

問題

N個のランプを使った2人対戦ゲームを行う。
初期状態で全ランプは消えている。

N個のランプは円形に並んでいる。
先手は、ゲームを継続するか中止するか選択できる。
継続するなら、任意の個数Kを選び、ランプをオンにする。
後手は、先手の選んだKに基づき、連続したK個をオフにする。

ゲーム終了時、先手はオン、後手はオフのランプの個数を最大化しようとする。
最適な先手の手順を答えよ。

解法

まずKを考える。
先手によって長さKの領域ができると後手につぶされるので、基本オンが連続したランプはK-1個ごととなる。
ここから最終的にオンになるランプ数が最大となるKが求まる。

あとは、K個毎にオンにしないランプを決め、それ以外を延々オンにしよう。
そのうち最適手状態になる。

int N;
int A[1010];
int T[1010];


void solve() {
	int i,j,l,r,x,y; string s;
	
	cin>>N;
	int ma=-1,k=0;
	for(i=1;i<=N;i++) {
		int num=N-(N+(i-1))/i-(i-1);
		if(num>ma) ma=num, k=i;
	}
	cerr<<ma<<endl;
	
	FOR(i,N) T[i]=(i%k!=k-1);
	T[N-1]=0;
	FOR(i,8888) {
		int num=0;
		FOR(j,N) num+=(T[j]==1&&A[j]==0);
		cout<<num;
		FOR(j,N) if(T[j]==1&&A[j]==0) {
			cout<<" "<<(j+1);
			A[j]=1;
		}
		cout<<endl;
		if(num==0) return;
		cin>>x;
		assert(x>0);
		x--;
		FOR(j,num) A[(x+j)%N]=0;
	}
	cout<<0<<endl;
}

まとめ

これも自信をもって答えにくい問題。