yukicoder No.74 - 貯金箱の退屈

Source

ニコニコミュニティ
問題文

問題概要

$N$ 個のコインが円周上に並んでいる.
最初コイン $k$ は表か裏なのかが与えられる.
あるコイン $k$ を選ぶと,$k$ から $D_k$ 個だけ右のコインをひっくり返し,$D_k$ 個だけ左のコインをひっくり返す.
ただし,その $2$ つのコインが一致する場合は,$2$ 回ひっくり返すのではなく $1$ 回だけひっくり返す.
すべてのコインを表にすることができるかどうかを判定する問題.

解法

各コインを選ぶかどうかを変数として,各コインがひっくり返る回数に対する方程式を立てると ${\mathbb Z}/2{\mathbb Z}$ 上の連立一次方程式になるのでガウスの掃き出し法などで解き解があるかどうかを判定すれば良い.
もしくは,コイン $x$ とコイン $y$ を同時にひっくり返せるなら,ノード $x$ とノード $y$ の間に枝を張るようなグラフを考え,各連結成分ごとにすべて表にできるかどうか調べれば良い.
このとき,各連結成分内のパスにそってひっくり返せば任意の $2$ つのコインをひっくり返せるので,裏のコインの数が偶数であれば可能.
また,$1$ 枚だけひっくり返せるなら,偶奇が調節できるので可能.
連立一次方程式では,時間計算量 $O(N^3)$ でビット並列すれば数十倍早くなる,連結成分ごとに調べるのはほぼ $O(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)

#define ll long long
#define ull unsigned ll

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 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');}

int binaryGaussJordan(int r, int c, int right, ull **mat){int i,j,k,b =(c+right+63)/64,a=0;rep(j,c){REP(i,a,r)if(mat[i][j>>6]&(1ULL<<(j&63))) break;if(i==r)continue;if(i!=a)REP(k,j>>6,b)swap(mat[i][k],mat[a][k]);REP(i,a+1,r)if(mat[i][j>>6]&(1ULL<<(j&63)))REP(k,j>>6,b)mat[i][k]^=mat[a][k];a++;}return a;}

int N;
int D[1000], W[1000];

ull *mat[222];

int main(){
  int i, j, k;

  reader(&N);
  rep(i,N) reader(D+i);
  rep(i,N) reader(W+i);

  rep(i,N) mat[i] = (ull*)malloc(10000);

  rep(i,N){
    j = (i + D[i]) % N;
    k = (i - D[i] + 100000*N) % N;
    mat[j][i/64] |= 1ULL<<(i%64);
    mat[k][i/64] |= 1ULL<<(i%64);
  }

  rep(i,N) if(W[i]==0) mat[i][N/64] |= 1ULL<<(N%64);

  k = binaryGaussJordan(N, N, 1, mat);
  REP(i,k,N) if(mat[i][N/64]&(1ULL<<(N%64))) break;
  writerLn(i==N?"Yes":"No");

  return 0;
}

Current time: 2017年09月25日07時50分51秒
Last modified: 2014年11月21日00時53分08秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: