ちょっと古い問題だけど、ARCで解ききってないのはこれだけなので解いてみた。
公式の解説が無いので、他のソースを見ながら自分なりに解釈して回答。
http://arc002.contest.atcoder.jp/tasks/arc002_4
問題
歩だけでできている将棋の盤面がある。
自分の歩を相手側一番奥のマスに到達させるか、相手の歩を全滅させたら勝ち。
oとxで盤面が与えられたとき、勝利する方を答える。
解法
"o.x"のようにoとxが1マス空けた状態では、先に動くと相手に自分の駒を取られて負ける。
まず、上の条件より、自分の進行方向に敵駒があるとそれを突破することができない。
敵駒との距離を1マス以下にできない。
よって、まずは自分の正面に敵駒が無い場合列があった場合、敵陣奥までの距離を求めてそれが小さい方が勝ち。
他のケースは、互いに自分の正面に敵駒がある場合である。
まず、oとxが混在している場合、例えば..o..x..oo..x.x..という場合、oは左に動かないしxは右に動かないので、左側のxと右側のoは関係しない。
よって、余計なマスも取り除いて"o..x"および"oo..x.x"の２つの組があると考える。
ここで、以下の条件を考える。
- 先ほど"o.x"の様に1マス空けた状態では先に動くと負けると書いたが、駒が多くても"ooooo.xxxxx"のような場合、先に動くとその駒を取られた上に先頭のoとxが１マス空いた状態が続くので、やはり負ける。
- 逆に、２マス以上空いている場合、できるだけ先頭の駒を進めるのが得である。なぜなら、"ooooo...xxxx"のような構成の時、先頭のoを１マス進めると、残りの４つのoを1マス進める猶予ができるからである。
左側にo、右側にxが集まるように分割した文字列の各組に対し、ox両者が最適に動く場合何マス移動できるか考える。
両者とも、先頭同士の距離が残り２マス（＝空きが１マス）または３マス（空きが２マス）になるまで積極的に動くと考える。
そして"oooo.xxxxx"の様に距離が２マスまたは３マスを残して後ろが詰まるまでのステップ数をカウントしておく。
また、この際残りが３マスになる場合、oとxの数およびその和を覚えておく。
先頭同士の距離が偶数の場合、互いに同じマスずつ動くと最後に空きが１マスになる。
このような状態では、どちらが先に動いても変わらない。
問題は距離が奇数の場合で、これは先に動いた方が得である。あとで動くと、最後に空きが１マスの状態で動くことになるためである。
ここで、距離が奇数になるような文字列群が複数ある場合、どこから先に動くとよいか考えると、これは文字列中にあるoとxの和の大きい順であることがわかる。
たとえば、先頭のoが先に１歩動くと、加えて後ろにある残りのoが１歩ずつ動ける猶予ができるうえ、敵のxが１歩ずつ動ける猶予をなくせるので、足し引きで両者の数の分得するためである。
色々書いたが、まとめると以下の通り。
- 先頭同士の距離が偶数なら、oxそれぞれ距離が２マスになるまで動く場合のステップ数を猶予ステップカウントする。
- 先頭同士の距離が奇数なら、まずoxそれぞれ距離が３マスになるまで動く場合のステップ数を猶予ステップカウントする。そして、距離が奇数になる項目同士をoとxの和で大きい順にソートし、順番にoとxの数を猶予ステップ数にカウントする。
- 最後に猶予ステップ数の大きい方が勝ち。
int W,H; char str[2002][2002]; vector<string> strs; void dostep(string& st,int& dist,int& no,int& nx,int& stepo, int& stepx) { int i,lo,fx,farx,faro; //数を数えつつ、残り距離が1になるまでのステップを探る no=nx=stepo=stepx=0; lo=fx=-1; FOR(i,st.size()) { if(st[i]=='o') lo=i; if(st[i]=='x') if(fx<0) fx=i; } //残り1ますになるまでの距離 dist = fx-lo-2; //残り1マス・2マスになるまでのステップ faro=lo+dist/2; farx=fx-dist/2; for(i=st.size()-1;i>=0;i--) if(st[i]=='o') stepo += faro-(no++)-i; FOR(i,st.size()) if(st[i]=='x') stepx += i-(farx+(nx++)); } void solve() { int f,r,i,j,k,l; int x,y,mx,my; int mino, minx; GET2(&H,&W); FOR(y,H) GETs(str[y]); //触れずにゴールできるか？ mino=minx=3000; FOR(y,H) { for(x=W-1;x>=0;x--) { if(str[y][x]=='x') break; if(str[y][x]=='o') mino=min(mino, W-1-x); } FOR(x,W) { if(str[y][x]=='o') break; if(str[y][x]=='x') minx=min(minx, x); } } if(mino<=minx && mino<3000) { _P("o\n"); return; } if(minx<mino) { _P("x\n"); return; } //oとxの対を調べる FOR(y,H) { int so=-1,sx=-1; string s=string(str[y]); FOR(x,W) { if(str[y][x]=='o') { if(sx>=0) { strs.push_back(string(s,so,sx-so+1)); so=x; } if(so==-1) so=x; sx=-1; } if(str[y][x]=='x') sx=x; } if(sx>=0) strs.push_back(string(s,so,sx-so+1)); } ll tso,tsx; tso=tsx=0; vector<pair<int, pair<int,int> > > cand; FOR(i,strs.size()) { int dist, no, nx, stepo, stepx; dostep(strs[i],dist,no,nx,stepo,stepx); tso+=stepo; tsx+=stepx; //先手を取った方がよい if(dist%2) cand.push_back(make_pair(no+nx,make_pair(no,nx))); } //効果の大きい順に先手を取る sort(cand.begin(),cand.end()); reverse(cand.begin(),cand.end()); j=0; FOR(i,cand.size()) { if(j==0) tso += cand[i].second.first; else tsx += cand[i].second.second; j^=1; } if(tso>tsx) _P("o\n"); else _P("x\n"); return; }
まとめ
他人のソースを見ての回答作りであるが、ソースを読んで理屈を理解できたのは良かった。
でも本番だけでこれを思いつくのはすごいな…。
Nimとかとも違うけど、定石があるのかな。
