概要

\(N\) 本のパイプから1本以上を選んでつなぎ合わせ、完成するパイプの長さを最大化する問題です。各パイプには有効長があり、2本以上つなぐときは接続箇所ごとに長さ \(K\) が減少します。

考察

有効長の計算

まず各パイプの有効長を求めます。

• 錆びていないパイプ（\(B_i = 0\)）：有効長は \(A_i\)
• 錆びているパイプ（\(B_i = 1\)）：有効長は \(\max(A_i - C, 0)\)

完成品の長さの式を分解する

\(M\) 本のパイプを選んだとき、完成品の長さは：

\[\sum_{j=1}^{M} e_j - (M - 1) \times K\]

ここで \(e_j\) は選んだ各パイプの有効長です。この式を変形すると：

\[= e_1 + \sum_{j=2}^{M} (e_j - K)\]

つまり、最初の1本はそのまま有効長が加算され、2本目以降は有効長から \(K\) を引いた値（\(e_j - K\)）が加算されると解釈できます。

貪欲法のアイデア

この分解から、最適な戦略が見えてきます：

1. 最も有効長が大きいパイプを最初に選ぶ（そのまま加算されるため）
2. 残りのパイプについて、\(e_j - K > 0\)（つまり \(e_j > K\)）であれば追加する（追加するほど完成品の長さが増えるため）
3. \(e_j - K \leq 0\) のパイプは追加しても長さが増えない（または減る）ので選ばない

有効長を降順にソートしておけば、先頭から順に見ていき、\(e_j - K > 0\) を満たす限り追加し続ければよいです。\(e_j - K \leq 0\) になった時点でそれ以降のパイプも同様なので打ち切れます。

素朴なアプローチとの比較

全ての部分集合を試すと \(O(2^N)\) で、\(N \leq 10^5\) では到底間に合いません。上記の貪欲法ならソート後に1回走査するだけで済みます。

アルゴリズム

1. 各パイプの有効長 \(e_i\) を計算する。
2. 有効長を降順にソートする。
3. まず先頭の要素（最大の有効長）を選び、合計 \(\text{total} = e_0\) とする。
4. 2番目以降のパイプについて、\(e_i - K > 0\) であれば \(\text{total}\) に \(e_i - K\) を加算する。そうでなければ打ち切る。
5. 最終的な \(\text{total}\) の最大値が \(D\) 以上なら出力、そうでなければ \(-1\) を出力する。

具体例: \(N=3\), \(K=2\), \(C=1\) で有効長が \([10, 5, 1]\)（降順ソート済み）の場合

• 1本目: \(\text{total} = 10\)
• 2本目: \(5 - 2 = 3 > 0\) → \(\text{total} = 13\)
• 3本目: \(1 - 2 = -1 \leq 0\) → 追加しない（打ち切り）

完成品の長さの最大値は \(13\) です。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（有効長の配列）

実装のポイント

• \(A_i\) や \(D\) が大きいため、合計値が大きくなり得ます。Python では整数オーバーフローの心配はありませんが、C++ などでは long long を使う必要があります。

• 錆びたパイプの有効長は \(\max(A_i - C, 0)\) であり、負にならないよう注意が必要です。

• 有効長が \(0\) のパイプは \(K \geq 1\) より \(e_j - K < 0\) となるため、自動的に選ばれません。

• sys.stdin.buffer.read() で高速に入力を読み込んでいる点も、\(N\) が大きい場合のTLE回避に有効です。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    D = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    C = int(input_data[idx]); idx += 1
    
    effective = []
    for i in range(N):
        A = int(input_data[idx]); idx += 1
        B = int(input_data[idx]); idx += 1
        if B == 1:
            eff = max(A - C, 0)
        else:
            eff = A
        effective.append(eff)
    
    # When we select M pipes, the total length is:
    # sum of effective lengths - (M-1)*K
    # Adding a pipe with effective length e increases total by e - K (except for the first pipe).
    # So we should:
    # 1. Pick the pipe with the largest effective length first.
    # 2. Then greedily add pipes where e - K > 0 (i.e., e > K), sorted by effective length descending.
    
    effective.sort(reverse=True)
    
    if N == 0:
        print(-1)
        return
    
    # Start with the best single pipe
    total = effective[0]
    best = total
    
    for i in range(1, N):
        gain = effective[i] - K
        if gain > 0:
            total += gain
            if total > best:
                best = total
        else:
            break
    
    if best >= D:
        print(best)
    else:
        print(-1)

solve()

---

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