Grenache's blog

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

問題概要

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

何度復習しても解き方を忘れてしまいます。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になるくらいシビアな問題でした。

問題概要

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

$O(nk^2)$の解法までしか自分ではわかりませんでした。

解法

制限から$O(n)$の解法でなければならないというのはわかるのですが、どのようにそこにたどりつくのかを考えてみます。

駅$i$までで、駅$i$を含んで連続するちょうど$j$個の駅に止まる組合せを考えると、$j=0$(駅$i$に止まらない)の時は駅$i-1$までに連続して$0~K-1$止まる組合せの和になります。$j\gt 0$の時(駅$i$に止まる)は、駅$i-1$までに連続してちょうど$j-1$止まる組合せと同じになります。

漸化式の定義: $$dp[i][j]= \begin{cases}\displaystyle \sum_{k=0}^{K-1}dp[i-1][k] & (j=0)\\ dp[i-1][j-1] & (j\gt 0) \end{cases}$$

$dp[i][j]$:駅$i$までで、駅$i$を含んで連続する$j$個の駅に止まる組合せ数
$(0\le i \le N,\ 0\le j \le K-1)$

初期値:$dp[1][0]=0$(駅1には必ず止まるので),$dp[1][1]=1(駅0には止まらないという仮定なので)$

求める解:$\displaystyle \sum_{k=1}^{K-1}dp[N][k]$(駅$N$には必ず止まるので$k=0$は含まない)

こう考えると、求める解は$dp[N][0]=0$(駅$N$には必ず止まるので)とすると$dp[N+1][0]=\displaystyle \sum_{k=0}^{K-1}dp[N][k]$と同じということがわかります。

次に、$j\gt 0$のケースの式から、例えば$j=K-1$の時、$dp[i][K-1]=dp[i-1][K-2]=...=dp[i-(K-1)][0]$となって、「駅$i$までで、駅$i$を含んで連続する$K-1$個の駅に止まる組合せ数」は、「駅$i-(K-1)$までで、駅$i-(K-1)$に止まらない組合せ数」と同じという式が得られます。確かに、駅$i-(K-1)$より後連続して駅$i$まで止まる組合せは1通りしかないので、そうなります。これらから、結局$j=0$の時だけ考えればよいということになります。

$j=0$の時の漸化式は結局、$dp[i][0]=\displaystyle \sum_{k=0}^{K-1}dp[i-1-k][0]$となり、駅$i$に止まらない場合の組合せ数を考えればよいということになりました。

さらにさらに、1つ前までの$K$個分の和を求めればいいので、累積和で求めることができます。

漸化式の定義: $$\begin{eqnarray} dp[i] & = & \sum_{k=0}^{K-1}dp[i-1-k]\\ & = & \sum_{j=0}^{i-1}dp[j] - \sum_{j=0}^{i-1-K}dp[j]\\ & = & sum[i-1]-sum[i-1-K]\\ sum[i] & = & \sum_{j=0}^{i}dp[j] \end{eqnarray}$$

$dp[i]$:駅$i$までで、駅$i$に止まらず、$K$個以上連続して止まらない組合せ数
$(0\le i \le N+1)$

初期値:$dp[1]=0,\ dp[N]=0,\ dp[0]=1,\ sum[i]=0(i\lt 0)$

求める解:$dp[N+1]$

考察

あとから考えると、このような説明を付けることはできるのですが、本番ではどのように考えるのがいいのでしょうかね。しかし、いきなり$O(n)$のDPを考えるのはとても無理な気がしているので、わかるところから考えて少しずつ改善していくのが常道なのでしょうか。

あと、実装に関してですが、引き算のmodを取るところがあるので、注意が必要です。

問題概要

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

詳細な解説を作問者の方が既に書かれているので、気になったところだけ書きます。

考察

  1. インディケータ確率変数

    求めたい期待値の確率変数を、期待値の線形性を使って$X\{2\}$などの和で表しています。この1つの数字について生き残れば1、生き残らなければ0という確率変数を定義することで、結局確率を求めればよいとなっています。このような確率変数はインディケータ確率変数という名前で参考書籍で紹介している「数学ガール 乱択アルゴリズム」の中に出てきます。

  2. 条件付き確率

    「2 によって消されない」かつ「3 によって消されない」かつ「4 によって消されない」確率の説明の部分が直感的にわかりませんでした。

    「2 によって消されない」を事象$A$、「3 によって消されない」を事象$B$、「4 によって消されない」を事象$C$とすると、求める確率は$\Pr\{A\cap B\cap C\}$です。ここで条件付確率の乗法定理によって次のようになります。

    $$\Pr\{A\cap B\cap C\}=\Pr\{A\}\cdot\Pr\{B|A\}\cdot\Pr\{C|A\cap B\}$$

    事象$A$と事象$C$が独立ではないので、ちょっとややこしくなっています。$\Pr\{A\}=1-p$、事象$A$と事象$B$は独立なので$\Pr\{B|A\}=\Pr\{B\}=1-p$となります。$\Pr\{C|A\cap B\}$は、事象$A$、$B$が起こったという条件の下での事象$C$(4によって消されない)の確率なので、これも単純に$1-p$になります(事象$A$の2によって消されていないのは前提なので)。

    ということで、結局1と自分自身を除いた約数の個数分$1-p$をかけたものが求める確率です。

    条件付き確率を持ち出したことで余計わかりにくくなった気もするのですが、なかなか直感的に理解できない部分なので、こういうところまで考えないとなんかもやもやが残ります。

    確率変数についても、これを持ち出すと難しく見えますが、実はとても素晴らしい概念だと思います。高校数学の時には全然理解できていませんでしたが、確率変数の概念はおすすめです。

このページのトップヘ