概要

\(N\) 日間の水やりで、毎日方法 A か B を選び、方法 A を選んだ翌日は成長量が半減するというペナルティがある中で、成長量の合計を最大化する問題です。\(N\) が最大 \(10^{12}\) と非常に大きいため、max-plus 半環上の行列累乗で高速に解きます。

考察

状態遷移として捉える

各日の成長量は「前日に何を選んだか」だけで決まります。つまり、状態は「前日に A を選んだ」「前日に B を選んだ（または初日）」の 2 状態 で管理できます。

遷移をまとめると：

前日の選択	今日の選択	今日の成長量
B（またはなし）	A	\(a\)
B（またはなし）	B	\(b\)
A	A	\(\lfloor a/2 \rfloor\)
A	B	\(\lfloor b/2 \rfloor\)

素朴な DP では間に合わない

\(dp_A(i)\)：\(i\) 日目に A を選んだときの最大成長量合計、\(dp_B(i)\)：\(i\) 日目に B を選んだときの最大成長量合計、と定義すれば：

\[dp_A(i) = \max(dp_A(i-1) + \lfloor a/2 \rfloor, \; dp_B(i-1) + a)\]

\[dp_B(i) = \max(dp_A(i-1) + \lfloor b/2 \rfloor, \; dp_B(i-1) + b)\]

これは \(O(N)\) ですが、\(N \le 10^{12}\) なので到底間に合いません。

max-plus 行列累乗で高速化

上の遷移は「最大値を取りながら足し算する」形をしています。これは通常の行列積における \((+, \times)\) を \((\max, +)\) に置き換えた max-plus 半環上の行列積と見なせます。

遷移行列 \(T\) を次のように定義します（行が「今日の状態」、列が「前日の状態」）：

\[T = \begin{pmatrix} \lfloor a/2 \rfloor & a \\ \lfloor b/2 \rfloor & b \end{pmatrix}\]

ここで \(T[i][j]\) は「前日が状態 \(j\)、今日が状態 \(i\)」のときの成長量です。

初日のベクトルは \((dp_A, dp_B) = (a, b)\) で、これに \(T\) を \((N-1)\) 回適用すれば \(N\) 日目の状態が得られます。

具体例：\(N=3, a=10, b=7\) の場合 - 初日：\(dp_A=10, dp_B=7\) - 2 日目：\(dp_A = \max(10+5, 7+10)=17\)、\(dp_B = \max(10+3, 7+7)=14\) - 3 日目：\(dp_A = \max(17+5, 14+10)=24\)、\(dp_B = \max(17+3, 14+7)=21\) - 答え：\(\max(24, 21) = 24\)（A → A → A ではなく B → B → A で達成）

アルゴリズム

1. \(N=1\) なら \(\max(a, b)\) を出力して終了。
2. max-plus 半環上の \(2 \times 2\) 遷移行列 \(T\) を定義する。
3. 繰り返し二乗法で \(T^{N-1}\) を計算する（max-plus 行列積を使用）。
4. 初期ベクトル \((a, b)\) に \(T^{N-1}\) を適用し、得られた 2 状態の最大値が答え。

max-plus 行列積の定義： $\(C[i][j] = \max_k \left( A[i][k] + B[k][j] \right)\)$

単位行列は対角成分が \(0\)、非対角成分が \(-\infty\) です（\(\max\) の単位元が \(-\infty\)、\(+\) の単位元が \(0\)）。

計算量

• 時間計算量: \(O(\log N)\)（\(2 \times 2\) 行列の累乗なので、各ステップは定数時間）
• 空間計算量: \(O(1)\)（行列サイズが固定の \(2 \times 2\)）

実装のポイント

• max-plus 半環の単位元：\(-\infty\) を適切に扱う。Python では float('-inf') を使用。

• 初期ベクトルの適用：\(T^{N-1}\) を計算した後、初期ベクトル \((a, b)\) との max-plus 積で最終結果を得る。具体的には \(\max_{i,j}(T^{N-1}[j][i] + \text{init}[i])\) を計算する。

