概要

\(N\) 人の住人が番号順に巡回して水やり当番を務めるとき、\(D\) 日間で使われる水の合計量を求める問題です。\(D\) が最大 \(10^{14}\) と非常に大きいため、1日ずつシミュレーションせず効率的に計算する必要があります。

考察

素朴なアプローチの問題点

1日ずつ順番にシミュレーションすると、\(D\) 回のループが必要です。\(D\) は最大 \(10^{14}\)（100兆）にもなるため、到底時間内に終わりません（TLE）。

重要な気づき：巡回の周期性

当番は \(N\) 人を1周すると、また同じ順番に戻ります。つまり、\(N\) 日ごとに同じパターンが繰り返されるのです。

例えば \(N = 3\), \(S = 2\), \(A = [5, 3, 7]\) のとき、当番の順番は：

\[\underbrace{2, 3, 1}_{1周目}, \underbrace{2, 3, 1}_{2周目}, \underbrace{2, 3, 1}_{3周目}, \ldots\]

水の量は \(3, 7, 5, 3, 7, 5, 3, 7, 5, \ldots\) と \(N\) 日周期で繰り返します。

解決方法

\(D\) 日間を以下のように分割します：

• 完全な周回数: \(q = \lfloor D / N \rfloor\) 回（\(N\) 人全員がちょうど1回ずつ当番をする周回）
• 余りの日数: \(r = D \bmod N\) 日

完全な1周回では全員が1回ずつ当番をするので、水の合計は \(A_1 + A_2 + \cdots + A_N\) です。これが \(q\) 回繰り返されるので、\(q \times \sum A_i\) で一括計算できます。

余りの \(r\) 日分だけは、開始位置 \(S\) から順に \(r\) 人分の水量を足します。\(r \leq N - 1 \leq 2 \times 10^5\) なので、ループで処理しても十分高速です。

アルゴリズム

1. \(A\) の総和 \(\text{total\_sum} = \sum_{i=1}^{N} A_i\) を計算する。
2. 完全周回数 \(q = \lfloor D / N \rfloor\) と余り \(r = D \bmod N\) を求める。
3. 結果を \(\text{result} = q \times \text{total\_sum}\) で初期化する。
4. 余りの \(r\) 日分について、\(j = 0, 1, \ldots, r-1\) に対して住人番号 \(((S - 1 + j) \bmod N) + 1\) の水量 \(A\) を加算する。
5. \(\text{result}\) を出力する。

具体例

\(N = 3\), \(D = 7\), \(S = 2\), \(A = [5, 3, 7]\) の場合：

• \(\text{total\_sum} = 5 + 3 + 7 = 15\)
• \(q = 7 \div 3 = 2\), \(r = 7 \bmod 3 = 1\)
• 完全周回分: \(2 \times 15 = 30\)
• 余り1日分: 住人 \(2\) の水量 \(A_2 = 3\)
• 合計: \(30 + 3 = 33\)

検算: 当番は住人 \(2,3,1,2,3,1,2\) → 水量 \(3+7+5+3+7+5+3 = 33\) ✓

計算量

• 時間計算量: \(O(N)\)（総和の計算と余り日数分のループ）
• 空間計算量: \(O(N)\)（配列 \(A\) の格納）

実装のポイント

• 0-indexed と 1-indexed の変換: 住人番号は1始まりだが、配列は0始まりなので、(S - 1 + j) % N でインデックスを計算する。

• 整数オーバーフローに注意: \(D\) が最大 \(10^{14}\)、\(\text{total\_sum}\) が最大 \(2 \times 10^9\) 程度なので、積は最大約 \(2 \times 10^{23}\) になる。Python は多倍長整数を扱えるので問題ないが、C++ などでは long long でも溢れる可能性があるため注意が必要。

  ソースコード

N, D, S = map(int, input().split())
A = list(map(int, input().split()))

# Reorder A so that the sequence starts from S
# Day j (1-indexed) is handled by person ((S-1+j-1) % N) + 1
# So the sequence of water amounts is A[S-1], A[S%N], A[(S+1)%N], ...

total_sum = sum(A)
full_cycles = D // N
remainder = D % N

result = full_cycles * total_sum

# Add the remainder days
for j in range(remainder):
    idx = (S - 1 + j) % N
    result += A[idx]

print(result)

---

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