問題文長いな…。
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; }
まとめ
これも自信をもって答えにくい問題。