はじめに
- 問題: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1167
- ソースコード: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1359188
- Javaで実装
方針
計算量の見積もりが非常に難しい。はじめは全探索したが、当然のように通らなかった（下の方にある「通らなかったコード」参照）ので、動的計画法を使う。
dp[i] = (iを表すのに必要な正四面体数の数)とする。- まず、すべての数字は 1+1+1+...+1 (1は正四面体数である) で表すことができるので、dp[i] = i とすることができる。
- 正四面体数 p を使うことで、i+p は、
(iを表すのに必要な正四面体数の数) + 1で表せることになる。よって、dp[i+p] = min(dp[i+p], dp[i] + 1)となる。すでに(iを表すのに必要な正四面体数の数) + 1よりも小さい個数で表す方法が見つかっているかもしれないので、minを取る。 - これを p < 1000000 となるようなすべての p について、このような更新を行う。
- 最後に入力された num に対して dp[num] を返すだけ。
奇数の正四面体数のみを使った場合の odp[] も作成し、こちらはpが奇数の時のみ更新を行えば良い。
計算量の見積もりだが、まず、1000000以下の正四面体数は180個あるらしい。DPのテーブルの大きさは 106 なので、180 * 106 で間に合いそうにもない気がするが、正四面体数が大きくなると更新すべきdpテーブルの数が減るので、間に合うらしい。*1 time limit も8秒あるし。*2
通ったコード
class Main{ // public static Graph g; public static void main(String[] args) throws Exception{ int[] dp = new int[1000001]; int[] odp = new int[1000001]; // dp[i] = i で初期化 for(int i = 0; i <= 1000000; i++){ dp[i] = i; odp[i] = i; } for(int n = 3, p = 4; p <= 1000000; n++){ for(int i = 0; i+p <= 1000000; i++){ dp[i+p] = Math.min(dp[i+p], dp[i] + 1); } if(p % 2 == 1){ for(int i = 0; i+p <= 1000000; i++){ odp[i+p] = Math.min(odp[i+p], odp[i] + 1); } } // pの値をここで更新 p = n * (n+1) * (n+2) / 6; } BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); while(true){ int num = Integer.parseInt(br.readLine()); if(num == 0) break; System.out.println(dp[num] + " " + odp[num]); } } }
通らなかったコード
class Main{ static ArrayList<Integer> a = new ArrayList<Integer>(); public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int p = 1; for(int i = 2; p <= 1000000; i++){ a.add(p); p = i * (i+1) * (i+2) / 6; } while(true){ int num = Integer.parseInt(br.readLine()); if(num == 0) break; int ans1 = dfs(num, a.size() - 1); int ans2 = dfsodd(num, a.size() - 1); System.out.println(ans1 + " " + ans2); } } static int dfs(int rest, int last){ if(rest == 0) return 0; int ret = 10000000; for(int i = last; i >= 0; i--){ int n = a.get(i); if(n > rest) continue; ret = Math.min(ret, 1 + dfs(rest - n, i)); } return ret; } static int dfsodd(int rest, int last){ if(rest == 0) return 0; int ret = 10000000; for(int i = last; i >= 0; i--){ int n = a.get(i); if(n % 2 == 0) continue; if(n > rest) continue; ret = Math.min(ret, 1 + dfsodd(rest - n, i)); } return ret; } }
