さて問題C。
練習の際、解法はすぐわかったけどWAを2回してしまった。
これでは本番参加しててもそこそこの順位にしかなんなかったな。
http://arc012.contest.atcoder.jp/tasks/arc012_3
問題
五目並べの盤面が与えられる。
この盤面が、普通に五目並べを行っていて到達可能かどうか回答する。
解法
到達可能である条件は以下の通り。
- 黒石と白石の数は、一致しているか黒石が1つ多くなければらない。そうでなければ到達不可。
- 最後に石を打った番の方は、1つ石を取り除くと5石連続しない(そうしないと途中で対戦が終了しているから)
- 最後に石を打った番でない方は、5石連続しない。
黒石と白石の数が同じなら最後の1手は白、黒石が1つ大きければ最後は黒。
それを意識して5石連続の有無を探せばよい。
「1つ石を取り除くと5石連続しない」は盤面のサイズNに対し適当にやってもO(N^4)なのでN<=19なら計算量は問題なし。
int W=19,H=19; char B[20][20]; int no,nx; int goal(char c) { int x,y; FOR(y,19) FOR(x,19) { if(B[y][x]!=c) continue; if(x<15 && B[y][x+1]==c && B[y][x+2]==c && B[y][x+3]==c && B[y][x+4]==c) return 1; if(y<15 && B[y+1][x]==c && B[y+2][x]==c && B[y+3][x]==c && B[y+4][x]==c) return 1; if(x<15 && y<15 && B[y+1][x+1]==c && B[y+2][x+2]==c && B[y+3][x+3]==c && B[y+4][x+4]==c) return 1; if(x>=4 && y<15 && B[y+1][x-1]==c && B[y+2][x-2]==c && B[y+3][x-3]==c && B[y+4][x-4]==c) return 1; } return 0; } void solve() { int f,r,i,j,k,l; int x,y,mx,my; no=nx=0; FOR(y,19) { GETs(B[y]); FOR(x,19) { if(B[y][x]=='o') no++; if(B[y][x]=='x') nx++; } } if(no!=nx && no!=nx+1) { _P("NO\n"); return; } char c1 = (no==nx)?'o':'x'; char c2 = (no==nx)?'x':'o'; if(goal(c1)) { _P("NO\n"); return; } int ng=0; FOR(y,19) FOR(x,19) { if(B[y][x]==c2) { B[y][x]='.'; if(!goal(c2)) { _P("YES\n"); return; } ng++; B[y][x]=c2; } } if(ng) _P("NO\n"); else _P("YES\n"); return; }
まとめ
面倒なので5石並びの判定はif文をだらだら並べてやってしまった。
解法がさっと思いつけたので良かった。