プログラミングコンテストチャレンジブック（通称蟻本）の「分割数」の問題・解説が難しかったため、備忘録的に記事を書いておく。
ちなみに、ググるといくつも記事が見つかるが、一番分かりやすかったのは個人的には下記の記事です。下記の記事を読んで理解できる人には自分が今から書くことはあまり意味ないと思います。
Tech Tips: 分割数を考える
また、もしかしたらまだ勘違いしている部分や誤りがあるかもしれないため、下記で何か気付いたことがありましたらコメント頂けると助かります。
前提知識
自分は理系の大学は出たが、社会人になって数年経っており数学的な知識をかなり忘れてしまった。そのため、問題文や解説に出てくる記載で理解出来なかった部分を最初にいくつか整理する。
分割する
分割数の問題文では「n個の何かをm個以下に分割する」というような記載がある。この文章すら混乱したため整理する。
m個に分割する
まず先に「n個の何かをm個に分割する」を考える。例えば、「4個の何かを2個に分割する」。「個」が2つ出てきて混乱したが、「4個の何かを2つに分ける」というだけの話らしい。その時、均等に分けたりする必要はないので「1個と3個」や「2個と2個」などに分けることが出来る。
ちなみに、この「4個の何か」は問題文にもあるように「互いに区別できない品物」であるため、例えばその4つにそれぞれアルファベットで名前を付けて{a, b, c, d}と考えて「2個と2個」に分けたパターンを{a,b},{a,c},,,というように考えるのは間違っている。「4個の何か」は全て同じもので、それをどう分けるかだけを考える。
そうすると、例えば「4個の何かを2個に分割する方法の総数」を求めると、下記の2パターンだけであり、分割する方法の総数は2となる。
- 1個と3個
- 2個と2個
m個"以下"に分割する
では、元の問題文に戻り「m個以下に分割する」を考える。
例えば「4個の何かを2個以下に分割する」。これはつまり、下記のパターンを考慮するという話だ。
- 4個の何かを2個に分割する
- 4個の何かを1個に分割する
この例であれば、上で既に「4個の何かを2個に分割する」の方法の総数は求めており、残りの「1個に分割する」パターンを求めればよい。また、「1個に分割する」というのは言い直せば「分割しない」ということで、必ず1パターンになる。「4個の何かを1個に分割する」と、4個のままになる。
よって、「4個の何かを2個以下に分割する方法の総数」を求めると 3になる。
注意
自分が勘違いしたのは、例えば「4個の何かを2個以下に分割する」というのが「4個の何かを何人かに配る。その際に1人2個以下になるように分ける」という意味かもしれない、というものだ。
そうすると、例えば4を分ける時に{1,3}と分けると3が2より大きいからダメで、{1,1,2}と{2,2}の2パターンに分ける、みたいな話か？などと勘違いした。
{ai - 1}
数学から遠ざかり過ぎて、これが何を表しているのか全然分からなかったため整理する。
中括弧
まず、中括弧({, })が何を表しているかと言うと、数学でいう集合である。（そんな事も忘れていた）
その為、例えば {ai} と書いたら a の集合を簡略化して書いている訳だ。例えば、「i = 0, 1, 2, 3」の場合、{ai} は {a0, a1, a2, a3} の 4つの何かの集合という意味になる。
解説の中では、nのm分割
a_{i} \Biggl(\sum_{i=1}^{m} a_{i}=n \Biggl)
という話の流れなので、例えば 4の3分割を考えた場合
a_{i} \Biggl(\sum_{i=1}^{3} a_{i}=4 \Biggl)
となり、{ai} = {a1, a2, a3} = {1, 1, 2} みたいな話になる。
また、これも自分が勘違いしていたことだがΣの部分は分かりやすく書くと下記のような話だ。
\Biggl(\sum_{i=1}^{3} a_{i}\Biggl) =4
3つの要素があり、全て合計すると4になるもの。Σの式の中にai=nが入ってると勘違いしていて理解出来なかったが、こうなると分かりやすい。その要素群をaiとして、この後に{ai - 1}の話をしようとしているのだ。（それが全然読み解けなかった。。）
注意
もう一つ自分が勘違いしていた点は、この解説では「jのi分割する想定」でDPの解説が続いていたため、{ai} のiは「i分割」かと思っていた点だ。i分割という意味で考えてしまうと、3分割の時に {a3} となり、その後の {ai - 1} の話が理解できない。
また、例えば4を2分割した場合の {ai} は {1,3} と {2,2} であるが、「この2パターンあるよ！」みたいな情報はΣの式では表現されていない。Σの式では「aiというのは、iが1~mまで（つまり要素がm個）あって、その全ての合計はnです」という事だけが表現されている。
{ai "- 1"}
さて、ではその集合における「-1」とは何なのか。ググり方も良く分からなくて理解に苦しんだのですが、最初に貼った解説を読んで想像できることは下記のような意味である。
{ai} = {a1, a2, a3} = {1, 1, 2} の時、
{ai - 1} = {0, 0, 1}
つまり、「その集合の全ての要素に -1 する」である。正しいかは分からないし、数学的な使われ方なのか否かも良く分からないのだが、そう理解すると解説の意味が分かったので一旦その前提で進める。
解説の理解
主に自分が理解できなかった部分と勘違いした部分を順に読み解く。
すべてのiでai>0ならば、（中略）ai=0となるiが存在したら
まず、「ai > 0」と「ai = 0」のケースを考慮している。これは、例えば下記のような話だ。
- {ai} = {1, 1, 2} ← 「すべてのiでai>0」
- {ai} = {0, 0, 1} ← 「ai=0となるiが存在している」
ここが自分は大きな勘違いをしていたため、改めて整理する。それは、「aiには0も含まれる」という点だ。
つまり、解説文において「nのm分割ai（Σ略）を考えます。」という記載は、問題文における「n個の何かをm個以下に分割する」という部分を表現している。
この記事の「前提知識」では「m個に分割」と「m個以下に分割」と書き分けて説明したが、蟻本の問題文と解説文ではそれが混同しており、自分や他の方も理解に苦しんでいたようである。
aiに0を許容することでm未満の分割数になる場合も含んで表現していることがぱっと理解できなくて
参考： https://qiita.com/MyOden/items/4cf63128469f5833e4aa
dp[i][j-i] と dp[i-1][j]
さて、概ね知識不足と勘違いが解決したので、後は DP に落とし込むだけ。
すべてのiでai>0
すべてのiでai>0の時、{ai-1}は上で書いた例の {0, 0, 1} などの様になる。これがn-mのm分割になるのは、最初に貼ったリンクを再度貼るが、下記の記事が分かりやすい。
「jをi個に分割するパターン」は、予めi個を1個ずつi個の集合に割り当てて、残ったj-i個をこの集合に割り当てるパターンを考えればいいと分かる。
参考： https://techtipshoge.blogspot.com/2011/01/blog-post_28.html
4の3分割の場合、1(n-m=4-3)の3(m)分割となり、1は分割しようがないので {0, 0, 1} のパターンだけ。
（ai=0が含まれてしまうと{-1, 0, 2}みたいなパターンが発生して、今回の分割では適していない。）
これが dp[i][j-i] の部分になる。（j-iのi分割の総数）
ai=0となるiが存在したら
0が存在するということは、「nのm-1分割となります」とあるが、これは「0が1つでもあるなら、0を1つ省略したら分割のmの数字を1つ減らせるよね」ということ。
例えばm=3分割のパターンで0が含まれるものは、下記の通りm=2分割の書き方に直せる。
- {0, 0, 4} → {0, 4}
- {0, 1, 3} → {1, 3}
- {0, 2, 2} → {2, 2}
よって、dp[i-1][j] の部分になる。（jのi-1分割の総数）
先ほどのパターンと足すことで、全部の総数が計算できるため、dp[i][j-i]+dp[i-1][j] となる。完
感想、考察
そもそも分割数の問題は蟻本では「DP はこう使えるよ」という応用編として記載されている。DPや漸化式について、もうちょっと経験を積まないとまだまだ使える気がしない。
ただ、漸化式では如何に前の状態を使いまわせるかを考えるかが重要で、その考え方は少しずつ経験値詰めている気はする。今回の件も解説が理解できたのは良いけれど、これを丸暗記しても効果が薄くて、DP をどう使うか、漸化式をどう考えるか、を考える必要がある。例えば今回のケースで言えば「0が1個でも含まれる場合、dp[i-1][j]で良い」という部分だけでも考えが至れば大きいんだろうな～とか、「すべてのiでai>0」の方を先に思いつくのは厳しそうとか。
競プロ始めたばかりなので引き続き頑張ります。また行き詰ったら記事書きます。