概要

\(N\) 人の住人が決まった順番で \(D\) 日間にわたり水やりを行います。\(D\) が非常に大きいため、愚直に 1 日ずつシミュレーションするのではなく、水やりの周期性（サイクル）を利用して計算量を抑える問題です。

考察

1. 愚直なシミュレーションの限界

\(D\) 日間、毎日誰が当番かを判定して水の量を足していく方法が最も単純です。しかし、制約を見ると \(D \leq 10^{14}\) と非常に大きな値になっています。1 秒間に計算できる回数は一般的に \(10^8\) 回程度であるため、この方法では実行時間制限（TLE）に間に合いません。

2. 周期性に着目する

住人の当番は \(N\) 人で 1 サイクルとなっており、1 サイクル（\(N\) 日間）で使われる水の合計量は常に一定です。 - 1 サイクルで使われる水の合計： \(S_{total} = A_1 + A_2 + \dots + A_N\)

\(D\) 日間のうち、このフルサイクルが何回繰り返されるかを考えると、計算を大幅に省略できます。 - フルサイクルの回数： \(full\_cycles = D \div N\) （商） - サイクルに入り切らない余りの日数： \(remainder\_days = D \bmod N\) （余り）

これにより、合計量は (full_cycles × Stotal) + (余りの日数分の水の量) で求められます。

3. 余りの日数の計算

余りの日数（\(0 \leq remainder\_days < N\)）については、1 日目の当番 \(S\) から数えて \(remainder\_days\) 人分を計算すればよいです。 この部分は最大でも \(N\) 日分なので、累積和（Prefix Sum）を用いることで、途中で番号が \(N\) から \(1\) に戻る場合（ラップアラウンド）も含めて効率的に計算できます。

アルゴリズム

1. 累積和の準備: 住人 \(1\) から \(i\) までの水の合計量を prefix_sum[i] とした配列を作成します。これにより、任意の区間の合計を \(O(1)\) で計算可能になります。
2. サイクルの計算: \(D\) を \(N\) で割り、商（サイクルの回数）と余り（端数の日数）を求めます。
3. 合計の算出:
   • フルサイクル分： 商 × prefix_sum[N]
   • 端数分： 住人 \(S\) から数えて「余り」の日数分だけ足します。
     • \(S + remainder\_days - 1 \leq N\) の場合： 単純な区間和。
     • \(N\) を超える場合： 「\(S\) から \(N\) まで」と「\(1\) から残りの日数分」の 2 つに分けて加算します。

計算量

• 時間計算量: \(O(N)\)
  • 累積和の構築に \(O(N)\) かかりますが、その後の計算は \(O(1)\) です。\(D\) の大きさに依存せず、制限時間内に十分間に合います。
• 空間計算量: \(O(N)\)
  • 長さ \(N\) の配列（住人の水の量および累積和）を保持するために必要です。

実装のポイント

• 0-indexed への変換: プログラム上では住人番号 \(1 \dots N\) を \(0 \dots N-1\) として扱うと、配列のインデックスや余りの計算がスムーズになります。

• 大きな数の扱い: 合計値は最大で \(D \times \max(A_i) = 10^{14} \times 10^4 = 10^{18}\) に達します。Python では自動的に多倍長整数として扱われますが、他の言語（C++ など）を使用する場合は 64bit 整数型（long long など）を使用する必要があります。

  ソースコード

import sys

def solve():
    # 入力を取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    d = int(input_data[1])
    s = int(input_data[2])
    a = list(map(int, input_data[3:]))
    
    # 累積和を計算
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + a[i]
    
    total_a = prefix_sum[n]
    
    # 全体のサイクル数と余りの日数を計算
    full_cycles = d // n
    remainder_days = d % n
    
    # フルサイクルの合計
    ans = full_cycles * total_a
    
    # 余りの日の計算
    if remainder_days > 0:
        # 1日目の当番は住人 S (0-indexed で S-1)
        start_idx = s - 1
        # 連続する remainder_days 分の合計を求める
        # 範囲が配列の末尾を越えない場合
        if start_idx + remainder_days <= n:
            ans += prefix_sum[start_idx + remainder_days] - prefix_sum[start_idx]
        else:
            # 範囲が配列の末尾を越えて先頭に戻る場合
            # 末尾までの和
            ans += prefix_sum[n] - prefix_sum[start_idx]
            # 先頭からの残りの和
            remaining_after_wrap = remainder_days - (n - start_idx)
            ans += prefix_sum[remaining_after_wrap]
            
    print(ans)

if __name__ == "__main__":
    solve()

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