保存されている過去のバージョンの一覧

2014年08月06日01時29分15秒

Yandex.Algorithm 2014 Round 3 F問題 - Weird Game

Source

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$）

C++によるスパゲッティなソースコード

#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年04月20日16時41分41秒
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)

ログイン：