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

2015年12月12日01時54分08秒

HackerRank HourRank 3 4問目 - The Cowardly Sage

Source

HourRank 3 4問目
problem statement（コンテストページ）

問題概要

$2$ 人でゲームをするので，先手必勝か，後手必勝かを判定する問題．
$N$ 個の打ち上げ花火が，第 $1$ 象限に設置されている．
$i$ 番目の花火は，原点から $R_i$ だけ離れていて，原点を通り傾きが $A_i/B_i$ の直線上にある．
花火を打ち上げる際，原点からの距離を指定して，原点からの距離が指定した距離に等しい花火を全て打ち上げるか，
原点を通る直線を指定し，その直線上の花火を全て打ち上げるかすることができる．
また，安全面の問題で，どうやっても，一度に $3$ つ以上の花火が打ち上げられることはありえないように，配置されている．
順番に，上のどちらかの行動を $1$ 回ずつ行っていき，最初に花火を打ち上げられなかった人が負けとなる．

解法

$A_i,B_i$ は $\mathrm{GCD}(A_i,B_i)$ で割っておくと，同時に打ち上げられる花火は $R_i$ が一致するか $(A_i,B_i)$ が一致するか，となる．
花火をノードとし，同時に打ち上げられる花火間に枝を張ると，最大次数が $2$ のグラフができる．
各グラフの連結成分は，直線か，サイクルになる．
よって，大きさ $1$ から $N$ までの直線のグラフ，サイクルのグラフについて，Grundy数を求めてやれば良い．
ノード数 $k$ のサイクルのグラフは，$2$ 個のノードを取って，$k-2$ ノードの直線のグラフに遷移するしかなく，
ノード数 $k$ の直線のグラフは，端を $1$ 個または $2$ 個取って，$k-1,k-2$ ノードの直線のグラフに遷移するか，
間の $2$ ノードを取って，ノード数 $i$ とノード数 $k-i-2$ の直線のグラフ $2$ 個に遷移する．
もちろん，グラフが分割されれば，別々にGrundy数を求めて $\mathrm{XOR}$ を取れば良い．
$O(TN^2)$ 時間をかけても十分間に合うが，Grundy数は最初に計算すれば良いので，時間計算量 $O(N^2 + TN (\log N + \log C)), \ C = \max(A_i,B_i)$ 程度でできる．

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);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

template<class T> T GCD(T a,T b){T r; while(a)r=b,b=a,a=r%a; return b;}
template<class T> void reduceFraction(T&a, T&b){T g=GCD(a,b);a/=g;b/=g;}

void unionInit(int d[],int s){int i;rep(i,s)d[i]=i;}
int unionGet(int d[],int n){int t=n,k;while(d[t]!=t)t=d[t];while(d[n]!=n)k=d[n],d[n]=t,n=k;return n;}
int unionConnect(int d[],int a,int b){a=unionGet(d,a);b=unionGet(d,b);if(a==b)return 0;d[a]=b;return 1;}

int T, N, R[1000], A[1000], B[1000];

int edge[1000][100], es[1000];
int ind[1000];

int lin[1010], cir[1010];
int memo[2010];

void solve_lin(int k){
  int i, j;
  if(lin[k] != -1) return;

  if(k==0){ lin[k] = 0; return; }
  if(k==1){ lin[k] = 1; return; }
  if(k==2){ lin[k] = 2; return; }

  solve_lin(k-1);
  solve_lin(k-2);
  rep(i,k-1) solve_lin(i), solve_lin(k-i-2);

  rep(j,k+10) memo[j] = 0;
  memo[lin[k-1]] = 1;
  memo[lin[k-2]] = 1;
  rep(i,k-1) memo[lin[i]^lin[k-i-2]] = 1;
  for(i=0;;i++) if(memo[i]==0) break;
  lin[k] = i;
}

void solve_cir(int k){
  int i, j;
  if(cir[k] != -1) return;

  if(k==0){ cir[k] = 0; return; }
  if(k==1 || k==2){ cir[k] = 1; return; }
  solve_lin(k-2);
  if(lin[k-2]==0) cir[k] = 1; else cir[k] = 0;
}

int main(){
  int i, j, k;
  int cnt, deg;
  int res;

  rep(i,1010) lin[i] = cir[i] = -1;
  rep(i,1010) solve_lin(i);
  rep(i,1010) solve_cir(i);

  reader(&T);
  while(T--){
    reader(&N);
    rep(i,N) reader(R+i,A+i,B+i);
    rep(i,N) reduceFraction(A[i], B[i]);

    res = 0;
    unionInit(ind, N);
    
    rep(i,N) es[i] = 0;
    rep(i,N) REP(j,i+1,N) if(R[i]==R[j] || (A[i]==A[j]&&B[i]==B[j])){
      edge[i][es[i]++] = j;
      edge[j][es[j]++] = i;
      unionConnect(ind, i, j);
    }

    rep(k,N){
      cnt = deg = 0;
      rep(i,N) if(unionGet(ind,i)==k){
        cnt++;
        if(es[i]==1) deg++;
      }
      if(deg){
        res ^= lin[cnt];
      } else {
        res ^= cir[cnt];
      }
    }

    if(res==0) writerLn("Coward"); else writerLn("Sage");
  }

  return 0;
}

Current time: 2024年04月19日02時47分25秒
Last modified: 2015年12月12日01時54分08秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_hourrank-3
トップページに戻る

Logged in as: unknown user (not login)

ログイン：