問題概要

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

コンテスト後の解説放送中に話題に出たＤＰを使った解法を書きました。数値が$n$以下という制限がないのでいわゆる桁ＤＰというよりは、「AtCoder Typical DP Contest Q 連結」の解説のような1文字ずつ増やしていくＤＰが近いのかなと思います。また、$n$番目の組み合わせを求めるというのは、「AtCoder Typical DP Contest G 辞書順」の解説に出てくるやり方です。

解法

まずは作問者の方の解説に書いてある条件をもとに、この問題を「"3"と"5"からなる長さ$1～L$の文字列のうち、1桁目が"5"であり、各桁の数字の和が3の倍数であるような文字列の組み合わせの中で、$n$番目の数を求めよ」と読みかえます。

このように$i$文字目の状態から$l$のループを回して$i+1$文字目として"3"または"5"のときそれぞれの遷移を配るＤＰで行います。今回はサンプルより最大の文字列の長さが25とわかるので、$i=25$までのＤＰを求めておくことができます。

まずは$n$番目の数が何桁なのかを求めるために、$n$から$dp[i][j][0]$を小さいほうから順に引いていきます。そしてそれが0以下になるところ(小さいほうからの累積和が初めて$n$以上になるところ)が求める桁数になります。この結果は作問者の方の解説では数え上げによって求められていたものと同じです。

桁数と先頭の数がわかったら、その中で$n'$番目の数は何なのかを求めます。上記の例では結局、4文字目が"5"で長さが4の条件を満たす文字列(2つある)の中で1番目の組み合わせを求めることになります。これは4文字目から1文字目までどのような遷移をたどってきたかを戻りながら求める$n'$番目の数を決定していきます。遷移を戻っていくためには決定した数字によって3で割った余りが変化していくところを考えていく必要があります。

考察

この解説ではわかりやすいかと思って$i$文字目が$d[j]$("3"または"5")のときの組み合わせの数という状態を作りました。ちなみにuwiさんの回答では$j$に関する状態は作られていません($dp[i][k]$：$i$文字目までで各桁の数字の和を3で割った余りが$k$の組み合わせの数)。その代り$i$文字目がどちらなのかを決定する際にＤＰの$i-1$の値を使って決定されています。この解説では$i$文字目を決定するためにＤＰの$i$の値を使っています。結局やっていることは一緒だと思います。

問題概要

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

これも「AtCoder Typical DP Contest Q 連結」を考えているときに参考になった問題です。ほぼ、「SRM671 Div1 Easy BearCries」の解説と同じ内容で、情報量少なめです。

解法

「Q 連結」の解説で書いたように、この問題を下記と同じ考え方で解いていきます。

• $i$文字目までの部分問題を使って、$i+1$文字目までの問題を解いている。
• $i$文字目で考えられるすべての状態から、$i+1$文字目で起きうる状態へ配るＤＰで遷移している。
• $i$文字目で考えるべき状態数は、問題の条件に依存する。
• 求める解は$L$文字目で条件に合う状態の値をすべて足したもの。

まずは問題を「'A'~'Z'または'?'からなる長さ$L$の文字列において、"KUROI"の部分列に分解できる最大の個数を求めよ。」と言い換えてみます。('?'は'A'～'Z'のどれかに当てはまる)

この条件を判定するために必要なすべての状態についてですが、1文字ずつ文字を増やしていったときに、部分列は"K"だけ、"KU"、"KUR"と状態が変化をしていきます。これらの個数をカウントすることで全体の状態を管理していきます。

1. "K"だけ(他の文字と組み合わさっていない)が$jk$個ある状態
2. "KU"が$ju$個ある状態
3. "KUR"が$jr$個ある状態
4. "KURO"が$jo$個ある状態
5. "KUROI"の状態の最大値

問題が部分列"KUROI"が最大何個できるのかなので、ＤＰの値としてこの値を更新するようにします。つまり、5.の状態になったらＤＰの値を1増やすという遷移を考えます。'?'の場合は'K','U','R','O','I'のすべての可能性があるとして遷移させます。これら以外の文字は何もしません。

この問題も与えられた文字列によって状態の遷移先が決まっていきます。

「SRM671 Div1 Easy BearCries」と違って、

• 求めるものが組合せの数ではなく、最終形の"KUROI"になる最大の数である。なので、初期値として$-INF$で初期化が必要。
• ワイルドカードの'?'が含まれている。なので、解が最大になるように遷移が追加される。

また、この問題は解説にもあるように次の点に注意が必要です。

• 全体の文字列の長さから"KUROI"は最大20個しかできないので、各文字の状態の管理の上限を20にしても構わない。(だからTLEしない)
• 遷移を発生させない関係ない文字のときは、$i$のときの値が$i+1$のときに移っていかないので、ＤＰの領域を再利用するか、関係ない文字のときも$i$から$i+1$のときに値を遷移させる($dp[i+1][jk][ju][jr][jo]=dp[i][jk][ju][jr][jo]$)必要がある。

考察

後で考えると分かるんですけどね。本番では$100^5$になって間に合わないと思っていました。

問題概要

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

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

考察

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$をかけたものが求める確率です。

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

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