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

2014年12月05日03時14分50秒

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: 2024年04月25日03時52分40秒
Last modified: 2014年12月05日03時14分50秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_w3
トップページに戻る

Logged in as: unknown user (not login)

ログイン：