E - Existence Counting 解説
by 
physics0523
ヒント
Hint 1
ひとまず地道に手で数え上げることを考えてみましょう。
この問題の答えをできるだけ楽に数え上げたい場合、どのようにすれば良いでしょうか?
Hint 2
\(N=6, K=4, P=(4,6,5,1)\) の場合を考えてみましょう。
手で数えようとしたとき、まず以下のものを取り扱うはずです。
その次に取り扱うものは以下の通りであるはずです。
- 辞書 \(s\) に含まれる、接頭辞が \((4,1)\) である列
- 辞書 \(s\) に含まれる、接頭辞が \((4,2)\) である列
- 辞書 \(s\) に含まれる、接頭辞が \((4,3)\) である列
- 辞書 \(s\) に含まれる、接頭辞が \((4,5)\) である列
Hint 3
Hint 2 の手順を「再帰的」に行うことで、答えを手で数え上げることはできるはずです。
これをコードを書いて実現できるように、詳細な分析を行いましょう。
Hint 4
Hint 2 にて、次のことを書きました。
\(N=6, K=4, P=(4,6,5,1)\) の場合を考えてみましょう。
手で数えようとしたとき、まず以下のものを取り扱うはずです。
- 辞書 \(s\) に含まれる、先頭が \(1\) である列
- 辞書 \(s\) に含まれる、先頭が \(2\) である列
- 辞書 \(s\) に含まれる、先頭が \(3\) である列
このとき、 \(1,2,3\) と \(4,5,6\) でそれぞれ等しい値を加算したはずです。(ここで加算する値を立式することはそう難しくありません)
そして、このような加算にフレンドリーなデータ構造を我々は知っているはずです。
Hint 5
Hint 2 にて、次のことも書きました。
その次に取り扱うものは以下の通りであるはずです。
- 辞書 \(s\) に含まれる、接頭辞が \((4,1)\) である列
- 辞書 \(s\) に含まれる、接頭辞が \((4,2)\) である列
- 辞書 \(s\) に含まれる、接頭辞が \((4,3)\) である列
- 辞書 \(s\) に含まれる、接頭辞が \((4,5)\) である列
このとき、 \(1,2,3,5\) と \(6\) でそれぞれ等しい値を加算したはずです。
\(4\) が歯抜けていますね。どうすればよいですか?
Hint 6
Hint 5 に至った時点で、調べていない列の先頭は必ず \(4\) です。言い換えると、これ以降に考える辞書 \(s\) 中の列はすべて \(4\) が含まれることになります。
Hint 7
漠然としたヒントを追加します。
\(P\) に \(4\) が出現した時点で、それ以降考える列には必ず \(4\) が出現するので、それ以降の \(4\) の取り扱いはかなりどうでもよいです。
しかし、最終的な求値では辞書 \(s\) 中の \(4\) から始まる列はどうでもよくないので、どこかで処理する必要があります。
Hint 8
Hint 3 と Hint 7 を紐づける時が来ました。
Hint 7 中の「処理」を「再帰」で片づけられないでしょうか?
投稿日時:
最終更新: