[分割統治法 例] 競技プログラミングっぽい問題を解いてみる
アルゴリズムの適用フレームワークとして下記のような図があることを以前ご紹介しました。
貪欲法が適用できない場合の例として、こんな問題をかんがえてみましょう。
整数Nが与えられたとき、そのNを1,3,4の和であらわす組み合わせの数を出力せよ
例 N=4のとき
4通り
N: {4},{1.3},{3,1},{1,1,1,1}
例 N=5のとき
6通り
N: {4,1},{1,4},{3,1,1},{1,3,1},{1,1,3},{1,1,1,1,1}
最適な部分構造を探す
貪欲法が利用できない場合には、どう問題に対してアプローチすべきでしょうか？ひとつの指針として、その問題に部分構造最適性を見つけることです。
最適な部分構造とは？
最適な部分構造があれば、分割統治法で解くことができます。ではその最適な部分構造とはどういうものでしょうか？上の問題を例に考えてみましょう。
うえの問題はNを1,3,4の組み合わせで表現すると決まっています。つまり、Nを1,3,4を部分構造として成り立つと考えられますね。分割統治のポイントは
部分構造を前提条件（Base condition)
として考えることです。すると、分割統治の問題は再帰関数処理によって、どんな入力が与えられたとしても、部分構造の前提条件に復元されます。つまり、分割統治法の問題は、部分構造の前提条件だけを繰り返し演算することで、答えがえられるのです。なので、分割統治法は、いかに部分構造の前提条件を決定するかという問題に置き換えられるのです。
部分構造の前提条件をもとめる
では、うえの問題の部分構造である1,3,4の前提条件をもとめてみましょう。
まずNが１のときを考えます。1は１,3,4を用いて表現すると{１}の1通りです。
N=3のとき {1,1,1} 1通り、N=4のとき{１,3},{3,1},{1,1,1,1},{4} 4通りとなりますね。
これらを前提条件として、N=5のときを考えます。このときに、部分構造の差分を考えます。部分構造はすでに上で求めているので、そのあまり分についてだけ考えればよいのです。つまり、
5- 1 = 4
5- 3 = 2
5- 4 = 1
結果として、4,2,1の部分構造の数を求める問題になります。4,1は部分構造の前提条件としてすでに導出済ですが、2は前提条件として求めていませんでした。しかしながら２は{1,1}と一意に決まりますので、これも前提条件に加えてしまいましょう。すると、
4 -> ４通り
2 -> 1通り
1 -> 1通り
となるので、これらの和の6がN=5を1,3,4の部分構造の前提条件をもちいて表現される答えとなります。では、ここまでをプログラムとして書き下してみましょう。
#include ＜iostream＞;
using namespace std;
int number_factor(int n){
// Base condition ここから
if(n<0){
cout ＜＜Input number more than 0. ＜＜ endl;
return n;
}
if(n==0 || n==1 || n==2)
return 1;// {}, {1}, {1,1}
if(n==3)
return 2; // {1,1,1}, {3}
// Base condition ここまで
int subtract1 = number_factor(n-1);
int subtract3 = number_factor(n-3);
int subtract4 = number_factor(n-4);
return subtract1 + subtract3 + subtract4;
}
int main(){
cout ＜＜ number_factor(5) ＜＜ endl;
cout ＜＜ number_factor(6) ＜＜ endl;
cout ＜＜ number_factor(-1) ＜＜ endl;
return 0;
}
N=2,0の場合が部分構造の前提条件に加えられたところがポイントです。目安としては、部分構造1,3,4の最大値以下0以上を部分構造の前提条件として考慮する感覚でよいと思います。なので、この場合は部分構造の最大値が4なので0以上4以下、つまり、0,1,2,3,4を部分構造の前提条件として考えるという方針になります。
ではでは