JOI 2023/2024 2次予選 問題2 解答解説

B – 買い物 2 (Shopping 2)

この解説は本選（Aランク）を目指す生徒向けの内容です。一部省略している部分があります。

問題概要

N個の商品が並んでおり、各商品には価格 P と種類番号 A が設定されています。 Q人の客がそれぞれ来店日 T と購入範囲 L〜R を指定し、範囲内の商品を購入します。 来店日 T と商品の種類番号 A が一致する場合、その商品は 50%割引 になります。 各客の合計購入金額を求めてください。

AtCoderで問題を見る →

解法1: 愚直解（15点）

各クエリに対して、範囲内の商品を1つずつ確認して合計金額を計算します。

n, m, q = map(int, input().split())
p = [0] * n
a = [0] * n
for i in range(n):
    p[i], a[i] = map(int, input().split())

for _ in range(q):
    t, l, r = map(int, input().split())
    l -= 1  # 0-indexed に変換

    ans = 0
    for j in range(l, r):
        if a[j] == t:
            ans += p[j] // 2  # 割引適用
        else:
            ans += p[j]
    print(ans)

この解法の計算量は O(NQ) です。N, Q が最大200,000の場合、最悪で 4×10¹⁰ 回の計算が必要となり、タイムアウトします。

解法2: 累積和（47点）

「範囲の合計」を高速に求めるには 累積和 が有効です。各種類番号ごとに累積和を事前計算しておきます。

n, m, q = map(int, input().split())
p = [0] * n
a = [0] * n
for i in range(n):
    p[i], a[i] = map(int, input().split())

# 全商品の累積和
total_sum = [0] * (n + 1)
for i in range(n):
    total_sum[i + 1] = total_sum[i] + p[i]

# 各種類番号ごとの累積和
category_sum = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(n):
    for day in range(1, m + 1):
        category_sum[day][i + 1] = category_sum[day][i]
        if a[i] == day:
            category_sum[day][i + 1] += p[i]

for _ in range(q):
    t, l, r = map(int, input().split())
    l -= 1

    # 範囲内の合計金額
    range_total = total_sum[r] - total_sum[l]
    # 範囲内の割引対象商品の合計金額
    discount_total = category_sum[t][r] - category_sum[t][l]
    # 割引適用後の金額
    ans = range_total - discount_total // 2
    print(ans)

この解法の計算量は O(NM + Q) です。各クエリは O(1) で処理できますが、累積和の事前計算に O(NM) かかります。M が大きい場合（M ≤ 200,000）はメモリと時間の両方で厳しくなります。

解法3: 二分探索（100点）

各種類番号の商品を 位置でソート しておき、クエリの範囲 [L, R] に含まれる商品を 二分探索 で特定します。

import bisect

n, m, q = map(int, input().split())
p = [0] * n
a = [0] * n
for i in range(n):
    p[i], a[i] = map(int, input().split())

# 全商品の累積和
total_sum = [0] * (n + 1)
for i in range(n):
    total_sum[i + 1] = total_sum[i] + p[i]

# 各種類番号ごとに (位置, 累積和) を記録
category_data = [[] for _ in range(m + 1)]
for day in range(1, m + 1):
    cum = 0
    for i in range(n):
        if a[i] == day:
            cum += p[i]
            category_data[day].append((i, cum))

for _ in range(q):
    t, l, r = map(int, input().split())
    l -= 1

    # 範囲内の合計金額
    range_total = total_sum[r] - total_sum[l]

    # 二分探索で範囲内の割引対象を特定
    data = category_data[t]
    if not data:
        print(range_total)
        continue

    positions = [d[0] for d in data]
    left_idx = bisect.bisect_left(positions, l)
    right_idx = bisect.bisect_left(positions, r)

    if left_idx >= right_idx:
        print(range_total)
    else:
        left_sum = data[left_idx - 1][1] if left_idx > 0 else 0
        right_sum = data[right_idx - 1][1]
        discount_total = right_sum - left_sum
        ans = range_total - discount_total // 2
        print(ans)

この解法の計算量は O(N + Q log N) です。事前処理が O(N)、各クエリの処理が O(log N) となります。

ポイント:

• 「範囲の合計」には累積和が有効
• 「範囲内の要素を特定」には二分探索が有効
• これら2つを組み合わせることで効率的に解ける

計算量の比較

解法	計算量	得点
愚直解	O(NQ)	15点
累積和	O(NM + Q)	47点
二分探索	O(N + Q log N)	100点

まとめ

この問題では、単純な累積和だけでは不十分で、二分探索と組み合わせる必要がありました。 競技プログラミングでは、複数のテクニックを組み合わせて解く問題がよく出題されます。 基本的なアルゴリズムをしっかり理解した上で、応用力を身につけていきましょう。