Yandex.Algorithm 2014
Yandex.Algorithm 2014 Round 3
問題文
$2$ 人でゲームを行う.交互に行動し,打つ手がなくなった方が負け.
ゲームは $2$ つの正整数 $N, L$ によって決まって,$N$ のみ入力で与えられる.
最初,$N$ マスの連続するセルがあって,全てのマスが白い.
各ターンでは,全てのマスが白い連続する $L$ マスを選び,その $L$ マス全てを黒く塗る.
$1 \leq L \leq N$ なる全ての $L$ に対して,先手必勝か,後手必勝かを求める問題.
全ての $L$ について,独立にGrundy数を求めると,それぞれの $L$ に対して $O(N^2)$ かかるので,合計 $O(N^3)$ となり間に合わない.
ただし,この $O(N^3)$ で全ての $1 \leq L \leq N \leq 7000$ のゲームが先手必勝か,後手必勝かを調べることができる.
これは実行しても $30$ 秒ぐらい程度しかかからないので,実行してみてパターンを探す.
サイズが大きいと,基本的には先手必勝が多く,後手必勝となるパターンとして,$N+a = bL$,ただし $(a,b) = (1,3),(1,5),(3,9),(5,13),(5,17),(7,21),\ldots$ というのを見ることができる.
今挙げたところまでを除くと,$L \geq 245$ では全て先手必勝となる.
よって,$L < 245$ のみを調べれば,計算量が $245 \times O(N^2)$ 程度になって間に合うようになる.
ただし,これだと結構制限時間ギリギリだったので,埋め込む後手必勝パターン数を増やした方が良いかもしれない.(次の後手必勝パターンは $b=29$)
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
int N;
char res[10000];
int main(){
int i, j, k, L;
int dp[10000], check[20000];
reader(&N);
// N=7000;
res[N] = '\n'; res[N+1] = '\0';
if(1){
rep(i,20000) check[i] = -1;
REP(L,1,N+1){
if(L < 245){
rep(i,N+1){
for(j=0;i-L-j>=j;j++){
check[ dp[j]^dp[i-L-j] ] = i;
}
for(j=0;;j++) if(check[j] != i) break;
dp[i] = j;
}
} else {
REP(i,N,N+1){
dp[i] = 1;
if( (i+1)%L==0 && ((i+1)/L==3 || (i+1)/L==5) ) dp[i] = 0;
if( (i+3)%L==0 && (i+3)/L==9 ) dp[i] = 0;
if( (i+5)%L==0 && (i+5)/L==13 ) dp[i] = 0;
if( (i+5)%L==0 && (i+5)/L==17 ) dp[i] = 0;
if( (i+7)%L==0 && (i+7)/L==21 ) dp[i] = 0;
}
}
// rep(i,N+1) if(i >= L && dp[i]==0) printf("N %d L %d\n",i,L);
if(dp[N]) res[L-1] = 'F'; else res[L-1] = 'S';
}
writer(res);
}
return 0;
}
Current time: 2024年03月19日10時54分17秒
Last modified: 2014年08月06日01時29分15秒 (by laycrs)
Tags: Competitive_Programming Yandex_Algorithm Yandex_Algorithm_2014 Yandex_Algorithm_2014_Round3
トップページに戻る
Logged in as: unknown user (not login)