概要

当番は \(N\) 日ごとに同じ並びを繰り返すので、\(D\) 日間を「丸ごと何周分あるか」と「最後に何日余るか」に分けて考える問題です。
1 周分の合計はすぐ求められ、端数部分は累積和で高速に計算できます。

考察

この問題でまず大事なのは、当番の並びは長さ \(N\) の周期で繰り返すということです。

例えば \(N=5,\ S=4\) なら、当番の順番は

\(4, 5, 1, 2, 3, 4, 5, 1, \dots\)

のようになります。
つまり、どこから始まっても \(N\) 日進めば全員が 1 回ずつ当番になります。

重要な気づき 1：1 周分の水の量は常に同じ

1 周 \(N\) 日の間には住人 \(1\) から \(N\) までがちょうど 1 回ずつ登場するので、1 周分の合計は

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

です。

したがって、\(D\) 日を

• \(q = \left\lfloor \dfrac{D}{N} \right\rfloor\) 周
• 残り \(r = D \bmod N\) 日

に分ければ、

• \(q\) 周分の合計は \(q \times \sum A_i\)
• あとは残り \(r\) 日分だけ求めればよい

となります。

---

重要な気づき 2：残り \(r\) 日は「円環上の連続区間」

残りの \(r\) 日分は、住人 \(S\) から始まる並びの先頭 \(r\) 人分の和です。

ただし、\(S\) から始めると途中で \(N\) を超えて 1 に戻るため、普通に配列を切り出すと少し扱いにくいです。

そこで、配列を 2 回つなげた

\(B = A + A\)

を作ります。

すると、円環上の連続区間は、\(B\) 上の普通の連続区間として表せます。
たとえば

\(A = [a_1, a_2, a_3, a_4, a_5]\)

なら

\(B = [a_1, a_2, a_3, a_4, a_5, a_1, a_2, a_3, a_4, a_5]\)

です。
\(S=4\) から 3 日分なら、必要なのは

\(a_4 + a_5 + a_1\)

ですが、これは \(B\) 上では連続する区間になります。

---

素朴な方法がなぜダメか

\(D\) 日を 1 日ずつシミュレーションして足していく方法だと、計算量は \(O(D)\) です。
しかし制約では \(D \le 10^{14}\) なので、これは到底間に合いません。

そこで、

• 周期性を使って大部分を一気に数える
• 残りだけ累積和で求める

ことで、高速に解けます。

---

具体例

例えば

• \(N=5\)
• \(D=8\)
• \(S=4\)
• \(A=[2,3,5,7,11]\)

とします。

当番順は

\(4,5,1,2,3,4,5,1\)

なので、使う水の量は

\(7,11,2,3,5,7,11,2\)

です。

ここで

• \(8 \div 5 = 1\) 余り \(3\)

なので、

• 1 周分の合計：\(2+3+5+7+11=28\)
• 残り 3 日分：\(7+11+2=20\)

よって答えは

\(28+20=48\)

です。

アルゴリズム

1. \(A\) の総和 total_cycle = sum(A) を求める
   これは 1 周 \(N\) 日分の合計水量である。

2. \(D\) を \(N\) で割って
   \(q, r = \mathrm{divmod}(D, N)\)
   を求める。

   • \(q\)：丸ごとの周回数
   • \(r\)：最後に余る日数

3. 配列を 2 回連結して B = A + A を作る。

4. B の累積和 pref を作る。
   これにより、区間和は

\(\text{pref}[R] - \text{pref}[L]\)

で求められる。

1. 開始位置を 0-indexed で start = S - 1 とする。

2. 残り \(r\) 日分の和は
   pref[start + r] - pref[start] で求める。

3. 最終的な答えは

\(q \times \text{total\_cycle} + \text{partial}\)

である。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 住人番号は \(1\) 始まりですが、Python の配列は \(0\) 始まりなので、開始位置は S - 1 にします。

• 残り日数 \(r\) は常に \(0 \le r < N\) なので、A + A を作っておけば必要な区間は必ずその中に収まります。

• r=0 のときも、
  pref[start + r] - pref[start] = 0
  となるので特別扱いは不要です。

• 他言語で実装する場合、答えは大きくなる可能性があるので 64-bit 整数型を使うと安全です。

  ソースコード

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)
    
    B = A + A
    pref = [0] * (2 * N + 1)
    for i in range(2 * N):
        pref[i + 1] = pref[i] + B[i]
    
    start = S - 1
    partial = pref[start + r] - pref[start]
    
    print(q * total_cycle + partial)

if __name__ == "__main__":
    main()

---

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