Grenache's blog

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

2015年09月

問題概要

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

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

解法

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

考察

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

問題概要

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

期待値のところで長い間苦労した問題です。

解法

以前、yukicoder No.65で説明した条件付き期待値を使って計算することになります。まずは確率変数を定義します。

$S=\{x_1,x_2,...,x_N\}$(最初に物が置いてある座標の集合)

$S_i\subseteq S$($S$の部分集合)

$X_{S_i}$:集合$S_i$の座標に物が残っているときに、全ての物を倒すのに必要なボールを投げる回数

このような確率変数を定義すると求めたいのは確率変数$X_S$の期待値$\mathrm{E}[X_{S}]$です。

ここで、条件付き期待値の考え方で次にボールをどこに投げるのかによって新しい確率変数$\mathrm{E}[X_{S_i}|Y]$を定義して、その確率分布を示します。

$\mathrm{E}[X_{S_i}|Y]$ $1+\mathrm{E}[X_{S_i-\{x-1\}}]$ $1+\mathrm{E}[X_{S_i-\{x\}}]$ $1+\mathrm{E}[X_{S_i-\{x+1\}}]$ 合計
確率 $\frac{1}{3}$ $\frac{1}{3}$ $\frac{1}{3}$ 1

$Y$:次にボールを座標$x$に投げたときに飛んでいく先の座標

結局、yukicoder No.65と同じように求める期待値は以下になります。

$$\begin{eqnarray} \mathrm{E}[X_{S_i}] & = & \mathrm{E}[\mathrm{E}[X_{S_i}|Y]] \\ & = & 1+\mathrm{E}[X_{S_i-\{x-1\}}]\cdot \frac{1}{3}+\mathrm{E}[X_{S_i-\{x\}}]\cdot \frac{1}{3}+\mathrm{E}[X_{S_i-\{x+1\}}]\cdot \frac{1}{3} \end{eqnarray}$$

ここで、$S_i-\{x\}$は集合$S_i$に$x$という座標が含まれていたらそれを除いた残りの集合という意味ですが、つまりはボールが飛んで行った先の座標にあった物が倒れた後の状態の期待値で表されるということを意味します。しかし、座標$x$にボールを投げたときに、$x-1,x,x+1$それぞれに必ず物があるとは限りません。座標$x$に物がない場合は、$S_i-\{x\}=S_i$となってしまいます。ということは、先ほどの漸化式の右辺にも$\mathrm{E}[X_{S_i}]$が現れるので、式の変形が必要となります。

また、集合$S_i$の要素は0~15の数値で重複はないので、bitDPが使えます。この後は、集合$S_i$を整数$i$にマッピングして表したとします。

漸化式の定義: $$\begin{eqnarray} dp[i] & = & \min\{1+dp[i\ \scriptsize clear\normalsize(x-1)]\cdot \frac{1}{3}+dp[i\ \scriptsize clear\normalsize(x)]\cdot \frac{1}{3}\\ & + & dp[i\ \scriptsize clear\normalsize(x+1)]\cdot \frac{1}{3}:x=1,2,...,14\} \end{eqnarray}$$

$dp[i]$:集合$S_i$の座標に物が残っているときに、全ての物を倒すのに必要なボールを投げる回数の期待値

$i$:集合$S_i$の要素(0~15の値)を$i$のビットの位置とみなして、要素に含まれる座標のビットを1とした場合の整数。ただし、$S_i\subseteq S$なので、$i\ \&\ \tilde{I}=0$が成り立つ$i$のみ。(最初に物がないところのビットが1になっている$i$の時は計算しない)

$i\ \scriptsize clear\normalsize(x)$:整数$i$の$x$番目のビットを0とした場合の整数

$(0\le i \lt I,\ 0\le x \le 15,\ I$:集合$S$の要素(最初に物がある位置の座標)のビットを全て1とした場合の整数)

初期値:$dp[0]=0$、その他は$INF$(適切な大きな値)

求める解:$dp[I]$

$i$のループですが、$S_i\subset S_j$の時には$i\lt j$が成り立つので、小さい値から$i=1~I$のループを回せばよいことになります。

$x$は倒れる確率が3か所とも同じなので、両端の座標0や15に投げる意味がない(倒れる対象が2か所になってしまうので1つ内側の1や14ほうが回数は少なくて済む)のでループに含めません。また、$x-1,x,x+1$全てに物がない場合も投げても意味がない(無駄に回数が増えるだけ)のでその場合は値の更新はありません。もし、$x-1$に物がない場合は$i=i\ \scriptsize clear\normalsize(x-1)$なので、右辺にも$dp[i]$が現れます。したがって、式を変形して$dp[i]=(1+dp[i\ \scriptsize clear\normalsize(x)]\cdot \frac{1}{3}+dp[i\ \scriptsize clear\normalsize(x+1)]\cdot \frac{1}{3})\cdot \frac{3}{2}$となります。$x-1,x$の2か所に物がない場合は、$dp[i]=(1+dp[i\ \scriptsize clear\normalsize(x+1)]\cdot \frac{1}{3})\cdot \frac{3}{1}$です。このように$x$のループを回しながら、$i$の値によっては式の変形もしつつ最小値を求める必要があります。

考察

$dp[i\ \scriptsize clear\normalsize(x)]$みたいな表現しましたが、ビットの操作を表現するのはどう書くのがいいのでしょうか?$\&$とか$|$とかビット演算で表すと、長くなって表現しにくいなと。($dp[i\ |\ \tilde{}(1 << x)]$とか。)

問題概要

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

$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に似ているのでしょうか。こういう問題をきっちりと解けるようになりたいです。

このページのトップヘ