時間通り参加していないのだけど、この回なんかあったの?
https://yukicoder.me/problems/no/936
問題
2人で以下のゲームを行う。
両者両指のうち0~4本のいずれかを立てた状態である。
両者交互に手番が回ってくるので、以下のいずれかの行動を行う。
- 自身の手のうち1本以上指が立っている手と、相手の手のうち1本以上指が立っている手を選び、相手の手の立てる指数を自身の立てた指の分加算しmod 5を取る。
- 自身の両手の指を再配分する。その際mod5を取ってもよい。ただし実質変わらない状態への変化は許可されない。
自身の行動により、相手の両手の立っている指の数が0になると勝ちとなる。
後手は、自身の手番で1手で勝ち確定できるなら、必ずその手を取る。
また、相手の次の手番で負け確定する手は(不可避でない限り)取らない。
先手がKターン以内に勝利する操作の組み合わせは何通りか。
解法
正直動作パターンを全部総当たりするたけ。
相手は「負け確定手しかない場合は、どれかを取る」という動きがあるので見落とさないよう注意。
ll mo=1000000007; int N,K; ll from[5][5][5][5]; ll to[5][5][5][5]; int win[5][5][5][5]; void solve() { int i,j,k,l,r,x,y; string s; FOR(i,5) FOR(j,5) FOR(x,5) FOR(y,5) if(i+j>0 && x+y>0) { if((i+x)%5+y==0) win[i][j][x][y]=1; if((i+y)%5+x==0) win[i][j][x][y]=1; if((j+x)%5+y==0) win[i][j][x][y]=1; if((j+y)%5+x==0) win[i][j][x][y]=1; } cin>>N>>K; cin>>i>>j>>x>>y; from[i][j][x][y]=1; ll ret=0; while(K--) { ZERO(to); //攻撃 FOR(i,5) FOR(j,5) FOR(x,5) FOR(y,5) if(from[i][j][x][y]) { ll v=from[i][j][x][y]; if(N==0) { if(i&&x) { if((i+x)%5+y==0) (ret+=v)%=mo; else (to[i][j][(i+x)%5][y]+=v)%=mo; } if(i&&y) { if((i+y)%5+x==0) (ret+=v)%=mo; else (to[i][j][x][(i+y)%5]+=v)%=mo; } if(j&&x) { if((j+x)%5+y==0) (ret+=v)%=mo; else (to[i][j][(j+x)%5][y]+=v)%=mo; } if(j&&y) { if((j+y)%5+x==0) (ret+=v)%=mo; else (to[i][j][x][(j+y)%5]+=v)%=mo; } int a,b; FOR(a,5) FOR(b,5) { if(a+b==0) continue; if(a+b>i+j) continue; if((a+b)%5!=(i+j)%5) continue; if(a==i&&b==j) continue; if(a==j&&b==i) continue; (to[a][b][x][y]+=v)%=mo; } } else { //必勝ならそれで終了 if(win[x][y][i][j]) continue; int pat=0; if(i&&x&&win[(x+i)%5][j][x][y]==0) (to[(i+x)%5][j][x][y]+=v)%=mo, pat++; if(i&&y&&win[(y+i)%5][j][x][y]==0) (to[(i+y)%5][j][x][y]+=v)%=mo, pat++; if(j&&x&&win[i][(x+j)%5][x][y]==0) (to[i][(j+x)%5][x][y]+=v)%=mo, pat++; if(j&&y&&win[i][(y+j)%5][x][y]==0) (to[i][(j+y)%5][x][y]+=v)%=mo, pat++; int a,b; FOR(a,5) FOR(b,5) { if(a+b==0) continue; if(a+b>x+y) continue; if((a+b)%5!=(x+y)%5) continue; if(a==x&&b==y) continue; if(a==y&&b==x) continue; if(win[i][j][a][b]) continue; (to[i][j][a][b]+=v)%=mo; pat++; } if(pat==0) { //どうやっても負ける if(i&&x) (to[(i+x)%5][j][x][y]+=v)%=mo; if(i&&y) (to[(i+y)%5][j][x][y]+=v)%=mo; if(j&&x) (to[i][(j+x)%5][x][y]+=v)%=mo; if(j&&y) (to[i][(j+y)%5][x][y]+=v)%=mo; int a,b; FOR(a,5) FOR(b,5) { if(a+b==0) continue; if(a+b>x+y) continue; if((a+b)%5!=(x+y)%5) continue; if(a==x&&b==y) continue; if(a==y&&b==x) continue; (to[i][j][a][b]+=v)%=mo; } } } } swap(from,to); N^=1; } cout<<ret<<endl; }
まとめ
ややこしいけど、やることは愚直な問題。