Codeforces Round #356 (Div. 1) B. Bear and Tower of Cubes

競プロ Codeforces

問題文

http://codeforces.com/contest/679/problem/B

問題概要

整数 m があたえられる．m 以下の整数 X で，以下を満たす (n, X) を求める．

  • X を超えない最大の a^3 （立方数）を選び，X = X - a^3 と更新する．
  • X に対して上記の操作を繰り返す．
  • 上記のように貪欲的に操作を繰り返すと，最終的に X がちょうど 0 になる．
  • このとき，n を上記の操作を繰り返した回数とする．
  • このような (n, X) は複数考えられるが，(n, X) は std::pair と見たときの最大値であるとする．つまり，まず n を最大化し，次に X を最大化する．

・制約
1 <= m <= 10^15

解法

求める解を f(m) とおく．
まず，a^3 <= m を満たす最大の a を求める．
実は，最適解は，この a^3 か (a - 1)^3 のどちらか一方を使っていくことで求められることがわかる．以下でそれを確認する．

1. a^3 を選んだ場合．次に f(m - a^3) を考えれば良い．

2. (a - 1)^3 を選んだ場合．次に f(a^3 - 1 - (a - 1)^3) を考えれば良い．m - (a - 1)^3 でないのは，a は貪欲的に選んでいかなければならないので，a^3 を選ばないためには a^3 未満である必要があるためである．a^3 未満で最大を考えるのが当然最適なので，a^3 - 1 を選択する．

3. (a - 2)^3 を選んだ場合．同様に f((a - 1)^3 - 1 - (a - 2)^3) を求めれば良い．しかし，これは case 2 を選ぶより悪い．なぜなら，それぞれ

  • a^3 - 1 - (a - 1)^3 > (a - 1)^3 - (a - 2)^3
  • n はともに 1 増加
  • 使用した数（総和がXに該当）はそれぞれ(a - 1)^3，(a - 2)^3だけ増加

つまり，case2 のほうが，より大きな数を残しつつ X にもより大きい数を加えられる．

よって，case 1 か 2 を繰り返し選択して行くDFSが考えられる．
問題は深さがいくらになるか．
じつは，そんなに大きくならないことがわかる．
(a + 1)^3 - 1 - a^3 = 3a^2 + 3a より，一回の操作で m のオーダーが 2/3 乗に落ちるからである．
したがって，case1 または case2 を繰り返し選択していくDFSを書けば，十分速い解答になる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr ll INF = 1e18;

pair<ll, ll> solve(ll total, ll cnt, ll used) {
    if(total == 0) {
        return make_pair(cnt, used);
    }

    ll next = 1;
    while(pow(next, 3) <= total) {
        next++;
    }
    next--;
    auto res = solve(total - pow(next, 3), cnt + 1, used + pow(next, 3));
    if(next > 0) {
        res = max(res, solve(pow(next, 3) - 1 - pow(next - 1, 3), cnt + 1, used + pow(next - 1, 3)));
    }
    return res;
}

int main() {
    ll m;
    cin >> m;
    auto res = solve(m, 0, 0);
    cout << res.first << ' ' << res.second << endl;
}

感想

n はたかだか18らしい．
こういうのは実験すると見えるんだろうか．
典型ではないらしいが，本番で解いてる人多いし，頑張って通したい問題．