概要

「前日に方法 A を選んだかどうか」だけを状態として持つ \(2\) 状態 DP に落とし込み、\(N\) が \(10^{12}\) と非常に大きいので max-plus 行列累乗（行列累乗による DP の高速化）で \(O(\log N)\) で最大値を求めます。

考察

重要な気づき（状態は 2 つで十分）

各日の成長量が半減するかどうかは 「前日に A をやったか」だけで決まります。
つまり、過去の履歴を全部覚える必要はなく、次の 2 状態だけで十分です。

• 状態 \(0\): 前日が A ではない（前日が B、または 1 日目の前）
• 状態 \(1\): 前日が A

このとき「今日 A/B を選ぶ」だけで、次状態と得点が確定します。

素朴な方法がダメな理由

普通に DP を \(N\) 日ぶん回すと \(O(N)\) ですが、制約は \(N \le 10^{12}\) なので到底間に合いません（\(10^{12}\) 回の更新は不可能）。

どう解決するか

遷移が「同じ形で \(N\) 回繰り返される」ので、DP 遷移を 行列で表して 二分累乗（繰り返し二乗法）で \(N\) 回分をまとめて計算します。
ただし今回の DP は「和」ではなく「最大」を取るので、通常の行列積ではなく

• 掛け算：\(+\)
  
• 足し算：\(\max\)

で計算する max-plus（トロピカル）半環の行列積を使います。

アルゴリズム

1. 2 状態 DP の定義

\(dp_t[s]\) を「\(t\) 日終わった時点で状態 \(s\) にいるときの、成長量合計の最大値」とします（\(s \in \{0,1\}\)）。

初期状態（1 日目の前）は「前日は A ではない」なので
\(dp_0 = [0, -\infty]\) です。

2. 1 日ぶんの遷移（行列化）

今日の選択が A/B のときの得点は以下：

• 前日が A でない（状態 0）
  
  • 今日 B：得点 \(b\)、次状態 0
    
  • 今日 A：得点 \(a\)、次状態 1
• 前日が A（状態 1）
  
  • 今日 B：得点 \(\lfloor b/2 \rfloor\)、次状態 0
    
  • 今日 A：得点 \(\lfloor a/2 \rfloor\)、次状態 1

これを「状態 \(i\) から状態 \(k\) への遷移得点」として \(2\times2\) 行列 \(M\) にまとめます：

[ M = \begin{pmatrix} b & a \ \lfloor b/2 \rfloor & \lfloor a/2 \rfloor \end{pmatrix} ] （行が「現在状態」、列が「次状態」）

そして DP 更新は max-plus で [ dp{t+1}[k] = \max{i \in {0,1}} \left( dp_t[i] + M[i][k] \right) ] となり、これは「ベクトル × 行列（max-plus）」です。

3. \(N\) 日ぶんをまとめる（行列累乗）

同じ遷移を \(N\) 回繰り返すので [ dp_N = dp_0 \otimes M^N ] （\(\otimes\) は max-plus の積）

\(M^N\) は繰り返し二乗法で \(O(\log N)\) で求められます。

最後に答えは最終状態がどちらでもよいので [ \max(dp_N[0], dp_N[1]) ] です。

（具体例）\(N=3\) のときは \(dp_3 = dp_0 \otimes M^3\) を計算して最大値を取れば、全 \(2^3\) 通りを試さずに最適値が出ます。

計算量

• 時間計算量: \(O(\log N)\)（\(2\times2\) 行列の max-plus 乗算を繰り返すだけ）
• 空間計算量: \(O(1)\)（定数サイズの行列・ベクトルのみ）

実装のポイント

• \(-\infty\) の表現：到達不可能を表すため、十分小さい値（コードでは NEG = -10**80）を使います。

• max-plus の単位行列：通常の単位行列ではなく、
  [ I = \begin{pmatrix} 0 & -\infty \ -\infty & 0 \end{pmatrix} ] を使います（「遷移なし＝加点 0、他は不可能」）。

• 床関数：\(\lfloor a/2 \rfloor\) は Python では a//2 でOKです。

• 行列積は「\(C[i][k] = \max_j (A[i][j] + B[j][k])\)」である点に注意します（通常の + と * が逆になるイメージ）。

  ソースコード

import sys

def mat_mul(A, B, NEG):
    C = [[NEG, NEG], [NEG, NEG]]
    for i in range(2):
        for k in range(2):
            best = NEG
            for j in range(2):
                if A[i][j] == NEG or B[j][k] == NEG:
                    continue
                val = A[i][j] + B[j][k]
                if val > best:
                    best = val
            C[i][k] = best
    return C

def mat_pow(M, n, NEG):
    R = [[0, NEG], [NEG, 0]]  # identity in max-plus
    while n > 0:
        if n & 1:
            R = mat_mul(R, M, NEG)
        M = mat_mul(M, M, NEG)
        n >>= 1
    return R

def vec_mul(v, M, NEG):
    res = [NEG, NEG]
    for k in range(2):
        best = NEG
        for i in range(2):
            if v[i] == NEG or M[i][k] == NEG:
                continue
            val = v[i] + M[i][k]
            if val > best:
                best = val
        res[k] = best
    return res

def main():
    N, a, b = map(int, sys.stdin.readline().split())
    NEG = -10**80

    M = [
        [b, a],          # from state 0 (prev not A): B -> 0, A -> 1
        [b // 2, a // 2] # from state 1 (prev A):     B -> 0, A -> 1
    ]

    Mp = mat_pow(M, N, NEG)
    dp0 = [0, NEG]  # start in state 0 before day 1
    dpN = vec_mul(dp0, Mp, NEG)
    print(max(dpN))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。