概要

各会員が \(W\) 週間で獲得するトレーニングポイントの合計を求める問題。ポイントは「来館日数 + キャンペーン期間中の来館によるボーナス」で構成される。曜日が7種類しかないことを利用し、曜日ごとにキャンペーン日数を集計することで高速に解く。

考察

重要な気づき

ポイントの分解: 会員が通算第 \(k\) 日目に来館して得るポイントは \(1 + c\)（\(c\) はその日に適用されるキャンペーン数）なので、全体のポイントを次のように分解できます：

\[\text{合計ポイント} = \underbrace{\text{来館日数（ベースポイント）}}_{\text{days\_per\_week} \times W} + \underbrace{\text{キャンペーンボーナス}}_{\text{各キャンペーン期間中の来館日数の合計}}\]

素朴なアプローチの問題

\(W\) が最大 \(10^9\) なので、通算 \(7W\) 日（最大70億日）を1日ずつシミュレーションするのは不可能です。

解決のカギ：曜日は7種類しかない

会員の来館パターンは 曜日のみ で決まります。つまり、ある会員がキャンペーン \([S_j, E_j]\) 中に何日来館するかは、「区間 \([S_j, E_j]\) に曜日 \(d\) が何回現れるか」の合計で求まります。

さらに、全キャンペーンについてまとめると： $\(\text{ボーナス} = \sum_{d \in \text{通う曜日の集合}} \text{total\_camp}[d]\)\( ここで \)\text{total_camp}[d]\( は「全キャンペーン期間を合わせたとき、曜日 \)d$ が合計何回登場するか」です。

アルゴリズム

1. 曜日ごとのキャンペーン日数を集計:
   各キャンペーン \([S_j, E_j]\) について、曜日 \(d\)（\(1 \leq d \leq 7\)）が区間内に何回現れるかを計算し、total_camp[d] に加算する。
   区間 \([S, E]\) で曜日 \(d\) の出現回数は、\(k \equiv d \pmod{7}\) を満たす整数 \(k\) の個数として \(O(1)\) で計算可能。

2. 各会員の回答を計算:

   • ベースポイント \(= \text{days\_per\_week} \times W\)
   • ボーナス \(= \sum_{d \in \text{通う曜日}} \text{total\_camp}[d]\)
   • 答え \(= \text{ベースポイント} + \text{ボーナス}\)

具体例

\(L=6, R=2\) の会員は曜日 \(\{6,7,1,2\}\) に通う（週4日）。\(W=3\) なら： - ベースポイント \(= 4 \times 3 = 12\) - ボーナス \(= \text{total\_camp}[6] + \text{total\_camp}[7] + \text{total\_camp}[1] + \text{total\_camp}[2]\)

計算量

• 時間計算量: \(O(7M + 7N) = O(M + N)\)
  • 各キャンペーンにつき7曜日分の計算、各会員につき最大7曜日分の加算
• 空間計算量: \(O(N + M)\)

実装のポイント

• 区間内の特定曜日の数え方: 曜日 \(d\) が区間 \([S, E]\) に何回現れるかは、「\([1, X]\) で \(k \bmod 7 = t\)（\(t = d \bmod 7\)）を満たす \(k\) の個数」を関数化し、\(\text{cnt}(E) - \text{cnt}(S-1)\) で求める。

• \(L > R\) の場合の曜日集合: 巡回区間なので range(L, 8) と range(1, R+1) を結合して扱う。

• \(W\) が大きいがベースポイントは単なる掛け算なので問題ない。キャンペーン数 \(M\) は最大 \(2 \times 10^5\) なので各曜日ごとの集計も十分高速。

  ソースコード

import sys
from itertools import accumulate

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    W = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    members = []
    for i in range(N):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        members.append((L, R))
    
    campaigns = []
    for j in range(M):
        S = int(input_data[idx]); idx += 1
        E = int(input_data[idx]); idx += 1
        campaigns.append((S, E))
    
    # For each member, we need:
    # 1) Base points = number_of_days_per_week * W (each visit gives 1 point)
    # 2) Campaign bonus: for each campaign [S, E], count how many days in [S, E] 
    #    the member visits the gym.
    
    # Member i visits on days where (k-1) % 7 + 1 is in their day set.
    # If L <= R: days {L, L+1, ..., R}
    # If L > R: days {L, L+1, ..., 7, 1, 2, ..., R}
    
    # For a campaign [S, E], we need to count visits of member i in that range.
    # A member visits day k if day_of_week(k) is in their set.
    # day_of_week(k) = (k-1) % 7 + 1, i.e., 1-indexed.
    
    # Count of day d (1..7) in range [S, E]:
    # We need count of k in [S, E] where (k-1)%7 = d-1, i.e., k ≡ d (mod 7) (with 7≡0 mapped to 7)
    # Actually k mod 7: k=1->1, k=2->2, ..., k=7->0. Let's use (k-1)%7 giving 0..6 for days 1..7.
    
    # For range [S, E], count of k where (k-1)%7 = r (r=0..6):
    # This is count of k in [S, E] where k ≡ r+1 (mod 7).
    # = floor((E - (r+1))/7) + 1 if r+1 adjusted to be in [S, E], else ...
    # Let's use: count of integers in [S, E] ≡ t (mod 7) where t in {1,...,7}, treat 7 as 0.
    
    # Precompute for each campaign, the count of each weekday in [S, E].
    # Then for each member, sum over campaigns the count of their active weekdays.
    
    # But N, M up to 2e5, and weekdays only 7, so we can:
    # For each weekday d (1..7), compute total campaign-day count across all campaigns.
    # Then for each member, bonus = sum over d in their set of total_campaign_count[d].
    
    # count of k in [S,E] with weekday d: 
    # weekday d means (k-1)%7 = d-1, i.e., k ≡ d (mod 7) (where d=7 means k≡0 mod 7)
    
    def count_weekday_in_range(S, E, d):
        # count of k in [S, E] such that (k-1) % 7 == d-1
        # equivalently k % 7 == d % 7
        # Let t = d % 7  (so d=7 -> t=0, d=1 -> t=1, etc.)
        t = d % 7
        # count of k in [S, E] with k%7 == t
        # = floor(E/7)*7 adjusted...
        # Use: count in [1, X] with k%7==t: if t==0: floor(X/7), else floor((X-t)/7)+1 if t<=X else 0
        def cnt(X):
            if X <= 0:
                return 0
            if t == 0:
                return X // 7
            else:
                if t > X:
                    return 0
                return (X - t) // 7 + 1
        return cnt(E) - cnt(S - 1)
    
    # Accumulate total campaign counts per weekday
    total_camp = [0] * 8  # index 1..7
    for S, E in campaigns:
        for d in range(1, 8):
            total_camp[d] += count_weekday_in_range(S, E, d)
    
    out = []
    for L, R in members:
        # days per week
        if L <= R:
            days_per_week = R - L + 1
            day_set = range(L, R + 1)
        else:
            days_per_week = 7 - L + 1 + R
            day_set = list(range(L, 8)) + list(range(1, R + 1))
        
        base = days_per_week * W
        bonus = 0
        for d in day_set:
            bonus += total_camp[d]
        
        out.append(str(base + bonus))
    
    sys.stdout.write('\n'.join(out) + '\n')

solve()

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