Grenache's blog

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

カテゴリ: DP(動的計画法)

問題概要

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

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

解法

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)]]$

考察

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

問題概要

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

$n=300$なので、$O(n^3)$でもOKと気楽に考えられるようになりたいものです。

解法

文字列の問題は何となく$rec(0,n)$という再帰関数を呼び出したら答えが求まるようなイメージがあります。

$O(n^3)$なので、$rec(i,j)$ですべての組み合わせ(ただし、$j>i$)を試しても、$O(n^2)$でまだ余裕あります。なので、1文字ずつずらして文字列を2つに分割して文字列を消せる回数の最大値を調べていきます。(これで$O(n^3)$)

$$rec(i,j)=\max\{rec(i,k)+rec(k,j):k=i+1,i+2,...,j-1\}$$

これに、文字が消せる場合の処理を加えないといけません。3文字で"iwi"の時は簡単ですが、4文字以上の時は文字列の一部が消えたときの残りがどうなるのかというのも考慮しないといけません。こう考えると、全部消えてしまう場合、右に1文字残る場合、左に2文字残る場合など、いろいろ複雑な気がします。ただ、上記の再帰の式で1文字ずつずらして比較しているというのを考慮すると、実はすべて文字列が消えてしまう時だけを考慮すると、うまくいくということに気づきます。(自分で気づけたわけではないですけど)

ある文字列がすべて消えてしまう条件は以下のようになります。

  1. 文字列の長さが3の倍数
  2. 両端はいずれも'i'
  3. 両端の'i'と中にある'w'との間の文字列が消えてしまう

このように文字列がすべて消えてしまう(文字列の長さが3の倍数)時だけ特別な処理をすればいいと思いつけるかどうかで大きな差がつくんだなと実感しています。

漸化式の定義: $$\begin{eqnarray} rec(i,j) & = & \max\{rec(i,k)+rec(k,j):k=i+1,i+2,...,j-1\}\\ rec(i,j) & = & j-i\ (ただし次の条件を満たす場合) \end{eqnarray}$$

(1)$j-i$が3の倍数、(2)$s[i]=s[j-1]='i'$、
(3)$s[l]='w'$の時、$rec(i+1,l)=l-i-1\ $(文字列$s$の$[i+1,l)$の間が全部消える)かつ $rec(l+1,j-1)=j-1-l-1\ $(文字列$s$の$[l+1,j-1)$の間が全部消える)が成り立つ場合

$rec(i,j)$:文字列$s$の$[i,j)$の範囲において、消すことができる文字列の数。(一回やると分かったのですが消せる回数ではなく、消せる文字数のほうが扱いやすい。答えの時1/3する。)
$(0\le i \lt n,\ 0\le j \le n,\ i+1\le l \lt j-1,\ n:文字列$s$の長さ)$

求める解:$rec(0,n)/3$

もちろん、メモ化は必要です。(3)のところで文字列$s$の$[i,j)$の間の'w'を調べるので、結局$O(n^3)$のままです。

まずメモ化再帰で考えたのは、ボトムアップによるDPの場合、どこから計算するべきかがわからなかったからです。ここまで考えると、実は短い文字列から求めるとうまくいくというのがわかりました。ボトムアップのDPで漸化式を考えると次のようになります。

漸化式の定義: $$\begin{eqnarray} dp[i][j] & = & \max\{dp[i][k]+dp[k][j]:k=i+1,i+2,...,j-1\}\\ dp[i][j] & = & j-i\ (ただし次の条件を満たす場合) \end{eqnarray}$$

(1)$j-i$が3の倍数、(2)$s[i]=s[j-1]='i'$、
(3)$s[l]='w'$の時、$dp[i+1][l])=l-i-1\ $(文字列$s$の$[i+1,l)$の間が全部消える)かつ $dp[l+1][j-1]=j-1-l-1\ $(文字列$s$の$[l+1,j-1)$の間が全部消える)が成り立つ場合

$dp[i][j]$:文字列$s$の$[i,j)$の範囲において、消すことができる文字列の数。
$(0\le i \lt n,\ 0\le j \le n,\ i+1\le l \lt j-1,\ n:文字列$s$の長さ)$

初期値:全て0

求める解:$dp[0][n]/3$

ループの向き:文字列の長さが2文字以下の場合は消せる文字数は0になるので、処理は不要。$j-i$が3になる$i,j$の組み合わせから、$j-i$が$n$まで増えるループを回す。

最後のループの向きのところは次のような感じです

for (int len = 3; len <= n; len++) {
  for (int i = 0; i + len <= n; i++) {
    int j = i + len;
    dp[i][j]=......
  }
}

考察

再帰の時のオーダーの計算がぱっとわからないので、最初の漸化式のように1文字ずつずらして大丈夫なのかと思って躊躇してしまいます。案外愚直に試していくのがうまくいくこと多いですよね。なんかひらめきがないとだめだと思ってしまう。。。

問題概要

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

ナップサック問題の変形です。

解法

ナップサック問題の変形というと、個数制限なしのナップサック問題(参考書籍の蟻本に出てきます)などが典型かと思いますが、漸化式の変更をする必要がありました。

この問題も色というちょっとした制限の追加だけで、解けそうで解けなくなってしまいます。ただ、DPに慣れてくると$i$番目までのもので使った色の種類が$c$以下となり重さの合計が$w$以下というまとめ方になるんだろうなというのはわかってくると思います。これをどう実装するかが難しいんですけど。。。

