概要

この問題は、各会員がジムに通う曜日パターンと、キャンペーン期間（連続する日付の範囲）が与えられたとき、各会員が \(W\) 週間で獲得するトレーニングポイントの合計を求める問題です。

考察

素朴なアプローチとその限界

週の数 \(W\) が最大で \(10^9\)（営業日数は最大 \(7 \times 10^9\) 日）と非常に大きいため、1日ずつシミュレーションを行ってポイントを計算すると、実行時間制限（TLE）になってしまいます。また、会員数 \(N\) やキャンペーン数 \(M\) も最大 \(2 \times 10^5\) と大きいため、会員ごとにすべてのキャンペーンとの重複を個別に判定することもできません。

重要な気づき

獲得ポイントは、以下の2つの要素に分解して考えることができます。 1. 基本ポイント: キャンペーンに関係なく、ジムに来館した日数（1日につき \(1\) ポイント） 2. キャンペーンポイント: 来館した日がキャンペーン期間に含まれる回数の総和（1回につき \(+1\) ポイント）

このうち、基本ポイントは非常に簡単に計算できます。会員 \(i\) が1週間に通う日数を \(D_i\) とすると、 \(W\) 週間で獲得する基本ポイントは単に \(W \times D_i\) となります。

問題はキャンペーンポイントの計算です。 ここで、1週間は7日という短い周期で繰り返される点に着目します。 各キャンペーン \(j\) の期間 \([S_j, E_j]\) について、「その期間中に、各曜日（第 \(1\) 日目〜第 \(7\) 日目）がそれぞれ何回含まれているか」を数え上げることができます。

全キャンペーンにわたって、第 \(d\) 日目（\(1 \leq d \leq 7\)）がキャンペーン期間に含まれた延べ回数を \(tot[d]\) とします。 これが事前に計算できれば、会員 \(i\) が獲得するキャンペーンポイントは、会員 \(i\) が通う曜日の \(tot[d]\) の総和として、会員ごとに高速に求めることができます。

さらに、会員が通う曜日のパターン \((L_i, R_i)\) は、 \(1 \leq L_i, R_i \leq 7\) より、高々 \(7 \times 7 = 49\) 通りしか存在しません。したがって、あらかじめ 49 通りすべてのパターンについて「基本ポイント（1週間の日数）」と「キャンペーンポイント（通う曜日の \(tot[d]\) の総和）」を前計算（テーブル化）しておけば、各会員のクエリに対して \(O(1)\) で回答できます。

キャンペーン期間内の曜日出現回数の高速な数え上げ

あるキャンペーンの期間 \([S_j, E_j]\) において、特定の曜日 \(d\) が何回現れるかを \(O(1)\) で計算する方法を考えます。 0-indexed で考えるために、半開区間 \([s, e) = [S_j - 1, E_j)\) とします。

通算第 \(x\) 日目までに、曜日 \(d\)（\(1 \leq d \leq 7\)）が何回来るかは、 \(x\) を 7 で割った商 \(q\) と余り \(r\)（すなわち \(x = 7q + r\)）を用いて、以下のように表せます。 $\(\text{count}(x, d) = q + \begin{cases} 1 & (d \leq r) \\ 0 & (d > r) \end{cases}\)$

これを利用すると、区間 \([s, e)\) に含まれる曜日 \(d\) の回数は、以下の差分として \(O(1)\) で求まります。 $\(\text{count}(e, d) - \text{count}(s, d)\)$

これをすべてのキャンペーン（\(M\) 個）に対して、各曜日 \(d \in \{1, \dots, 7\}\) について足し合わせることで、配列 \(tot\) を \(O(M)\) で構築できます。

アルゴリズム

