Grenache's blog

競技プログラミング初心者です。

競技プログラミング初心者の方が動的計画法(DP)を勉強するのにお勧めの問題があります。AtCoderで開かれた「Typical DP Contest(tdpc)」です。2013年8月と結構昔に開催されたのですが、今でもたくさんの方が解いています。

このコンテストは、そもそもが「動的計画法の練習をすることを目的」として開催されて、「出題される問題はすべて(他のコンテストで使用できないほど)典型的なDPの問題です」とあるように、ちゃんと理解してみるとDPに関する典型的なテクニックをたくさん学べるとてもいいコンテストだと思います。ただ、難易度は高くて(TopCoder SRM d2 hard程度のものが多いとのこと)、初心者にとってはハードルが高いです。作者の方が一言ヒントをつぶやかれたり、いろいろな方がブログで解説を書かれていますが、一回読むだけではなかなか理解するのが難しいものが多いです。

そこで、競技プログラミング初心者の人にもわかりやすい解説を目指してこのブログを作成しました。もしわかりにくいところなどがあれば指摘していただけるとありがたいです。

また、自分にとってわかりやすかったと思われる他の方のブログも紹介させていただきます。あくまでも私にとってわかりやすかった記事ですので、そのほかにもいろいろ検索して勉強することをお勧めします。

問題概要解説ブログ
A コンテスト基本的な2次元のDPGrenache
B ゲームゲームの最善手Grenache
kagamizさん
C トーナメント確率Grenache
simeji_tanさん
D サイコロ確率、4次元のDP、素因数分解Grenache
kmjpさん
E 数組合せの数、桁DPGrenache
kmjpさん
tshitaさん
F 準急組合せの数、累積和Grenache
mayokoさん
G 辞書順組合せの数、文字列の部分列Grenache
simeji_tanさん
osakさん
H ナップザックナップサック問題の変形、最大値Grenache
kagamizさん
kmjpさん
I イウィ最大値、文字列Grenache
osakさん
???
J ボール期待値、bitDPGrenache
kagamizさん
K ターゲット最大値、LIS、幾何Grenache
kmjpさん
L 猫和の最大値、累積和Grenache
simeji_tanさん
kmjpさん
M 家組合せの数、巡回セールスマン問題(TSP)、
bitDP、行列累乗
Grenache
simeji_tanさん
N 木組合せの数、逆元、パスカルの三角形Grenache
kmjpさん
simeji_tanさん
O 文字列組合せの数Grenache
simeji_tanさん
hadroriさん
P うなぎ組合せの数、木構造Grenache
osakさん
shifthさん
Q 連結組合せの数、文字列、配るDPGrenache
osakさん
shifthさん
R グラフ
S マス目
T フィボナッチ

まだすべての問題を解けていないのですが、解けたらブログに書きたいと思います。

問題概要

問題文はこちらを参照してください。

苦手なタイプの問題です。

解法

DPは前提だとして考えると、部分問題を設定しないといけません。$i-1$番目までの猫で得られる幸福度の総和がわかっているとします。そこに、$i$番目の猫を加えたときに増える幸福度は、猫$i$がすでにいた猫のうち、どの猫と距離1以内なのかによります。$j$番目の猫までと距離1以内とすると、$j\le i$という条件で、$j,j+1,...,i-1,i$番目までの猫もすべて距離1以内になるはずです(自分自身も含めています)。なので、猫$i$の幸福度は$\displaystyle \sum_{l=j}^{i}f_{i,l}$となり、すでにいた$j~i-1$までの猫の幸福度がそれぞれ猫$i$との仲のよさ分増えるので、結局猫$i$の幸福度の分の2倍、$\displaystyle 2\cdot\sum_{l=j}^{i}f_{i,l}$増えることになります。

ここで出てきた、すでにいる猫の(左側の)どこまで距離1以内なのかという条件を付けて部分問題を考えると、猫$i$は猫$j$までが距離が1以内とすると、猫$i$よりも左にいる猫$i-1$は、必ず、猫$j$かそれよりも左にいる猫まで距離1以内のはずです。

なので、猫$i-1$が$j,j-1,...,1$番目の猫まで距離1以内の時の幸福度の最大値に、$i$番目の猫を加えたときに増える幸福度を足して最大になるような幸福度の総和を求めればよいことになります。

配列でイメージを示すと以下のようになります。

typicalDPL
漸化式の定義: $$dp[i][j]=\begin{cases} \max\{dp[i-1][k]+\sum_{l=j}^{i}f_{i,l}:k=1,2,...,j\} & (j\lt i)\\ \max\{dp[i-1][k]:k=1,2,...,j-1\} & (j=i) \end{cases}$$

$dp[i][j]$:$i$番目までの猫で、猫$i$から猫$j$までが距離1以内のときの幸福度の総和の最大値。($j=i$の時は猫$i$を加えても全体の幸福度は増えないので$i-1$番目までの猫での幸福度の最大値と同じ)

