Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 135 A問題 Floor, Ceil - Decomposition

AtCoder ARC ARC135 A問題 300 pts

問題

提出解答

問題の概要

黒板には整数 $X$ が書かれている. 以下の操作を任意回行う.

黒板に書かれている整数を1つ選び, それを $x$ とする.
黒板に書かれている $x$ を1つ消し, $\lfloor \frac{x}{2} \rfloor, \lceil \frac{x}{2} \rceil$ を書き加える.

この操作後, 黒板に書かれている整数の総積の最大値を求めよ.

制約

$1 \leq X \leq 10^{18}$

解法

黒板に $n$ 個の整数 $x_1, x_2, \dots, x_n$ が書かれているとき, それぞれの整数について独立に考えることができる. 従って, どのような整数について操作すべきかを考えれば良い.

ここで, 一般的に非負整数 $a,b$ に対して, $a b \geq a+b$ となるのはいつかを考えると,

$ab \geq a+b \iff (a,b)=(0,0) \quad \lor (a \geq 2 \land b \geq 2)$

である. そして, $a=\lfloor \frac{x}{2} \rfloor, b=\lceil \frac{x}{2} \rceil$ とする. すると, $a+b=x$ であるから,

$\lfloor \frac{x}{2} \rfloor \times \lceil \frac{x}{2} \rceil \geq x \iff x=0 \quad \lor \quad (x \geq 4)$

である.

ここで, $x=0$ の場合は操作前後で総積は変わらないので, 操作しないことにすると,

$4$ 以上の整数に対して操作すべきである.

という事がわかる. また, 操作後の2つの整数については独立性から, 最初の整数が小さい場合に帰着できる.

最初の整数が $X$ のときの答えを $f(X)$ をすると,

$f(X)=\begin{cases} X & (X \leq 3) \\ f( \lfloor \frac{X}{2} \rfloor) f(\lceil \frac{X}{2} \rceil) & (X \geq 4) \end{cases}$

である. よって, $f(X)$ を求めるためにはこの関係式を用いてメモ化することにより, $O(\log X)$ 回の再帰で求められることができる.

最後に, $f(X)$ を求めるために必要な $f(Y)$ の $Y$ の個数について考えると, 実はある整数 $k$ を用いて $Y=\lfloor \frac{X}{2^k} \rfloor, \lceil \frac{X}{2^k} \rceil$ と表せる場合だけでよい. よって, 再帰の各段階においての $Y$ は高々 $2$ 個なので, この問題を $O(\log X)$ で求めることができた.