1. キャンペーンの集計:

   • サイズ 8 の配列 \(tot\) を 0 で初期化します（1-indexed で曜日 \(1\) から \(7\) を管理するため）。
   • 各キャンペーン \(j = 1, \dots, M\) について：
     • \(s = S_j - 1\), \(e = E_j\) とします。
     • \(s, e\) それぞれを 7 で割った商と余りを求めます。

          - `q_s, r_s = divmod(s, 7)`
          - `q_e, r_e = divmod(e, 7)`
       

     • 各曜日 \(d \in \{1, \dots, 7\}\) について、期間内に含まれる回数を計算し、 \(tot[d]\) に加算します。

2. パターンの前計算:

   • \(7 \times 7\) の二次元配列 days_val と camp_val を用意します。
   • すべての \(L, R \in \{1, \dots, 7\}\) の組について：
     • \(L\) から \(R\) までの曜日（巡回を考慮）を列挙し、その日数を days_val[L][R] に、それらの曜日の \(tot[d]\) の総和を camp_val[L][R] に記録します。

3. 会員ごとの答えの計算:

   • 各会員 \(i = 1, \dots, N\) について、答えは次のように求まります。 $\(\text{獲得ポイント} = W \times \text{days\_val}[L_i][R_i] + \text{camp\_val}[L_i][R_i]\)$
   • これを出力します。

計算量

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

  • キャンペーンの集計: \(M\) 個のキャンペーンそれぞれに対して 7 回のループを回すため、 \(O(7M) = O(M)\) 時間。
  • パターンの前計算: \(7 \times 7\) 通りの組み合わせに対して、高々 7 日分の走査を行うため、 \(O(7^3) = O(1)\) 時間。
  • 会員ごとの計算: \(N\) 人の会員に対してそれぞれ \(O(1)\) で計算するため、 \(O(N)\) 時間。
  • 全体として \(O(N + M)\) となり、実行時間制限に十分間に合います。

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

  • 入力データおよび出力結果を保持するために \(O(N + M)\) のメモリを使用します。
  • 集計用および前計算用の配列はサイズが定数（最大でも \(8 \times 8\)）であるため、追加の空間は \(O(1)\) です。

実装のポイント

• 大きな値の処理: \(W\) が最大 \(10^9\) であり、会員が獲得する総ポイントは \(64\) ビット整数型（Python では自動的に多倍長整数として扱われます）が必要になる点に注意してください。

• 巡回区間の処理: \(L_i > R_i\) の場合、曜日が週をまたぎます。例えば \(L_i = 6, R_i = 2\) のときは、\([6, 7] \cup [1, 2]\) のように、 \(7\) で折り返してリストを結合することで正しく曜日の集合を表現できます。

  ソースコード

import sys


def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    W = int(input_data[1])
    M = int(input_data[2])

    L_R = list(map(int, input_data[3 : 3 + 2 * N]))
    S_E = list(map(int, input_data[3 + 2 * N : 3 + 2 * N + 2 * M]))

    tot = [0] * 8

    for j in range(M):
        s = S_E[2 * j] - 1
        e = S_E[2 * j + 1]

        q_e, r_e = divmod(e, 7)
        q_s, r_s = divmod(s, 7)

        diff_q = q_e - q_s
        for d in range(1, 8):
            tot[d] += diff_q + (1 if d <= r_e else 0) - (1 if d <= r_s else 0)

    days_val = [[0] * 8 for _ in range(8)]
    camp_val = [[0] * 8 for _ in range(8)]

    for l in range(1, 8):
        for r in range(1, 8):
            if l <= r:
                days = list(range(l, r + 1))
            else:
                days = list(range(l, 8)) + list(range(1, r + 1))

            days_val[l][r] = len(days)
            camp_val[l][r] = sum(tot[d] for d in days)

    ans = []
    for i in range(N):
        l = L_R[2 * i]
        r = L_R[2 * i + 1]
        pt = W * days_val[l][r] + camp_val[l][r]
        ans.append(str(pt))

    print("\n".join(ans))


if __name__ == "__main__":
    main()

---

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