Grenache's blog

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

2015年08月

問題概要

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

AtCoderのTypical DP ContestはDPの練習にお勧めです。難しい問題が多いですが、理解してみると典型的なDP問題が多く含まれています。今だに全部は解けていませんけど。。。

解法

$i-1$問目までの問題からできる合計点の集合がわかれば、それに$i$問目の配点$p_{i}$を足してできる合計点と、足さずにできる合計点を考えることで、$i$問目までの問題からできる合計点の集合がわかります。この時、合計点が同じであればどの問題の組み合わせによって出来た点数なのかが関係なくなっているため、解くべき部分問題を減らすことができています。

このままコーディングに入っても構わないんですけど、漸化式をちゃんと考えないとうまくできないことが多いので、定義してみます。

漸化式の定義: $$dp[i][j]=\begin{cases} dp[i-1][j]\lor dp[i-1][j-p_i] & (j\ge p_i) \\ dp[i-1][j] & (j\lt p_i) \end{cases}$$

$dp[i][j]$:$i$問目までの問題を使って、$j$点の合計点ができるかどうかの真理値
$(0\le i \le n,\ 0\le j \le MAX,\ $ $MAX$:合計点として考えられる最大値$\displaystyle \sum_{i} p_i)$

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

求める解:$dp[n][j]$が$1$となる要素数

ここではいわゆる「貰うDP」で、$i$のループは$1$から$n$に増える方向で漸化式を考えましたが、配るDPや、$i$のループが逆でも考えることができます。この辺の、同じDPでもいろいろな解法があるのことが、なかなか直感的にDPの問題が解けない1つの要因かなと思ったりしています。

ちなみに、この漸化式だと$j$のループを$MAX$から減る方向に回すことで、配列は1次元で済みます。こういう事を考え出すとますます難しくなる。。。

考察

動的計画法は次の2つの特徴がある場合に適用できます。

  1. 問題が、その問題よりも小さい部分問題を用いて解くことができる(部分構造最適性
  2. 同じ部分問題を繰り返し解く(部分問題重複性

この問題でいえば、

  1. $i$問目までの答えが、$i-1$問目までの答えから得られる。
  2. 合計点が$j$点と同じであれば、どの問題の組み合わせによる合計点かにかかわらず答えは同じなので、$2^N$の組み合わせが、合計点の最大値(この問題の条件だと10000)に抑えられる(くらい重複している)。
という特徴を満たしていることになります。

この辺が感覚的につかめてくるともっと問題が解けるようになるのかもしれませんが、わからない場合はここに立ち返るようにしています。

問題概要

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

期待値の線形性を使うと簡単な問題です。

解法

1個のサイコロで考えると、問題文中にあるように期待値の定義$\displaystyle \mathrm{E}[X]=\sum_{x}x\cdot \Pr\{X=x\}$を使って計算できます。

求める期待値の確率変数を定義します。

$X$:1個のサイコロを振って出る目

$X$の確率分布を表で表します。

出る目の数$X$ 1 2 3 4 5 6 合計
確率 $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ 1

したがって、1個のサイコロを振って出る目の期待値は $$\mathrm{E}[X_i]=1\cdot \frac{1}{6}+2\cdot \frac{1}{6}+3\cdot \frac{1}{6}+4\cdot \frac{1}{6}+5\cdot \frac{1}{6}+6\cdot \frac{1}{6}=\frac{21}{6}=3.5$$ となります。

次に、この問題で求める期待値の確率変数を定義します。

$Y$:n個のサイコロを振って出る目の合計

ここで、

$X_i$:i番目のサイコロの出る目

と定義すると、確率変数$Y$は$X_i$の和で表すことができます。 $$Y=X_1+X_2+...+X_n$$

このように求めたい期待値の確率変数を、別の確率変数の和で表すということを考えると、期待値の線形性を用いることができます。求めたい$Y$の期待値$\mathrm{E}[Y]$は下記のようになります。 $$\mathrm{E}[Y]=\mathrm{E}[X_1+X_2+...+X_n]=\mathrm{E}[X_1]+\mathrm{E}[X_2]+...+\mathrm{E}[X_n]$$ $\mathrm{E}[X_i]$は上記で求めた「1個のサイコロを振って出る目の期待値」と何ら変わりはないので、$\mathrm{E}[Y]=n\cdot \mathrm{E}[X]=n\cdot 3.5$となります。

考察

期待値の線形性を知ったときは目からうろこで、とても感激しました。ただ、これは高校時代に数学で習ったはずのことで、完全に忘れてしまっていたようです。。。

ちなみにこの問題を期待値の定義を使って解こうとすると下記のような感じになるのでしょうか。

$Y$:n個のサイコロを振って出る目の合計

これの確率分布を表で表すと

出る目の合計$Y$ n n+1 n+2 ... 6n-1 6n 合計
確率 $\frac{1}{6^n}$ $\frac{n}{6^n}$ $\frac{???}{6^n}$ ... $\frac{n}{6^n}$ $\frac{1}{6^n}$ 1

のようになります。この確率を求める公式もあるようですが、理解できませんでした。nが小さければ、全探索で計算することもできるようです。でも、期待値の線形性を知っていれば簡単という典型問題です。

競技プログラミングを初めてしばらく経ちますが、なかなか初心者の域を抜け出せません。 過去問を解いて、わからなければ先輩の方々が書かれた解説ブログを読むのですが、それでも理解できないものが多いです。特に、DP(動的計画法)期待値関連の問題です。

そこで、自分が解けた問題については初心者でも理解できるように、詳しい解法を残していきたいと思います。 わかりにくい部分があれば、いろいろ追記していくつもりです。

ちなみに、解法の解説のみで、ソースコードの掲載は省いています。

このページのトップヘ