競技プログラミングの問題を教えていただきたいです（正整数の立方数による表現）

Question

#include<stdio.h>
int amari(int , int);
int kosuu(int, int);
int keisan(int, int);
int sum = 0, min = 11;

int main(void){
  int n, m, kans = 0;
  scanf("%d%d", &n, &m);
  int i, k, ans = 100;
  if(n == 1){
    k = 1;
  }else{
    for(i = 1 ; i < n ; i++){
      if(i*i*i > n){
	k = i-1;
	break;
      }
    }
  }
  for(;k  > 1;k--){
    kans = keisan(n, k);
if(kans < ans){
      ans = kans;
    }
    sum = 0;
  }
  if(ans <= m){
    printf("%d\n", ans);
  }else{
    printf("-1\n");
  }
}

int amari(int n, int p){
  return n % (p*p*p);
}

int kosuu(int n, int p){
  return n / (p*p*p);
}
int keisan(int n, int k){
  int q = 0;
  if(k != 1){  
    sum += kosuu(n, k);
    keisan(amari(n, k), k-1);
  }else{
    sum += n;
  }  
  return sum;
}


```競技プログラムの問題を教えていただきたいです。（C言語でお願いいたします）
【問題原文】
正整数 n と m が与えらえるとき，n を m 個以下の立方数（正整数の三乗）の和で表現することを考える．
例えば，n = 35，m = 10 のとき，n は次のように立方数を使って表現できる
35 = 33 + 23
35 = 33 + 13 + 13 + 13 + 13 + 13 + 13 + 13 + 13
35 = 23 + 23 + 23 + 23 + 13 + 13 + 13
正整数 n が m 個以下の立方数の和として表現できるとき，必要な立方数の最小個数を調べるプログラムを作成せよ．
（入力）
入力は以下の形式で与えられる．
n m
（制約）
・n，m はいずれも正整数．
・1 ≤ n ≤ 50000
・1 ≤ m ≤ 10
（出力）
正整数 n を表現するのに必要な立方数の最小個数を出力せよ． ただし，n が m 個以下の立方数の和で表現できないときには -1 と出力せよ．
（例）
入力1:
35 10
出力1:
2
35 を表現するのに必要な立方数の最小個数は2個である（35 = 33 + 23）．
入力2:
53 3
出力2:
-1
53 を3個以下の立方数の和として表現することはできない．

自分で作成したソースコードを載せさせていただきました。
上記のコードでは例の入力1, 2には対応できているのですが、自分でほかの値で試したときに正しい値を出力しませんでした。（具体的にはn=4059, m=10この場合の正しい答えは12^3+11^3+10^3で3、自分のコードでは5と出てしまいます。）
理由はわかっているのですが、改善方法がわかりません。

Comments

[maisumakun]

どこまで実装してみましたか？

[y_waiwai]

まずはあなたのコードを提示しましょう
競技プログラムならなおさら

[raiboz1115]

返信ありがとうございます。
ソースコードを張らせていただきます。

#include<stdio.h>
int amari(int , int);
int kosuu(int, int);
int keisan(int, int);
int sum = 0, min = 11;

int main(void){
int n, m;
scanf("%d%d", &n, &m);
int i, k, ans;
for(i = 1 ; i < n ; i++){
if(i*i*i > n){
k = i-1;
break;
}
}
ans = keisan(n, k);
if(ans <= m){
printf("%d\n", ans);
}else{
printf("-1\n");
}
}

int amari(int n, int p){
return n % (p*p*p);
}

int kosuu(int n, int p){
return n / (p*p*p);
}
int keisan(int n, int k){
if(k != 1){
sum += kosuu(n, k);
keisan(amari(n, k), k-1);
}else{
sum += n;
}
return sum;
}

上記のコードでは例の入力1, 2には対応できているのですが、自分でほかの値で試したときに正しい値を出力しませんでした。

[y_waiwai]

質問文は編集できますんで、そこにコードを貼ってください

コードは、質問を編集し、<code>ボタンを押し、出てくる’’’の枠の中にコードを貼り付けてください

[raiboz1115]

一応提出もしてみたのですが、WRONG-ANSWERではなくRUN-ERROER判定となってしまいました。

[raiboz1115]

指摘ありがとうございます。
質問文を編集させていただきます。

[1T2R3M4]

https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q12244810592

以下ご対応ください。
https://teratail.com/help#posted-otherservice

[raiboz1115]

指摘ありがとうございます。
yahoo知恵袋の方は削除させていただきました。

[kazuma-s]

> 35 = 33 + 23

35 = 3^3 + 2^3 または 35 = 3**3 + 2**3 と書いてほしい。
最初見た時、なんだこれ？、と思いました。

Answer 1

この問題は「最小個数部分和問題」と呼ばれる典型的な動的計画法で解く問題です。
参考：
https://qiita.com/drken/items/a5e6fe22863b7992efdb
ナップザック問題の解法が分かっていればその応用で解けます。

一般的には表にすると分かりやすいです。
例題通り、n=35, m=10を考えます。

横列を0からターゲットである35までの数列(ni)、縦行を0からmまでの数列(mi)とする表を作成します。
この表の中には、「niをmiまでの数で作成した平方数（T[1..mi]）の和で作成した際の、平方数の最小個数」を入れるものとします。ただし、初期値として(0,mi) = 0 、それ以外のマスをm+1とします。m+1は「不可能」を表すと考えてください。（一般的には+∞を入れますが、この場合はm+1で良い）

mi = 1 から順番にそれぞれの ni に対して「最小いくつの立方数で作成できるか」を考えていきます。
mi = 1 の場合は、1 の平方数は 1 なので それぞれの ni に対して 1を何回足し算できるかで求まります。

赤字が差分です。
立法数が1のみだと、10までは作成できますがそれ以降は作成できません。当然ですね。

次に、mi=2 の行に注目します。
2の立方数は8（i の立法数を Ti と表現します）です。例えば ni=8 の場合、立法数8だけで構成できるので(8,2)に入る数値は1になるでしょう。
ni=9 の場合はどうでしょう。もともと 9 は 1 の平方数 9個で構成できます。しかし、1 と 8 の2つでも構成できます。こちらの方が構成数が小さいですね。
これは、ni=1 の現段階での最小構成に 8 を加算した場合に等しいです。
したがって、「miが1つまで段階での最小数（1行上の数字）」と「miが現段階で、ni - Ti の最小数 + 1」のどちらか小さい方が現時点での回答になります。

mi = 2 の行を ni = 1 から上記の方法で順番に埋めていくとこのような表になっていきます。

同様に mi = 3 の行も同じルールで埋めていきます。

mi = 4 の立法数 64 は既にn=35を超えているので、これ以上探索する必要はありません。ここで打ち切りとします。
最終的に、ni=35 の列の一番下の数値である 2 が回答となります。

以上のような計算をプログラムで行えばよいです。コーディングのサンプルは冒頭のqiita記事を参考にしてください（C++のコードですが入出力以外はCとほぼ同等なので十分参考になると思います）
質問者さんは貪欲法での実装ができているので動的計画法の実装も理屈が分かれば難しくないでしょう。

それでは全て正解できるよう頑張ってください。

Comments

[raiboz1115]

ありがとうございます！時間はかかってしまいましたが何とか理解することができました！

Answer 2

面白そうな問題なので、やってみました。

#include <stdio.h> // scanf, printf
#include <math.h>  // cbrt

int n, m, len = -1;

void gen(int i, int j, int k)
{
	if (k == 0) len = m = i;
	else if (k > 0 && i < m)
		for (; j > 0; j--) gen(i+1, j, k - j*j*j);
}

int main(void)
{
	scanf("%d%d", &n, &m);
	gen(0, (int)(cbrt(n) + 0.1), n);
	printf("%d\n", len);
}

総当たりですが、枝刈りしているので短時間で済むでしょう。
バグのご指摘は歓迎します。

Answer 3

ナイーブに、「最大の立方数から埋めていく」というパターンでは、正解が出ない数があります。

たとえば、855 = 8**3 + 7**3と立方数2つで表されますが、このアルゴリズムでは先に9**3を引いてしまうので、855 = 9**3 + 5**3 + 1**3の3つと出てしまいます。

Comments

[raiboz1115]

なるほど、理解しました。
問題意向を満たすにはどのようなアルゴリズムがありますでしょうか？
加えて、答えが間違って出力されるのであればWRONG-ANSWERと判定されるはずなのですがRUN-ERROER判定となる原因として何が考えられるでしょうか？

[maisumakun]

n=1の場合にkが初期化されない、という問題がまずありそうです。

[raiboz1115]

ありがとうございます。
RUN-ERRORではなくWRONG-ANSWERにはなりました。