HackerRank Weekly Challenges - Week 3 4問目 - A stones game

Source

HackerRank Weekly Challenges - Week 3 4問目
problem statement(コンテストページ)
problem statement

問題概要

$2$ 人で石取りゲームを行う.$2$ 人で順番に行動していって,行動できなくなったら負け.
最初,$N$ 個の山があって,$k$ 番目の山には $k$ 個の石が置いてある.
各ターン,$1$ つの空でない山を選び,その山に含まれる石の半分以上を破棄する.
先手必勝か後手必勝かを判定し,先手必勝ならば,先手が勝つために最初のターンに破棄する石の最小値を求める問題.

解法

$x$ 個の石から半分以上捨てると $y$ 個になったというのは,$2$ 進数で書き表した時,$y$ の桁数は $x$ の桁数より小さいという風に読み替えれることがわかる.
つまり,$k$ 番目の山に $k$ を $2$ 進数で書いた時の桁数個の石があるような,普通のNim($1$ 個以上の石を取っていく)と見ることもできる.
読み替えた後の,石の数は,$1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,\ldots$ となり,各山に対するgrundy数は石の数に等しい.
$N$ が奇数の場合は,最初の山から石を $1$ 個取れば,残りの山のgrundy数は必ずペアで出てくるので,勝てる.
よって,$N$ が奇数の場合は,答えは $1$.
$N$ が偶数の場合は,grundy数(のXOR)が $0$ になるような石の取り方をまじめに考える.
grundy数がいくつの山から石を取るかは全部試す.
その山のgrundy数をいくつにすれば良いかは,他の山のgrundy数のXORを取ればわかる.
この時,他の山のgrundy数はまじめに計算しなくても,最初の $1$,最後の山のgrundy数,取った山のgrundy数のXORを取れば良い(残りはペアになってでてきて消える).
その結果,grundy数 $i$ の山からいくつが石をとって,grundy数 $j$ の状態にしたいという時に,最小でいくつの石を取れば良いかを求めることになる.
$i-j \geq 2$ ならば,$2^{i-1}$ 個の石がある山から石を取り除いて,$2^{j}-1$ 個の石を残せば良い.
$i-j = 1$ ならば,半分以上捨てなければならなかったので, $2^{i-1}$ の山から半分捨てて $2^{i-2}$ 個だけ残せば良い.
ちなみに,最悪の場合でも,最後の山の石の数を $1$ にすれば,全体のgrundy数が $0$ の状態にできるので,必ず先手必勝(だが,これは取る石の数最小とは限らない).
時間計算量は $O(T \log N)$.

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(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

int main(){
  int T, N;
  int i, j, k, h, x;
  int res, tmp;

  reader(&T);
  while(T--){
    reader(&N);
    res = 1000000000;

    if(N%2==1){
      res = 1;
    } else {
      k = N;
      h = 0;
      while(k) h++, k/=2;
      x = (h^1);
      for(i=h;i;i--) for(j=i-1;j>=0;j--) if((x^i^j) == 0){
        tmp = (1<<(i-1)) - ((1<<j)-1);
        if(j==i-1) tmp = (1<<(i-1))/2;
        res = min(res, tmp);
      }
    }

    writer(res, '\n');
  }

  return 0;
}

Current time: 2017年07月23日15時42分09秒
Last modified: 2014年12月05日03時14分50秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_w3
トップページに戻る

Logged in as: unknown user (not login)

ログイン: