D - Takahashi the Wall Breaker Editorial
by 
mechanicalpenciI
高橋君の住む町に対して、次のような重み付き有向グラフ \(G\) を考えます。
- 頂点は区画と一対一に対応する。特に、\(G\) は\((H\times W)\) 個の頂点を持つ。
- それぞれの区画 \(C\) について、上下左右に隣接する区画 \(C'\) であって、道であるようなものについて、\(C\) に対応する頂点から \(C'\) に対応する頂点へ向けてコスト \(0\) の辺を張る。
- それぞれの区画 \(C\) について、上下左右に隣接する区画 \(C'\) であって、壁であるようなものについて、\(C\) に対応する頂点から \(C'\) に対応する頂点へ向けてコスト \(1\) の辺を張る。
- それぞれの区画 \(C\) について、その区画において上下左右方向いずれかを向いたときに \(2\) つ前にあるような区画 \(C'\) であって、\(C\) と \(C'\) の間にある区画または区画 \(C'\) が壁であるようなものについて、\(C\) に対応する頂点から \(C'\) に対応する頂点へ向けてコスト \(1\) の辺を張る。
このとき、\(G\) における、高橋君が最初にいる区画に対応する頂点から魚屋がある区画に対応する頂点への最短距離（経路上の辺の重みの総和の最小値）は答えと一致します。
まず、\(G\) における最短経路を考えると、コスト \(0\) の辺を通る行動を上下左右に隣接する道であるマスへの移動に対応させ、コスト \(1\) の辺を通る行動を、前蹴りしその道になった区画への移動に対応させることで、前蹴りの回数が「 \(G\) における最短距離」以下になるような、魚屋までの行動順を構築できます。
一方で、高橋君が最初にいる区画から前蹴りを \(k\) 回以下行って到達可能な区画について、その区画に該当する頂点まで高橋君が最初にいる区画に対応する頂点から距離が高々 \(k\) となるような経路が構築できることを数学的帰納法によって示すことができます。
証明
$k=0$ のときは明らかです。
$k=d-1$ で成り立っているとして、$k=d$ のときについて考えます。
以下、到達可能・到達不可能と述べたとき、始点としては高橋君が最初にいる区画を考えるものとします。
前蹴りを $d$ 回行って到達可能な区画 $T$ を $1$ つとり、前蹴りを $d$ 回行って到達する具体的な行動順を $1$ つとります。
町の状態は高橋君が前蹴りを行う前(以下、便宜上、$0$ 回行った後と表記します)、$1$ 回行った後、$\ldots$、$d$ 回行った後の $(d+1)$ 種類存在し、
高橋君が最初いる区画から道への移動を繰り返すだけで（前蹴りせずに）到達可能な区画の数は（広義）単調増加します。
特に、行動順の移動の途中で通った区画は、前蹴りを $d$ 回行った後の状態において、すべて到達可能です。
ここで、それぞれの移動の途中で通った区画について次のように $0$ 以上 $d$ 以下の整数を割り当てることができます。
- その区画が、前蹴りを（一度も）行う前に到達可能であったならば、$0$ を割り当てる。
- その区画が、前蹴りを $(i-1)$ 回行った時点では到達不可能であったが、$i$ 回行った時点で到達可能になったとき、$i$ を割り当てる。
そうでないとき、行動順の移動の途中で通った区画について、割り当てられた数字を通った順に並べた列（複数回通った場合はその度に並べるものとする）$A=(A_1,A_2\ldots,A_{\lvert A\rvert})$ を考えると、 列の最終項は区画 $T$ に割り当てられた数字となるから $d$ となります。
列の初項には $0$ $(\neq d)$ が割り当てられていることから、ある $m$ が存在して、$A_{\lvert A\rvert}=A_{\lvert A\rvert-1}=\cdots=A_{\lvert A\rvert-m+1}=d$, $A_{\lvert A\rvert-m} < d$ となります。
ここで、$A_i=d$ となるのは、定義より、「$d$ 回目の前蹴りで道に帰られた区画」または「最初の時点で道であった区画」のいずれかですが、行動順における $\lvert A\rvert-m+1$ 番目の区画が最初の時点で道であった区画であった場合、$A_{\lvert A\rvert-m}\geq A_{\lvert A\rvert-m+1}$ となるため、この区画は $d$ 回目の前蹴りで道に帰られた区画となります。
よって、行動順における $\lvert A\rvert-m+1$ 番目、$\lvert A\rvert-m+2$ 番目、$\ldots$、$\lvert A\rvert$ 番目の区画の中に$d$ 回目の前蹴りで道に帰られた区画は少なくとも $1$ つ存在し、そのうち最も最後に訪れたもの（番号が大きいもの）を区画 $T'$ とします。$d$ 回目の前蹴りを行った区画（以下、区画 $S'$ とします）自体は $(d-1)$ 回以下の前蹴りで到達できるものであり、対応する頂点まで距離 $(d-1)$ 以下の経路を構築できます。
区画 $T'$ は区画 $S'$ からの前蹴りによって道に変えられたため、区画 $S'$ に対応する頂点からは区画 $T'$ に対応する頂点まで長さ $1$ の辺が伸びています。
区画 $T'$ から区画 $T$ までの移動においては（区画 $T'$ 自身を除いて）「最初の時点で道であった区画」しか経由しないため、区画 $T'$ に対応する頂点から区画 $T$ に対応する頂点まではコスト $0$ の辺のみを用いて到達可能です。よって、「高橋君が最初いる区画に対応する頂点から区画 $S'$ に対応する頂点までの経路」（帰納法により存在）、「区画 $S'$ に対応する頂点から区画 $T'$ に対応する頂点へ張られている辺」、「区画 $T'$ に対応する頂点から区画 $T$ に対応する頂点までの距離 $0$ の経路」をこの順につなげることで距離が高々 $d$ となるような経路が構築できました。
ゆえに、$k=d$ のときにも成り立つことが示されました。
これらにより、「必要な前蹴りの回数」\(\leq\)「\(G\) における最短距離」、「必要な前蹴りの回数」\(\geq\)「\(G\) における最短距離」が示され、等しいことがわかりました。 上記のグラフにおける最短距離は Dijkstra 法などでも適切な実装で時間内に解くことが可能ですが、今回は辺の重みが \(0\) または \(1\) しかないため 01-BFS を用いることでより高速に問題を解くことができます。 01-BFSは、基本的な考え方は Dijkstra 法と同じですが、探索中にキューに入る頂点の暫定距離が高々 \(1\) しか異ならないことを活かして、優先度付きキューの代わりに両端キューなどを用いることで、この問題を \(O(HW)\) で解くことができます。 01-BFSについては、 ABC246-Eの公式解説 にも詳細が記述されているため、参照してみてください。
よって、グラフ \(G\) の構築、最短距離の計算いずれも \(O(HW)\) で行えるため、十分高速です。
ゆえに、この問題を解くことができました。
c++ による実装例:
#include <bits/stdc++.h>
using namespace std;
int main() {
int h,w;
int a,b,c,d;
int x,y,z,nx,ny;
bool wall;
deque<int>dq;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
cin>>h>>w;
vector<string>s(h);
vector<vector<int> >ans(h,vector<int>(w,h*w));
for(int i=0;i<h;i++)cin>>s[i];
cin>>a>>b>>c>>d;
a--,b--,c--,d--;
ans[a][b]=0;
dq.push_front(a*w+b);
while(!dq.empty()){
z=dq.front();
dq.pop_front();
if(z==(c*w+d)){
cout<<ans[c][d]<<endl;
return 0;
}
x=z/w,y=z%w;
for(int i=0;i<4;i++){
wall=false;
for(int j=1;j<=2;j++){
nx=x+dx[i]*j;
ny=y+dy[i]*j;
if((nx<0)||(nx>=h)||(ny<0)||(ny>=w))break;
if(s[nx][ny]=='#')wall=true;
if(!wall){
if(j==1){
if(ans[nx][ny]>ans[x][y]){
ans[nx][ny]=ans[x][y];
dq.push_front(nx*w+ny);
}
}
}
else{
if(ans[nx][ny]>ans[x][y]+1){
ans[nx][ny]=ans[x][y]+1;
dq.push_back(nx*w+ny);
}
}
}
}
}
return 0;
}
posted:
last update: