猫でもわかるWeb開発・プログラミング

本業エンジニアリングマネージャー。副業Webエンジニア。Web開発のヒントや、副業、日常生活のことを書きます。

AOJ 1167: ポロック予想 (Pollock's conjecture)

はじめに

方針

計算量の見積もりが非常に難しい。はじめは全探索したが、当然のように通らなかった(下の方にある「通らなかったコード」参照)ので、動的計画法を使う。

  • 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;
    }
}

*1:ダメ元でブルンゲルなみのり打ったらのろわれボディだったぐらいの感情になった

*2:ポケモンの名前とか特性の名前にちゃんとリンク貼られることに気づいた。はてなスゲェ