AGC43 A問題をC++で解く

タイトルの通りAGC43 A問題をC++で解いた話です。
問題のリンク

今回はDP(動的計画法)を用いた解法を説明していこうと思います。

注意事項

この記事は筆者なりの解法を説明しています。
筆者は初心者です(重要)。
よって高度な解法は出来ないため効率が良い解き方などを求めている方だとあまり参考にならないと思います...
また、DPに関して筆者も現在勉強中のため一部内容に不備があるかもしれません。
その時はコメントやTwitterのDMなどで連絡していただけると幸いです。
Twitterのリンク

考察を行う前に

今回与えられた問題を要約すると、左上のマスから右下のマスまで最も少ないコストを用いて移動するときそのコストを求めるというものです。

ポイントは常に右か下にしか移動できないという点です。
これを言い換えると、ある点を(i,j)とするとその点に遷移することが出来るのは、
(i-1,j)か(i,j-1)の2点しか存在しないということです。( 0 < i,j )

そして今回入力例にはない重要なパターンがあります。
具体例を挙げます。


このような入力が与えられた時、右下までの最短コストは1です。
以下の長方形の部分の色を1回変更することによって右下まで移動することが出来ます。


これからわかる情報としては、#が連続している部分を通るルートが最もコストが低い場合も存在するということです。

考察

先程の、入力をもう一度用います。

最短経路について考察します。
最短経路は以下の画像の通りになります。

これを文字列として表現すると、
####.
となります。
この場合のコストは1です。

次に,以下の画像のようなルートを考えます。

これを文字列として表現すると、
#..#.
となります。
この場合のコストは2です。

もう一つ別のルートを考えてみます。

これを文字列として表現すると、
##.#.
となります。
この場合のコストは2です。

以上の3つの例から、ある経路に対するコストは、
連続している#を1つの#に置き換えた後の文字列のうち、#の個数
ということがわかります。

DPとして考える

そしてやっとDPの登場です。
今回用いるDPは、
dp[i][j] = 点(i,j)に移動するまでにかかる最小コスト
とします。
そして、最小コストを求めるので、dpの初期値は大きい値に設定します。
また、dp[0][0]を以下のように設定します。

 //s[0][0]が#の時
 dp[0][0] = 1
 
 //それ以外
 dp[0][0] = 0

そしてDPの更新式についてです。
今回の更新式は大まかに2種類に分けることが出来ます。

( i > 0 の時 )

 //s[i][j]が#の時かつs[i-1][j]が.の時
 dp[i][j] = min( dp[i][j], dp[i-1][j] + 1 )

 //それ以外
 dp[i][j] = min( dp[i][j], dp[i-1][j] )

( j > 0 の時 )

 //s[i][j]が#の時かつs[i][j-1]が.の時
 dp[i][j] = min( dp[i][j], dp[i][j-1] + 1 )

 //それ以外
 dp[i][j] = min( dp[i][j], dp[i][j-1] )

この更新式を用いて以下の例を解いてみます。


1列目

 dp[1][2] = min( dp[1][2], dp[1][1] )
 // dp[1][2] = 1
 
 dp[1][3] = min( dp[1][3], dp[1][2] )
 // dp[1][3] = 1
 

2列目

 dp[2][1] = min( dp[2][1], dp[1][1] )
 // dp[2][1] = 1
 
 dp[2][2] = min( dp[2][2], dp[1][2] )
 dp[2][2] = min( dp[2][2], dp[2][1] )
 // dp[2][2] = 1

 dp[2][3] = min( dp[2][3], dp[1][3] )
 dp[2][3] = min( dp[2][3], dp[2][2] )
 // dp[2][3] = 1
 

3列目

 dp[3][1] = min( dp[3][1], dp[2][1] )
 // dp[3][1] = 1
 
 dp[3][2] = min( dp[3][2], dp[2][2] + 1 )
 dp[3][2] = min( dp[3][2], dp[3][1] + 1 )
 // dp[2][2] = 2

 dp[3][3] = min( dp[3][3], dp[2][3] )
 dp[3][3] = min( dp[3][3], dp[3][2] + 1 )
 // dp[3][3] = 1
 

のようになります。テーブルは以下のようになります。

最後に

筆者のコード