概要

屋台の1日あたりの収支（売上 − 日給の合計）を求め、それが黒字か赤字かで場合分けし、赤字の場合は所持金が尽きるまでの最大日数を計算する問題です。

考察

まず、1日の営業で所持金がどう変化するかを整理しましょう。

• 1日の売上: 全商品の人気度の合計 \(\displaystyle\sum_{i=1}^{N} A_i\)
• 1日の支出: 全アルバイトの日給の合計 \(\displaystyle\sum_{j=1}^{M} B_j\)
• 1日あたりの収支（利益）: \(P = \displaystyle\sum_{i=1}^{N} A_i - \sum_{j=1}^{M} B_j\)

\(d\) 日営業した後の所持金は以下のようになります：

\[S + d \times P\]

場合分け

場合1: \(P \geq 0\) のとき（利益がゼロ以上）

毎日の営業で所持金が減らない（増えるか変わらない）ため、何日でも営業を続けられます。答えは -1 です。

場合2: \(P < 0\) のとき（毎日赤字）

1日あたり \(|P|\) 円ずつ所持金が減っていきます。\(d\) 日後に所持金が \(0\) 以上であるための条件は：

\[S + d \times P \geq 0\]

\[S - d \times |P| \geq 0\]

\[d \leq \frac{S}{|P|}\]

\(d\) は整数なので、最大日数は \(\left\lfloor \dfrac{S}{|P|} \right\rfloor\) です。

具体例

例えば \(N=2, M=2, S=10, A=[3, 5], B=[4, 6]\) のとき：

• 売上合計 \(= 3 + 5 = 8\)
• 日給合計 \(= 4 + 6 = 10\)
• 1日あたりの損失 \(= 10 - 8 = 2\) 円

最大日数 \(= \lfloor 10 / 2 \rfloor = 5\) 日です。実際に確認すると、5日後の所持金は \(10 + 5 \times (-2) = 0\) 円で、ちょうど \(0\) 円なのでOKです。

アルゴリズム

1. 配列 \(A\) の合計（売上）と配列 \(B\) の合計（日給）を計算する。
2. 1日あたりの利益 \(P = (\text{売上}) - (\text{日給})\) を求める。
3. \(P \geq 0\) なら -1 を出力する。
4. \(P < 0\) なら \(\left\lfloor S / |P| \right\rfloor\) を出力する。

計算量

• 時間計算量: \(O(N + M)\)（配列の合計を求めるだけ）
• 空間計算量: \(O(N + M)\)（入力の格納）

実装のポイント

• \(S\) の上限が \(10^{18}\)、\(A_i, B_j\) の上限が \(10^9\) で、それぞれ最大 \(10^5\) 個あるため、合計値は最大 \(10^{14}\) 程度になります。Python は多倍長整数を扱えるのでオーバーフローの心配はありませんが、C++ などで実装する場合は long long 型を使う必要があります。

• \(P = 0\) のとき（売上と日給がちょうど等しいとき）も、所持金は減らないため無限に営業でき、-1 を出力します。この場合を見落とさないよう注意しましょう。

• Python の整数除算 // は負の無限大方向への切り捨てですが、ここでは \(S \geq 0\) かつ \(|P| > 0\) なので通常の切り捨て除算と一致し、問題ありません。

  ソースコード

def main():
    import sys
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    S = int(input_data[idx]); idx += 1
    
    A = []
    for i in range(N):
        A.append(int(input_data[idx])); idx += 1
    B = []
    for i in range(M):
        B.append(int(input_data[idx])); idx += 1
    
    total_sales = sum(A)
    total_wages = sum(B)
    
    daily_profit = total_sales - total_wages
    
    if daily_profit >= 0:
        # Each day we gain or break even, so we can operate forever
        print(-1)
    else:
        # daily_profit < 0, so each day we lose (-daily_profit) yen
        # After d days: S + d * daily_profit >= 0
        # S + d * daily_profit >= 0
        # d <= S / (-daily_profit)
        loss_per_day = -daily_profit
        print(S // loss_per_day)

main()

---

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