Problem 1167 : Pollock's conjecture

Problem C: ポロック予想
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1167&lang=jp

• 問題概要

今年の国内予選のC。とっても悔しい。
コイン両替問題みたいな感じ。
その、枚数を答えろみたいな。

• 解法

DP。DPで先にテーブル作る、ということには考えは至っていたのだけれども、
ひとつの要素を何回も使う場合をいっぺんにかんがえ、オーダーが増えてしまった。

複数回つかえても一回しかつかわなくても、つぎあとでその要素からまた同じ単位使うっていうのを
考慮にいれられるから、1000000×(1000000までに含まれる正四面体数)でよかった。

• ソース

#include<iostream>
#include<algorithm>
#include<vector>

#define MAX 1000001

using namespace std;

main(){
  int t[MAX], kt[MAX];

  fill(t, t+MAX, MAX);
  fill(kt, kt+MAX, MAX);
  t[0] = 0;
  kt[0] = 0;
  vector<int> v, kv;
  for(int i=1;; i++){
    int tmp = i*(i+1)*(i+2)/6;
    if(tmp > MAX)break;
    v.push_back(tmp);
    if(tmp % 2 == 1){
      kv.push_back(tmp);
    }
  }

  for(int i=0; i<MAX; i++){
    for(int j=0; j<v.size(); j++){
      int tmp = i+v[j];
      if(tmp >= MAX)break;
      t[tmp] = min(t[i] + 1, t[tmp]);
    }
    for(int j=0; j<kv.size(); j++){
      int tmp = i+kv[j];
      if(tmp >= MAX)break;
      kt[tmp] = min(kt[i]+1, kt[tmp]);
    }
  }

  int n;

  while(cin >> n){
    if(n == 0)break;
    cout << t[n] << ' ' << kt[n] << endl;
  }
}

わりと、簡潔にかけたのではないか、とおもう。

ああああああああああああああああああああ、くやしいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいいい。