概要

初期資金 \(S\) 円からスタートし、毎日の売上（商品の人気度の総和）と支出（アルバイトの日給の総和）を繰り返す中で、所持金がマイナスにならない最大の日数を求める問題です。

考察

まず、1日あたりの収支の変化を整理します。 - 1日の売上の合計を \(X = \sum_{i=1}^{N} A_i\) とします。 - 1日の支払いの合計を \(Y = \sum_{j=1}^{M} B_j\) とします。

1日の営業が終わるごとの所持金の変化量は \(X - Y\) 円です。\(k\) 日目の営業終了時点での所持金は、以下の式で表せます。 $\(\text{所持金} = S + k \times (X - Y)\)$

ここで、問題の条件である「営業終了時点での所持金が \(0\) 円以上」を維持できる日数を考えます。

1. 収支がプラスまたはゼロの場合 (\(X \geq Y\))

1日あたりの収支 \(X - Y\) が \(0\) 以上であれば、日数が経過しても所持金は減りません。 最初の所持金 \(S\) は \(0\) 以上であり、1日の売上 \(X\) を得てから支払い \(Y\) を行うため、最初の営業日も必ず乗り越えられます。その後も所持金は維持されるか増えていくため、永遠に営業を続けることができます。したがって、この場合は -1 を出力します。

2. 収支がマイナスの場合 (\(X < Y\))

1日ごとに所持金が減っていくため、いずれ営業ができなくなります。 1日あたりの損失を \(L = Y - X\) （\(L > 0\)）とおくと、 \(k\) 日後の所持金は \(S - k \times L\) です。これが \(0\) 以上である必要があるため： $\(S - k \times L \geq 0\)\( \)\(k \times L \leq S\)\( \)\(k \leq \frac{S}{L}\)\( これを満たす最大の整数 \)k\( は、 \)S\( を \)L$ で割ったときの商（小数点以下切り捨て）となります。

アルゴリズム

1. 商品の人気度の総和 \(X = \sum A_i\) と、日給の総和 \(Y = \sum B_j\) を計算します。
2. \(X \geq Y\) であれば、-1 を出力して終了します。
3. \(X < Y\) であれば、損失 \(L = Y - X\) を計算します。
4. \(S\) を \(L\) で割った商 \(S // L\) を計算し、その値を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • \(A_i\) の総和と \(B_j\) の総和を計算するのに、それぞれ \(N\) 回と \(M\) 回の加算が必要です。
• 空間計算量: \(O(N + M)\)
  • 入力値をリストとして保持する場合に必要です。

実装のポイント

• 大きな入力値: \(N\) や \(M\) が \(10^5\) と大きいため、Pythonでは sys.stdin.read().split() などを用いて高速に入力を読み込むのが効率的です。

• 数値の範囲: \(S\) や \(A_i, B_j\) の値が大きいため、合計値や計算過程で \(10^{18}\) を超える可能性があります。Pythonは標準で多倍長整数を扱えるため、オーバーフローの心配はありません。

• 切り捨て除算: \(S\) を \(L\) で割る際、Pythonでは // 演算子を使うことで整数部分（切り捨て）を簡単に求められます。

  ソースコード

import sys

def solve():
    # Fast I/O: read all input at once and split into tokens
    # This is efficient for handling the large number of inputs (up to 2*10^5 integers).
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # N: Number of items, M: Number of part-time workers, S: Initial capital
    n = int(input_data[0])
    m = int(input_data[1])
    s = int(input_data[2])
    
    # Popularity A_i corresponds to the daily sales from the i-th item.
    # Daily wage B_j is the amount paid to the j-th worker.
    # The total daily sales is the sum of all A_i.
    # The total daily expense is the sum of all B_j.
    # A_i values are located from index 3 to 3+n-1 in the input_data list.
    # B_j values are located from index 3+n to 3+n+m-1.
    
    # Using sum(map(int, ...)) is efficient in Python for summing a slice of the input.
    a_sum = sum(map(int, input_data[3:3+n]))
    b_sum = sum(map(int, input_data[3+n:3+n+m]))
    
    # The problem states that each day, sales are earned first, and then wages are paid.
    # Business is successful for a day if the balance after paying wages is non-negative.
    # Let S_k be the balance after k days.
    # S_k = S + k * (a_sum - b_sum)
    # We need S_k >= 0 for all k from 1 to the maximum business days.
    
    diff = a_sum - b_sum
    
    if diff >= 0:
        # If daily sales are greater than or equal to daily wages, the balance 
        # will not decrease over time. Since S >= 0 and a_sum >= b_sum, 
        # S_1 = S + (a_sum - b_sum) will always be >= 0, and subsequent days 
        # will also maintain a non-negative balance.
        print("-1")
    else:
        # If daily wages are greater than daily sales, the balance decreases each day.
        # Let loss = b_sum - a_sum (where loss > 0).
        # The balance after k days is S - k * loss.
        # We need S - k * loss >= 0, which implies k <= S / loss.
        # The maximum integer k satisfying this is the floor of S / loss.
        loss = b_sum - a_sum
        # In Python, // performs floor division.
        print(s // loss)

if __name__ == '__main__':
    solve()

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