AOJ 1167: Pollock's conjecture

問題

Pollock's conjecture | Aizu Online Judge

  • 与えられた数を正四面体数(n番目の正四面体数は n(n+1)(n+2)/6である)の和で表すときに最小でいくつの数が必要か
  • また奇数の正四面体数のみの和で表すときはどうか

方針

動的計画法を使う

dp[n]はnを表すのに必要な最小の正四面体数の個数を表す行列とする。 初期条件はdp[0]=0

それぞれの正四面体数iについて

  • iを使うならdp[n]=dp[n-i]+1が最小の個数
  • iを使わないなら現在dp[n]に入っている数が最小の個数

であるので、dp[n]=min(dp[n-i]+1, dp[n])として行列を更新していく。

奇数の場合も同様。

正四面体数はあらかじめ200番目(=1353400)まで求めておき、奇数番目だけ抜き出して他の行列に入れておいた。

コード

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
#define rep(i, n) for(int i=0; i<(n); ++i)

const int size = 200;
const int limit = 1000001;
int dp[limit], dp_odd[limit];
int tetra[size], odd[size];

int main(void){
    int size_odd = 0;
    for(int i=1; i<size+1; ++i) {
        ll t = i*(i+1)*(i+2)/6;
        tetra[i-1] = t;
        if(t%2==1) {odd[size_odd]=t; size_odd++;}
    }
    int inf = numeric_limits<int>::max();
    rep(i, limit) dp[i] = dp_odd[i] = inf;
    dp[0] = 0;
    dp_odd[0] = 0;
    rep(i, size) {
        for(int j=tetra[i]; j<limit; ++j) 
            dp[j] = min(dp[j-tetra[i]]+1, dp[j]);
    }
    rep(i, size_odd) {
        for(int j=odd[i]; j<limit; ++j) 
            dp_odd[j] = min(dp_odd[j-odd[i]]+1, dp_odd[j]);
    }

    int n;
    while(cin >> n && n) {
        cout << dp[n] << " ";
        cout << dp_odd[n] << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1896259#2

反省

  • dpを思いつかずに、再帰でやったらTLEした。AOJが20 sまで待ってくれることにびっくりした