問題概要

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

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

解法

以前、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]$を定義して、その確率分布を示します。

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

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

ここで、$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$にマッピングして表したとします。

$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)$でもＯＫと気楽に考えられるようになりたいものです。

解法

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

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

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

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

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

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

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

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

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

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

考察

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

問題概要

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

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

解法

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

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

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

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

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

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

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

考察

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