概要

\(N\) 本のパイプから \(M\) 本（\(1 \le M \le N\)）を選んで繋ぎ合わせたときの最大長を求め、その値が目標値 \(D\) 以上であるか判定する問題です。パイプが錆びている場合の減衰や、接続時のジョイントによる長さの減少を考慮する必要があります。

考察

1. 各パイプの「有効長」を確定させる

まず、各パイプを単体で見たときの「実際に使える長さ（有効長）」を計算します。 - 錆びていない場合（\(B_i = 0\)）：\(A_i\) - 錆びている場合（\(B_i = 1\)）：\(\max(A_i - C, 0)\)

この有効長は、他のパイプをどう選ぶかに関わらず一定です。

2. \(M\) 本選ぶときの最適な組み合わせ

\(M\) 本のパイプを選んで繋ぐとき、完成品の長さは以下の式で表されます。 $\((\text{選んだ } M \text{ 本の有効長の合計}) - (M - 1) \times K\)$

この値を最大化するためには、有効長が長い順に \(M\) 本選ぶのが最適です。したがって、あらかじめ全てのパイプを有効長の降順（大きい順）にソートしておけば、上から \(M\) 本取ることが最善となります。

3. 選ぶ本数 \(M\) の決定

\(M\) 本選んだ状態から、さらに \(1\) 本追加して \(M+1\) 本にすることを考えます。 新しく追加するパイプの有効長を \(L_{M+1}\) とすると、全体の長さの変化量は次のようになります。 - 新しいパイプの長さ \(L_{M+1}\) が加わる - 接続箇所が 1 箇所増えるため、長さが \(K\) 減少する

つまり、変化量は \(L_{M+1} - K\) です。 この値が正であれば、本数を増やすことで完成品の長さはより長くなります。逆に負であれば、本数を増やすと短くなります。

今回の問題では、本数 \(M\) を \(1\) から \(N\) まで変化させたときの最大値を求めればよいため、有効長をソートした後に順番に足し合わせていき、その都度最大値を更新していくことで答えが得られます。

アルゴリズム

1. 有効長の計算: 各パイプについて、錆の有無に応じた有効長 \(L_i\) を計算し、リストに格納します。
2. ソート: リスト \(L\) を降順（大きい順）にソートします。
3. 最大値の探索:
   • 最初に \(1\) 本選んだ場合（\(M=1\)）の長さ \(L_0\) を暫定の最大値とします。
   • 次に、残りのパイプを \(i = 1\) から \(N-1\) まで順番に見ていき、現在の長さに \((L_i - K)\) を加算します。
   • 各ステップでの長さの最大値を保持します。
4. 判定: 最大値が \(D\) 以上ならその値を、そうでなければ \(-1\) を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 有効長の計算に \(O(N)\)、ソートに \(O(N \log N)\)、最大値の走査に \(O(N)\) かかります。全体のボトルネックはソート部分です。
• 空間計算量: \(O(N)\)
  • パイプの有効長を保持するリストに \(O(N)\) のメモリを使用します。

実装のポイント

• 入力の高速化: \(N\) が \(10^5\) と大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 錆による負の値: 錆びたパイプの長さ \(A_i - C\) が負になる可能性があるため、必ず max(0, A_i - C) をとるようにします。

• 最大値の初期化: \(M=1\) のときは接続箇所が \(0\) なので、初期値を \(L_0\) とし、ループ内では \(2\) 本目以降の増分 \((L_i - K)\) を処理するように実装するとシンプルです。”`python

  処理のイメージ

  current_sum = L[0] # 1本目の長さ max_val = current_sum for i in range(1, N): current_sum += (L[i] - K) # 2本目以降、1本増えるごとに L[i]-K 変化する if current_sum > max_val: max_val = current_sum

  ソースコード

import sys

def solve():
    # sys.stdin.read().split() を使用して、入力を一括で読み込みトークンに分割します。
    # これは Python において大量の入力を高速に処理する一般的な手法です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 最初の 4 つのトークンは N, D, K, C です。
    N = int(input_data[0])
    D = int(input_data[1])
    K = int(input_data[2])
    C = int(input_data[3])
    
    # 各パイプの有効長（effective length）を計算します。
    # B_i = 0 の場合はそのまま A_i、B_i = 1 の場合は max(A_i - C, 0) となります。
    L = [0] * N
    for i in range(N):
        A = int(input_data[4 + 2*i])
        B = int(input_data[5 + 2*i])
        if B == 0:
            L[i] = A
        else:
            # 錆びているパイプの有効長は max(A - C, 0)
            effective = A - C
            if effective < 0:
                effective = 0
            L[i] = effective
    
    # 完成品の長さを最大化するために、有効長が長い順にパイプをソートします。
    # M 本のパイプを選んだとき、どの M 本を選ぶのが最適かは、有効長の大きい順に選ぶことと同義です。
    L.sort(reverse=True)
    
    # 完成品の長さの最大値を求めます。選ぶ本数 M は 1 以上 N 以下です。
    # M = 1 のとき、長さは選んだパイプの有効長そのものです。
    current_sum = L[0]
    max_val = current_sum
    
    # M = 2 から N までの場合を順番に試します。
    # M 本選んだときの長さは (M 本の有効長の合計) - (M - 1) * K です。
    # これは M-1 本の時の長さに (新しく選んだパイプの有効長 - K) を足すことで計算できます。
    for i in range(1, N):
        # i は 0-indexed なので、L[i] は (i+1) 本目に長いパイプの有効長です。
        current_sum += (L[i] - K)
        if current_sum > max_val:
            max_val = current_sum
            
    # 最大値が目標値 D 以上であればその値を出力し、そうでなければ -1 を出力します。
    if max_val >= D:
        print(max_val)
    else:
        print("-1")

if __name__ == "__main__":
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。