通常のナップサック問題では$i$番目のものまでを使ってと考える時に、$i-1$番目までのものにしか依存しないので、実際には$dp[W]$という1次元の記憶領域しか必要としません。今回も、何番目までのものを使ったのかは領域を使いまわせると仮定して、$i$種類以下の色を使って、重さの合計が$j$以下の時の価値の最大値を$dp[i][j]$で表すと考えてみます。もし、これが求められたら、答えは$dp[C][W]$になります。

これをどうやって求めるかですが、それまで使ったことがない色のものを考える時に、$i\lt C$の$dp[i][j]$を使って、通常のDPを行うと$C$種類以下の色のものでの最大価値が求まります。ただ、新しく考えるものの色をすでに使ったことがある場合は、$i\le C$の$dp[i][j]$を使ってDPを行う必要があります。これを実現するために2つの漸化式をたてます。

漸化式の定義: $$\begin{eqnarray} dp2[i][j] & = & \max\{ dp2[i][j],\\ & & dp[i-1][j - w_k]+v_k,\\ & & dp2[i][j - w_k]+v_k\} \end{eqnarray}$$ $$dp[i][j] = \max\{dp[i][j],\ dp2[i][j]\}$$

$dp[i][j]$:$i$種類以下の色のものを使って、合計の重さ$j$以下となる組合せでの価値の合計の最大値

$dp2[i][j]$:$dp[i][j]$で使ってない色のものを組合せとして考える場合に、その新色を含めて$i$種類以下の色のものを使って、合計の重さ$j$以下となる組合せでの価値の合計の最大値

$k$:$k\in\{dp[i][j]に含まれていない色c_lのものの集合\}$
$(0\le i \lt C,\ 0\le j \le W)$

初期値:全て$0$

求める解:$dp[C][W]$

この2つの漸化式は、次の手順で計算をしていきます。

  1. 色が$c_l$のものについて$dp2$を更新する(この時$j$は$W$から減らす方向でループを回す)。
  2. $dp$を更新する
  3. 次のまだ使っていないものの色について1.から繰り返す。

このような手順を踏むことで、1.が終わった時点では色が$c_l$のものを使いかつ$C$種類以下のものの組み合わせでの価値の合計の最大値が$dp2$に入っています。それを2.によって$dp$とマージすることで、$dp$に(どの色の組み合わせかは問わずに)$C$種類以下のものの組み合わせでの価値の合計の最大値が入っています。

考察

漸化式を2つ使うというか、領域を2つ使う点では桁DPに似ているのでしょうか。こういう問題をきっちりと解けるようになりたいです。

問題概要

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

何度復習しても解き方を忘れてしまいます。Javaなんですが、MLEでも苦労しました。

解法

辞書順で$K$番目のものを求めるので、'a'~'z'のそれぞれで始まる部分列の個数がわかると、その和が$K$を超えた時点の文字で始まるのが$K$番目のものだとわかります。同様に、その文字で始まる部分列の中で、全体で$K$番目にあたるものを、その文字を除いた部分列の個数の中から探せます。

つまり、文字列を先頭(左)から見ていって、例えば'a'が現れないうちは、それ以降の文字列から'a'で始まるものの数と同じになります。初めて$i$文字目に'a'が現れたとし、$i+1$文字以降の文字列からそれぞれ'a'~'z'で始まる部分列の数がわかっているとしたら、それの先頭に'a'を足した新しい部分列ができるので、それらの数を足したものになります。ただし、$i+1$文字以降で{'a'}という部分列があった場合、それに'a'を足した{'a','a'}という部分列としてカウントしているので、{'a'}という部分列分、1個増えることになります。

従って、文字列$s$の先頭から$i$文字目以降で、$j$という文字から始まる部分列の数を考えると、次のようになります。

漸化式の定義: $$dp[i][j-'a\ ']= \begin{cases}\displaystyle 1+\sum_{k='a\ '}^{'z\ '}dp[i+1][k-'a\ '] & (j=s[i])\\ dp[i+1][j-'a\ '] & (j\ne s[i]) \end{cases}$$

$dp[i][j-'a\ ']$:$i$文字目以降で、$j$という文字から始まる部分列の数
$(0\le i \le N,\ 'a\ '\le j \le 'z\ ')$

初期値:$i$は0-indexedとしたときに、$dp[N][j]=0$(全て0)

答えとなる部分列の求め方ですが、以下の方法で求めます

  1. 'a'から順番にその文字で始まる部分列の数を$K$から引いていく
  2. $K$を超えるところで、答えとなる部分列にその文字を加える
  3. その文字が現れるところまで$i$を進める
  4. $K$から1を引いて(上記で説明したその文字1文字だけの部分列分)次の文字から同様に1から繰り返す

もし、先頭の文字が'z'までいっても$K$を超えなければ答えは"Eel"となります。

途中で部分列の数はlongでもオーバーフローすると考えられるので、対策が必要です。$K$番目がどれかを探せばいいので、$K+1$以上の数は計算する必要がありません。$INF=K+1$として、それ以上は計算しないという対策をしました。

この辺はソースコードを見るか、ちゃんとフローチャートとか書かないと分かりにくいですね。。。

考察

同じ問題が出たとしても、解ける気がしません。その時は、このページを見ながら解きます。

ちなみに、JavaではMLEになりました。文字列が$10^5$を超えるので、自前でBufferedReaderをかまして読み込みをしているのですが、そのバッファサイズを減らさないとMLEになるくらいシビアな問題でした。

このページのトップヘ