E - 通勤経路
古い問題ということもあり、解説記事が少なかったので、
記事にします。
問題雑概要
(1,1)から(w,h)までの経路を数えます。w,hはそれぞれ100以下です。
今回の問題では、交差点で「曲がる」という選択が2連続で出来ません。
「曲がった」場合には、次の交差点では一度「直進」する必要があります。
進行方向は常に上か右かの2択です。
方針
DPをします。
遷移を考えます。
通常であれば、以下のようなコードで済みます。
dp[i+1][j]+=dp[i][j]; dp[i][j+1]+=dp[i][j];
しかし今回の場合、進み方に制限がかかっているため無闇に上や右に進めません。
状態を持たせる
過去２回分の進行方向を状態として持たせます。
連続で「直進」している場合には、「直進」「曲がる」の両方を選べますし、
過去２回の進行方向が異なる場合には「曲がった」ということになるので、「直進」にのみ遷移できます。
//2回前の進行方向をlast_last_direction、１回前の進行方向をlast_directionとする //縦方向の移動→０、横方向の移動→１とする //配列のサイズは多めに宣言しておく int w_max=110, h_max=110, last_last_direction=3, last_direction=3; int dp[w_max][h_max][last_last_direction][last_direction];
（これは後で気づきましたが、状態はわざわざ２次元用意する必要はなく、
０：横横
１：横縦
２：縦横
３：縦縦
とかにすれば１次元でも十分機能するはずです。bit探索的な考え方ですね。）
なお、問題文上では、
JOIさんは，通勤時間を短くするため，東または北にのみ向かって移動して通勤している．
というように進行方向を示していますが、この記事では便宜上、東向きを「横方向」、北向きを「縦方向」と呼びます。上下も左右も区別しません。
遷移
現在の位置（ｉ、ｊ）は４つの状態を持ちます。
そのそれぞれの状態について、どこから遷移されてくるかをそれぞれ考えます。
状態は以下のように表せました。
dp[i][j][0][0] dp[i][j][1][0] dp[i][j][0][1] dp[i][j][1][1]
まず縦方向の移動から考えます。
縦は０を表すので、dp[ i ][ j ][ k ][ 0 ]が遷移先となります。（last_directionが縦を表している）
dp[i][j][0][0]+=dp[i-1][j][0][0]+dp[i-1][j][1][0]; dp[i][j][1][0]+=dp[i-1][j][1][1];
- dp[ i ][ j ][ 0 ][ 0 ]は縦縦となるため、遷移元が１つ前の交差点で曲がった場合でも受け入れられます。
しかし、２回前の操作も縦方向の移動である必要があるため、例えばdp[ i-1 ][ j ][ 0 ][ 1 ]は受け入れられません。 - dp[ i ][ j ][ 1 ][ 0 ]は横縦です。つまり「曲がる」を選択したので、その前の操作としては「直進」を連続で選んでいる場合のみ認められます。この時の直進は横移動です。
横方向へ移動する遷移も同様に書けます。
dp[i][j][1][1]+=dp[i][j-1][1][1]+dp[i][j-1][0][1]; dp[i][j][0][1]+=dp[i][j-1][0][0];
初期化を考える
考えます。
初期位置は通常１を置きます。（初期位置への経路は１通りなので）
ですが今回の場合は、１つの位置が４つの状態を持っています。
ややこいので初期位置dp[ 0 ][ 0 ][ last_last_direction ][ last_direction ]は飛ばします。
| h\w | 0 | 1 | 2 |
|---|---|---|---|
| 0 | ? | ? | |
| 1 | ? | ||
| 2 | ? | ||
| 3 | ? |
？の部分について考えます。
結論から言うと、？＝１です。直進するしかないからです。
問題はこの１をどの状態に置くべきかということです。
端を進むだけなので進行方向は常に同じです。
[ 0 ][ 0 ] あるいは[ 1 ][ 1 ]に入れるのがよいでしょう。（ここらへんでｗを高さ、ｈを横幅としてコーディングしていることに気づく）
for(int i=1;i<w;i++) dp[i][0][0][0]=1; for(int i=1;i<h;i++) dp[0][i][1][1]=1;
横横、縦縦の状態に入れておくことで「直進」「曲がる」どちらでも選べるようになります。
その他の状態は０でよいです。
ここまでを一旦実装します。
#include<bits/stdc++.h> using namespace std; int dp[110][110][3][3]; int ans[110][110]; main() { int w,h; cin>>w>>h; for(int i=1;i<w;i++)dp[i][0][0][0]=1; for(int i=1;i<h;i++)dp[0][i][1][1]=1; for(int i=0;i<w;i++) { for(int j=0;j<h;j++) { if(i==0||j==0)continue; //初期化ずみ if(i>0) { dp[i][j][0][0]+=dp[i-1][j][0][0]+dp[i-1][j][1][0]; dp[i][j][1][0]+=dp[i-1][j][1][1]; } if(j>0) { dp[i][j][0][1]+=dp[i][j-1][0][0]; dp[i][j][1][1]+=dp[i][j-1][1][1]+dp[i][j-1][0][1]; } } } //4つの状態を1つにまとめる for(int a=0;a<2;a++)for(int b=0;b<2;b++)for(int i=0;i<w;i++)for(int j=0;j<h;j++) { ans[i][j]+=dp[i][j][a][b]; } //debug for(int a=0;a<2;a++)for(int b=0;b<2;b++) { printf("[%d][%d]\n",a,b); for(int i=0;i<w;i++) { for(int j=0;j<h;j++) { cout<<dp[i][j][a][b]<<" "; } cout<<endl; } cout<<endl; } for(int i=0;i<w;i++) { for(int j=0;j<h;j++)cout<<ans[i][j]<<" "; cout<<endl; } }
入力例１の3 4を投げてみます。
3 4 [0][0] 0 0 0 0 1 0 0 0 1 1 1 1 [0][1] 0 0 0 0 0 1 0 0 0 1 1 1 [1][0] 0 0 0 0 0 1 1 1 0 0 1 1 [1][1] 0 1 1 1 0 0 1 1 0 0 1 2 0 1 1 1 1 2 2 2 1 2 4 5
このようになります。5つ目のテーブルの右下が答えです。
なお、今回の問題では、100,000で割った余りを出力するよう求められます。
w=49, h=49くらいでlong longを超えるからです。
const int mod=1e5; dp[i][j][0][0]+=(dp[i-1][j][0][0]+dp[i-1][j][1][0])%mod;
cout<<ans[w-1][h-1]%mod<<endl;
というようにこまめにmodを取ってあげるとよいでしょう。int型で十分動くようになります。
提出コードはこちらです。
解説はここまでで以上になります。
ここまでお読みいただいた方、ありがとうございました。
