ホーム画面を整理して！
締め切りが 2017/06/13 10:00 AM なので，その 1 分後に投稿されるように予約
設問
多くの人が使うようになったスマートフォン。
そのホーム画面には多くのアプリのアイコン（以下、アイコン）が並びます。
そこで、このアイコンをフォルダにまとめて整理することを考えます。
1つのフォルダには1個～9個のアイコンを登録でき、登録するとフォルダ1つのアイコンにまとまり、そのフォルダに登録されているアイコンの数が識別できるようになります。
なお、フォルダの中にフォルダを作ることはできません。
n 個のアイコンを整理するとき、そのフォルダ構成について、アイコンの数の組み合わせがいくつ考えられるかを求めます。
ただし、個々のアイコンは識別せず、並び順も考えないものとし、アイコンの数の組み合わせだけを考えます。
（フォルダ内にあるアイコンの数が異なる場合は、別々のフォルダ構成としてカウントします。）
なお、ホーム画面には最大で24個のアイコンを並べられるものとし、n は 1≦n≦216を満たす整数とします。
例えば、n = 5 のとき、以下の7通りがあります。
（図の黄色はフォルダを、数字はアイコンの数を表します。）
当然、n = 216のときは、すべてフォルダにまとめた1通りしかありません。
標準入力から n が与えられるとき、アイコンの数の組み合わせがいくつあるかを求め、標準出力に出力してください。
【入出力サンプル】
標準入力
5
標準出力
7
==============================================================
整数分割問題だが，分割数が 24 以下という制約があるもの。
n=108 で対称。つまり，f(128) == f(88), f(214) == f(2)。
R だと，制限時間オーバー
initDiv = function(length, max) {
ary = NULL
repeat {
if (max >= length) {
ary = c(ary, length)
return(ary)
} else {
ary = c(ary, max)
length = length - max
}
}
}
nextDiv = function(ary) {
# 1でない要素を後ろから探す
sum = 0
for (pos in length(ary):1) {
a = ary[pos]
sum = sum + a
if (a != 1 && (pos > 1 && ary[pos - 1] >= ary[pos])) {
break
}
}
if (ary[1] == 1) { # 全て1
return(FALSE)
}
ary = ary[1:pos]
ary[pos] = ary[pos] - 1
max = ary[pos]
sum = sum - max
pos = pos + 1
repeat {
if (pos > 24) {
ary[pos] = sum
return(ary)
}
if (max >= sum) {
ary[pos] = sum
return(ary)
} else {
ary[pos] = max
sum = sum - max
}
pos = pos + 1
}
}
f = function(length, max) {
length = min(length, 216 - length)
d = initDiv(length, max)
count = 1
repeat {
d = nextDiv(d)
if (length(d) == 1) {
break
}
count = count + (24 >= length(d))
}
cat(count)
}
f(128)
f(5, 9) # 7
f(10, 9) # 41
system.time(f(50, 9)) # 39777, 0.884 sec.
system.time(f(128, 9)) # 449718, 9.317 sec.
system.time(f(214, 9)) # 2
Java で書いて OK
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
long start = System.currentTimeMillis();
int n, i;
if (false) {
n = 88; // 449718
} else {
Scanner cin = new Scanner(System.in);
String line;
line = cin.nextLine();
n = Integer.parseInt(line);
n = Math.min(n, 216-n);
}
int m = 9;
int[] d = initDiv(n, m);
int count = 0;
for (;;) {
for (i = 0; i < d.length; i++) {
if (d[i] == 0 || i > 24) {
break;
}
}
if (24 >= i) {
count++;
}
if (nextDiv(d) == false) {
break;
}
}
System.out.println(count);
long end = System.currentTimeMillis();
System.out.println((end - start) + " ms");
}
static int length(int[] a) {
for (int len = 0;; len++) {
if (a[len] == 0)
return len;
}
}
static int[] initDiv(int length, int max) {
int a = length / max;
int[] ary = new int[1000];
for (int i = 0; i < a; i++) {
ary[i] = max;
}
ary[a] = length % max;
return (ary);
}
static boolean nextDiv(int[] ary) {
int sum, pos, a, max;
sum = 0;
for (pos = length(ary) - 1; pos >= 0; pos--) {
a = ary[pos];
sum += a;
if (a != 1) {
break;
}
}
if (pos == -1) {
return false;
}
max = --ary[pos];
sum -= max;
for (pos++;; pos++) {
if (max >= sum) {
ary[pos] = sum;
for (int j = pos + 1; j < 1000; j++) {
ary[j] = 0;
}
return true;
} else {
ary[pos] = max;
sum -= max;
}
}
}
}
