BayanのEliminationラウンドに参加。
前半は運営のグダグダもあり苦戦したけど、後半C,Eを解いてTシャツ圏内に入れた。
http://contest.bayan.ir/en/contest/elimination_2014/problem/C/
問題
N*Mのグリッドがあり、各セルの初期値は0である。
プレイヤーは任意のセルからスタートし、隣接マスをたどっていくという処理を行う。
その際、通過したマスには1,2,3...と段々数字をインクリメントさせながら格納していく。
(同じマスは複数回通っても良く、そのたび数字は上書きされる)
最終的なグリッドの状態が与えられるので、そのような移動は可能か答えよ。
解法
最終的なグリッドにおいて、数字の小さなマスの順に辿っていくことを考える。
この場合、以下の条件を満たすなら条件を満たす移動は可能である。
セルAの次に大きな数値のセルをBとしたとき:
- A→Bへの移動は、セルAの値以上のセルだけを通って到達できる。
- かつ、その際の最短移動距離はセルBとセルAの数値の差以下である。
- かつ、最短移動距離とセルBとセルAの数値の差の偶奇は一致する。偶奇が一致すれば最短移動距離がセルBとセルAの数値の差より短い場合、途中で2セルを往復することで数値の増分を嵩増しできる。
- ただし、最後の2セルだけは隣接してかつ数値の差が1である。なぜなら往復して数値を嵩増しする2セルがないためである。
A→Bの最短距離は適当なBFSでO(NM)なので、全体でO(N^2*M^2)で解ける。
int H,W; ll A[51][51]; vector<pair<int,int> > V; int ok[51][51]; int dist(int ty,int tx,int sy,int sx) { int y,x,i; int di[51][51]; FOR(y,H) FOR(x,W) di[y][x]=100000; di[ty][tx]=0; queue<int> Q; Q.push(ty*100+tx); while(Q.size()) { int k=Q.front(); Q.pop(); int cy=k/100,cx=k%100; FOR(i,4) { int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1}; int ttx=cx+dx[i],tty=cy+dy[i]; if(ttx<0 || tty<0 || ttx>=W || tty>=H || ok[tty][ttx]==0) continue; if(di[tty][ttx]>di[cy][cx]+1) { di[tty][ttx]=di[cy][cx]+1; Q.push(tty*100+ttx); } } } return di[sy][sx]; } void solve() { int i,j,k,l,r,x,y; string s; V.clear(); cin>>H>>W; FOR(y,H) FOR(x,W) { cin>>A[y][x]; ok[y][x]=1; V.push_back(make_pair(A[y][x],y*100+x)); } sort(V.begin(),V.end()); y=V[0].second/100; x=V[0].second%100; for(i=1;i<V.size();i++) { int ty=V[i].second/100; int tx=V[i].second%100; ok[y][x]=0; int d=dist(y,x,ty,tx); if(d>=10000) return _P("NO\n"); if(V[i].first-V[i-1].first<d) return _P("NO\n"); if((V[i].first-V[i-1].first)%2!=d%2) return _P("NO\n"); if(i==V.size()-1) { if(d!=1 || V[i].first-V[i-1].first!=1) return _P("NO\n"); } x=tx; y=ty; } _P("YES\n"); }
まとめ
これはアプローチはすぐ思いついたけど、7WAとかなりコーナーケースの分類に手こずった。