この手の問題にどうしても慣れることが出来ないのでメモ。
問題概要
非負整数 $n$ に対して関数 $f(n)$ を以下のように定義する。
- $f(0) = 0$
- $n$ 以下の最大の立方数を $c$ としたとき、 $f(n)=f(n-c)+1$
簡単には、 $ f(n)= $ 「引ける最大の立方数を貪欲に引く」を繰り返した時に $n$ は何個の立方数で表されるか と言い換えられる。
整数 $ m $ が与えられるので、以下の条件を全て満たす $X$ を求めよ。
- $ 1 \le X \le m $
- $f(X) = \max_{1 \le i \le m} f(i)$
- $X$ は以上の条件を満足する中で最大の整数である。
なお、 $f(X)$ と $X$ の双方を出力せよ。
$1 \le m \le 10^{15}$
ひとまず、 $f$ はそんなに大きくならなさそうという直感がある ( $10^{15}-1$ あたりから始めても、ひとつ平方数をさっ引けば必ず $10^{10}$ 程度になる → 一段操作を施す度に値の大きさが $2/3$ 乗程度になるはず) 。
$f(x)=i$ となる最小の $x$ を列挙してみると以下のようになる。
1 : 1
2 : 2
3 : 3
4 : 4
5 : 5
6 : 6
7 : 7
8 : 15
9 : 23
10 : 50
11 : 114
12 : 330
13 : 1330
14 : 10591
15 : 215970
16 : 19464802
A055402 - OEIS を発見。とりあえず $f(X) \le 18$ であることは分かった。
ここで、気持ちとしては $2^{18}$ みたいな解法を見つけたくなるので、そのマインドで進めていく。
実は、以下の解法が成立する。
(無駄にした値, 現在残っている値) というペアを要素として取る集合 $S$ を管理する。
最初は $ S=\{ (0,m) \} $ から始める。
足し算に使う平方数を $1$ つ増やすことは、以下の手順を踏むことに対応する。
- $S'$ を以下の手順で構成する。
- $S$ の各要素 $e=(e_1,e_2)$ に対して、以下を行う。
- $e_2=0$ なら何もしない。
- そうでない時 $mx=e_2$ 以下の最大の立方数とする。
- $S'$ に $(e_1,e_2-mx)$ を追加。
- 立方数 $mx$ を足すことに対応。
- $mx \neq 1$ なら、 $mx$ より小さい最大の立方数を $mx'$ とした時、 $S'$ に $(e_1+(e_2-mx-1),mx-1-mx')$ を追加。
- 立方数 $mx'$ を足すことに対応。
- $S=S'$ と置き換える。
この手順で一番長く生き残った要素のうち、 (無駄にした値) が最小のものを $s$ とすると $X=m-s$ が答えとなる。
最大の立方数かその一回り下しか選ばなくてよいというのは、それ未満の立方数を選んだ時にこのアルゴリズム上で「無駄にした値も増え、現在残っている値も減ってしまう」ということから言える。(ここにけっこう大きな飛躍がありますが、分かりやすい日本語で説明できる気がしなかったので勘弁してください...)
計算量もやはり $O(2^{18})$ 程度となった。
Submission #185404760 - Codeforces
A - Pay to Win とほんのちょっと似てるような気もする。この手の再帰構造が問題にあって「実は変数○○ってそんな大きくないんですよ！いかがでしたか？」の問題、一生友達になれる気がしない。
