CodeIQ：本の読み方は何通り？

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「本の読み方は何通り？」（CodeIQ）を参照してください。

問題の概要

nページの本があります。これをm日以内に読み終わる必要があります。
必ず前日よりも少ないページ数になるように配分します。
標準入力からn,m(1≦n≦180, 1≦m≦14)が与えられます。
m 日以内で読み終わるパターンが全部で何通りあるかを求め、標準出力にパターン数を出力してください。

私のプログラム

Javaで解答しています。

import java.io.*;

class Main {

	public static long g(int n, int l, int k){
		long s=0;
		if(k==1){return 1;}
		for(int i=l+1; i<=n; i++){
			long v=0;
			if(n-i+1 < i){
				break;
			}
			else if(k-1 == 1){
				v=1;
			}
			else{
				v = g(n-i+1, i, k-1);
			}
			if(v == 0){
				break;
			}
			s+=v;
		}
		return s;
	}

	public static long A000009(int n,int m){
		long s=0;
		if(n==0){	return 1; }
		for(int k=1; k<=m; k++){
			s += g(n,1,k);
		}
		return s;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try{
			String line;
			while((line = br.readLine()) != null){
				line = line.trim();
				if(line.length() == 0){
					break;
				}
				String[] vals = line.split(",");
				int n = Integer.parseInt(vals[0]);
				int m = Integer.parseInt(vals[1]);
				System.out.println(A000009(n,m));
			}
		}
		finally{
			br.close();
		}
	}
}

解説

この問題はかなり苦労しました。
問題を読んで自然数分割で解けるなとは思ったのですが、それを実装するのに苦労しました。

基本的な考え方

前述の通り自然数分割です。問題を数学の問題っぽく言い換えると次のようになるでしょうか。
「自然数nがある。これをm個以下の違いに異なる自然数に分割した場合、何通りの組み合わせがあるか？」
自然数分割のアルゴリズムは検索すれば結構見つかるのですが、m個以下に分割するアルゴリズムがなかなかわかりませんでした。m個以下ではなく全てのパターンを列挙するアルゴリズムを実装してみてそこから何とかしようとしていた時に、OEISというサイトを発見しA000009という数列にたどり着きました。この数列が答えです。

A000009()

ぱっと見非常にダメな関数名ですが、これはOEISのA000009であることが後で分かるようにしたためです。
OEISでは幾つかの言語でプログラムが示されてはいるのですが、私が読める言語での記述がありません。OEISのどこかを見て多分こういうことだろうと考えながら実装しました。

A000009()はnをm個以下の互いに異なる自然数に分割したパターンの合計を求める関数で、nを1個、2個、3個、…とそれぞれの個数に分割するのはg()という関数です。g()という名前もどうかと思いますが、OEISで調べた時に同じ名前がつけられていたのでそれに習いました（後で調べやすいように）。

g()

引数はn,i,kでnは元の数、lは分割後の最小の数、kは何個に分割するかです。今回の場合、lは常に1が渡されます。

まず、k=1なら1パターンしかないので1でリターンします。
k>1の場合、nを(n-1,1)、(n-2, 2)、…と分割し、左側の値と右側の値+1、k-1を再度g()に与えて再帰的に呼び出します。わかりにくいのでn=6、k=3で具体的に考えてみます。
まずforループで(5,1)、(4,2)に分割されます。10行目の条件があるのでそれ以上には分割されません。
（5,1）はg(5,2,2)で再帰的に呼び出されます。結果(3,2)となってもう一度g(3,3,1)で呼び出されます。これはk=1なので1が帰ります。
（4,2）はg(4,2,2)で再帰的に呼び出されます。こちらは10行目の条件でbreakし、0が帰ります。
結果、22行目は1となり最終的に1が帰って6を3個の異なる自然数に分割するパターンは1通りになります。
このようにしてg()はA000009()からk（何日で読み終わるか）のパターンだけ呼び出され、kのパターンの数を返すのでそれをA000009()で合計したのが答えになります。

雑感

私はこのプログラムを最初Pythonで書き、Cで書き直し、さらにJavaで書き直しました。理由は性能です。Pythonでは話にならず、これと同じロジックを実装したCのプログラムでは1秒を超えていました。再帰なので関数呼び出しのオーバヘッドが問題だろうとは思っていてリターン条件のチェックをg()の呼び出し前にするなどしてみましたが1秒をわずかに切れませんでした。-O2の最適化を行えば0.7秒くらいになったのですが、CodeIQのテストサーバにオプションを指定することはできません。
そこでふとJavacには最適化オプションがないことを思い出しました。つまり、もしかしたらJavaは勝手にいい感じの最適化を施してくれるのでは？という想像です。で、やってみたら0.7秒くらいでCよりも早いという結果に！
これには非常に驚きました。JavaはJVMのオーバヘッドがあるので相当の最適化が施されているということです。これについて少し考えてみたのですが、多分次のようなことが起こっているのだと思います。
JVMはJITコンパイラがあって実行時最適化が施されます。プログラムは再帰で実行前は呼び出し回数が不定ですが、パラメータが与えられた実行時には呼び出し回数が確定します。そのためJITコンパイラは再帰をループなりに展開することが可能なため静的最適化しかできないCよりも高速に実行可能になったのではないか、と想像しています。
しかし、Javaは速くなった（特にデーモンのようなずっと動き続けるプログラムではJVMの軌道オーバヘッドが無視できるのでC言語並みになった）という話は結構前からいろんな記事で目にしてはいたのですが、実際にCよりも早いということが起きるとは想像していませんでした。

ちなみに別の出題者の近い時期の問題「プラス・マイナス・ゼロ」問題も自然数分割の問題で、このころは整数分割の問題ばかり考えていました。