Codeforces Round #356 (Div. 1) B. Bear and Tower of Cubes
問題概要
整数 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らしい.
こういうのは実験すると見えるんだろうか.
典型ではないらしいが,本番で解いてる人多いし,頑張って通したい問題.