$f_{i,j}$:猫$i$と猫$j$の仲のよさ。

$(1\le i \le n,\ 1\le j\le i)$

初期値:$dp[1][1]=0$

求める解:$2\cdot dp[n][j]$の最大値$(1\le j\le n)$

漸化式の中で、$k$と$l$は別にループが回せるので、これで$O(n^3)$になり、このままではまだ駄目です。

図の中の1)の部分ですが、$l$を$i$から$j$の方向に累積和を考えることで、$\displaystyle sum[i][j]=\sum_{l=j}^{i}f_{i,l}$という$sum[i][j]$を$O(n^2)$で事前に計算することができます。

図の中の2)の部分ですが、$dp[i][j]$を猫$i$からの距離が1以内の猫が、猫$j$かそれよりも左の場合の幸福度の最大値、つまり上記の漸化式で$dp[i-1][j]=\max\{dp[i-1][k]:k=1,2,...,j\}$と定義しなおすと、$dp[i][j]=\max\{dp[i][j-1], dp[i-1][j]+sum[i][j]\}(j=1,2,...)$と更新していくことで、$k$のループを回す必要がなくなります。

これらを踏まえて漸化式を書き直すと$O(n^2)$で解けます。

漸化式の定義: $$dp[i][j]=\begin{cases} \max\{dp[i][j-1],\ dp[i-1][j]+sum[i][j]\} & (j\lt i)\\ \max\{dp[i][j-1],\ dp[i-1][j-1]\} & (j=i) \end{cases}$$

$dp[i][j]$:$i$番目までの猫で、猫$i$から猫$1$~猫$j$のどれかまでが距離1以内のときの幸福度の総和の最大値。

$sum[i][j]$:猫$i$が猫$j$から自分自身までが距離1以内の時の猫$i$の幸福度。

$(1\le i \le n,\ 1\le j\le i)$

初期値:$dp[1][1]=0$、$dp[i][0]=-INF(1\le i \le n)$(適切な小さな値)

求める解:$2\cdot dp[n][n]$

猫$i$が加わることによって増える全体の幸福度の総和は、猫$i$の幸福度の2倍なのですが、DPの時は2倍せずに最後の解のところで2倍するようにしています。

初期値の$-INF$ですが、最小の仲のよさの最小値が$-1000$、猫が1000匹までなので1匹の幸福度の最小値が$-10^6$、1000匹の総和で$-10^9$までなりそうです。したがって、$-INF$はこれよりも小さい値でなければいけません。

考察

図中の1)の累積和のオーダーを落とすところはわかるような気がするのですが、2)のオーダーの落とし方が結構苦手です。最初解いたとき(解説見た後に)は$O(n^3)$でもACだったのですが、いろいろな解説を見ると$O(n^2)$だということで、この投稿を書く中で何とか理解したつもりです。

問題概要

問題文はこちらを参照してください。

DPの問題として有名なLISを使います。

解法

x軸上の円の列が次々に前の円の内部になければならないということなので、簡単にするため円の右端の座標で降順に並べ替えます。すると、ある円は前の円の左にはみ出すか、内部にあるかのどちらかになります。左にはみ出すということは円の左端の座標が前の円の左端の座標より小さいということになり、内部にあるということは左端の座標が大きいということになります。

ということで、左端の座標の列の中で、増加している部分列の最大サイズを求める問題、つまりLIS(Longest Increasing Subsequence)問題に帰着します。

しかし、この問題では「strictlyに内部」なので、端が接している場合は含めないようにしなければいけません。左端の重なりはLISで解く際にはじくことができますが、右端のみが重なって、左端が重ならないものも省くようにしないといけません。これは最初に右端の座標で並べ替える際に、右端の座標が同じならば左端の座標が大きいほうを先に並べるように(左の座標でも降順)することでLISの時にはじくことになります。

LISについては参考書籍の蟻本などに書かれているので詳細は省きます。$O(n^2)$と$O(n\log{n})$の解法が紹介されていますが、この問題は$O(n\log{n})$の解法でなければいけません。漸化式だけ書いておきます。

漸化式の定義: $$dp[lower\_bound(dp,\ l[i])]=l[i]$$

$dp[i]$:長さ$i+1$の増加部分列の最後の要素の値。同じ長さの増加部分列がある場合はその最小値。

$l[i]$:円の列を円の右端の座標で降順に並べた時の円の左端の座標列

$lower\_bound(dp,\ l[i])$:$dp$の要素の中で、$l[i]$の値以上となる最小のインデックス

$(0\le i \lt n)$

初期値:全て$INF$(適切な大きな値)

求める解:$dp[lower\_bound(dp,\ INF)]]$

考察

こうしてみると簡単な問題に見えるのですが、最初の並べ替えを思いつけるかどうかの積み重ねでしょうか。

このページのトップヘ