• \(N=1\) の特別処理：行列累乗の指数が \(0\) になるケースを正しく扱うため、先に処理しておくと安全。

• 整数除算：Python の // 演算子は非負整数に対して \(\lfloor x/2 \rfloor\) を正しく計算するので、そのまま使える。

  ソースコード

def solve():
    N, a, b = map(int, input().split())
    
    if N == 0:
        print(0)
        return
    
    # We need to choose A or B each day to maximize total growth.
    # If previous day was A, current day's growth is halved.
    # 
    # Let's think about patterns:
    # - All B: N * b
    # - All A: a + (N-1) * (a // 2)
    # - Alternating A, B, A, B, ...: each A gives a (since prev is B or first day), each B gives b//2 (since prev is A)
    #   Wait, A then B: B gets halved. So pattern AB AB AB...
    #   A gives a, B gives b//2. Per 2 days: a + b//2
    # - Alternating B, A, B, A, ...: B gives b, A gives a (since prev is B). Per 2 days: b + a
    #   Wait, but then the next B after A gets halved: b//2
    #   So pattern: B, A, B, A, B, A, ...
    #   Day 1 (B): b, Day 2 (A): a, Day 3 (B): b//2, Day 4 (A): a, Day 5 (B): b//2, ...
    #   Hmm, not purely periodic from the start.
    #
    # Let me think with DP states. State = what was done previous day (A or B).
    # dp[A] = max total ending with A on last day
    # dp[B] = max total ending with B on last day
    #
    # Transitions:
    # If last day was B, new day A: gain a (no halving)
    # If last day was B, new day B: gain b
    # If last day was A, new day A: gain a//2
    # If last day was A, new day B: gain b//2
    #
    # So this is a 2-state linear recurrence over N days -> matrix exponentiation.
    #
    # State vector: (dp_A, dp_B) after day i
    # But it's max-plus, not standard linear algebra.
    # We can use max-plus matrix exponentiation.
    
    # Max-plus semiring: (max, +) instead of (+, *)
    # Matrix multiplication: C[i][j] = max_k (A[i][k] + B[k][j])
    
    # Transition matrix T (2x2):
    # From state A (col 0) or state B (col 1) to state A (row 0) or state B (row 1)
    # T[0][0] = a//2   (A -> A: gain a//2)
    # T[0][1] = a      (B -> A: gain a)
    # T[1][0] = b//2   (A -> B: gain b//2)
    # T[1][1] = b      (B -> B: gain b)
    
    # Initial (day 1):
    # dp_A = a, dp_B = b
    # Then apply T for (N-1) more days.
    
    # For N=1, answer is max(a, b).
    
    if N == 1:
        print(max(a, b))
        return
    
    NEG_INF = float('-inf')
    
    def mat_mult(A, B, size=2):
        # Max-plus matrix multiplication
        C = [[NEG_INF]*size for _ in range(size)]
        for i in range(size):
            for j in range(size):
                for k in range(size):
                    if A[i][k] != NEG_INF and B[k][j] != NEG_INF:
                        C[i][j] = max(C[i][j], A[i][k] + B[k][j])
        return C
    
    def mat_pow(M, p, size=2):
        # Identity for max-plus: 0 on diagonal, -inf elsewhere
        result = [[NEG_INF]*size for _ in range(size)]
        for i in range(size):
            result[i][i] = 0
        while p > 0:
            if p & 1:
                result = mat_mult(result, M, size)
            M = mat_mult(M, M, size)
            p >>= 1
        return result
    
    ha = a // 2
    hb = b // 2
    
    T = [
        [ha, a],
        [hb, b]
    ]
    
    # Apply T^(N-1) to initial vector (a, b)
    Tn = mat_pow(T, N - 1)
    
    # Result vector: for each final state, max over initial states
    # val[j] = max_i (Tn[j][i] + init[i])
    init = [a, b]
    
    best = NEG_INF
    for j in range(2):
        for i in range(2):
            if Tn[j][i] != NEG_INF:
                best = max(best, Tn[j][i] + init[i])
    
    print(best)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。