概要

当番は \(N\) 日ごとに同じ並びを繰り返すので、\(D\) 日分を「完全な周回」と「端数の日数」に分けて合計を求める問題です。
1日ずつシミュレーションせず、周期性を使って高速に計算します。

考察

重要な観察は、当番の順番が長さ \(N\) の周期で繰り返すことです。
住人ごとの水量配列を \(A_1, A_2, \dots, A_N\) とすると、1周（\(N\) 日）で使う水の合計は

\( \text{total\_cycle} = \sum_{i=1}^{N} A_i \)

です。

素朴解が厳しい理由

素朴に \(1\) 日目から \(D\) 日目まで毎日「今日の当番」を計算して足すと、\(O(D)\) かかります。
しかし制約では \(D \le 10^{14}\) なので、これは到底間に合いません。

どう解決するか

\(D\) 日を

• 完全な周回数 \(q = \lfloor D/N \rfloor\)
• 端数日数 \(r = D \bmod N\)

に分解します。

• 完全な周回分は \(q \times \text{total\_cycle}\)
• 残り \(r\) 日分だけ、開始位置 \(S\) から順に足す

これで大きな \(D\) でも高速に求められます。

例えば、\(N=5, S=4\) なら並びは
\(4,5,1,2,3,4,5,\dots\)
なので、端数 \(r\) 日分は「配列の後ろ側 + 先頭側」にまたがる可能性があります。
この場合分けを実装で処理します。

アルゴリズム

1. \(N, D, S\) と配列 \(A\) を読む。
2. \(\text{total\_cycle} = \sum A\) を計算。
3. \((q, r) = \text{divmod}(D, N)\) を計算。
4. 初期答えを \(ans = q \times \text{total\_cycle}\) とする。
5. 開始位置を 0-index で start = S - 1 とする。
6. \(r>0\) のとき、残り \(r\) 日分を加算：
   • start + r <= N なら A[start:start+r] を足す（はみ出さない）
   • それ以外なら A[start:] + A[:(start+r)%N] を足す（末尾から先頭へ回り込み）
7. ans を出力。

計算量

• 時間計算量: \(O(N)\)
  （sum(A) と、最大でも配列全体をなめる程度の加算）
• 空間計算量: \(O(N)\)
  （入力配列 \(A\) の保持）

実装のポイント

• 住人番号は 1-index、Python の配列は 0-index なので start = S - 1 に変換する。

• 回り込み処理（末尾→先頭）を正しく分けることが大事。

• 答えは最大で大きくなるが、Python の int ならオーバーフローの心配はありません。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, D, S = map(int, input().split())
    A = list(map(int, input().split()))

    total_cycle = sum(A)
    q, r = divmod(D, N)

    ans = q * total_cycle

    start = S - 1  # 0-index
    if r > 0:
        if start + r <= N:
            ans += sum(A[start:start + r])
        else:
            ans += sum(A[start:]) + sum(A[:(start + r) % N])

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。