95. 今日解いた問題（2022.04.05）

今日解いた問題についてまとめます。

自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。

問題一覧

A - Floor, Ceil - Decomposition (Diff: 634)
B - Sum of Three Terms (Diff: 1239)

自分の解法など

A - Floor, Ceil - Decomposition

目的を達成するための最適な戦略を考察します。

$x$ を $\lfloor x/2 \rfloor, \lceil x/2 \rceil$ に書き換えると、積はどのように変化するでしょうか。大まかに見積もるため $x/2$ が 2 つ登場すると考えると、この部分の積は $x^2/4$ になります。よって、 $x \gt 4$ であれば書き換える、 $x \lt 4$ であれば書き換えない戦略が有効そうです。実際、 $x = 5$ など周辺値で確かめて、この仮説が正しいことが分かります。

よって、 $X$ を書き換える操作を繰り返して得られる数を、全て $4$ 以下にしたあと積を取ると答えです。ただし、制約が大きいので単純にシミュレーションすると間に合いません。ここで、「値を半分に（近い値に）する操作を繰り返す」ということを考えて、同じような計算が多く登場することに注目すると、メモ化再帰で $O(\log X)$ くらいに落とせることが分かります。

B - Sum of Three Terms

各項の関係を数式で表現することで考察します。

$S_1 = A_1 + A_2 + A_3$
$S_2 = A_2 + A_3 + A_4$

と並べてみると、 $S_1 - S_2 = A_1 - A_4$ であることが分かり、整理すると $A_4 = A_1 - S_1 + S_2$ です。同様に、以下のような式が導出できます。

$A_4 = A_1 - S_1 + S_2$
$A_5 = A_2 - S_2 + S_3$
$A_6 = A_3 - S_3 + S_4$
$A_7 = A_4 - S_4 + S_5 = A_1 - S_1 + S_2 - S_4 + S_5$

このように、 $A$ の全ての項が最初の 3 項を用いて表現できることが分かりました。 $S_i$ は入力から与えられるので定数として考えてよいです。よって、この問題は $A_1, A_2, A_3$ を決定する問題と読み替えることができました。もっと言えば、 $A_3 = S_1 - A_1 - A_2$ であり、 $A_1, A_2$ の 2 項を決める問題であると言い換えられます。

$A_i \le 10^9$ という暗黙の制約があるので、単純な探索は不可能です。ただし、 $A$ の各項から $A_1, A_2, A_3$ の「差」を求めることはできています。任意の $i$ について $A_i \ge 0$ を満たす必要があるため、最初の 3 項に対応する「差」の最小値を求めます。ここで見た項が $0$ 以上になればよいので、結局、

「差」の最小値が非負であれば $0$
「差」の最小値が負であれば、その絶対値

とすれば、「全ての項が非負」という条件を満たす最小の $A_1, A_2, A_3$ を求められます。また、 $A_3 = S_1 - A_1 - A_2$ という制約を考えて、 $A_1, A_2$ はできるだけ小さな値を取ると、 $A_3$ を正にするという戦略において有利であることが分かります。よって、この条件で $A_1, A_2$ を決定するのが最善です。