JOI 2023/2024 2次予選問題2 解答解説 | 秀英塾コラム

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

対象外：1次予選で4問完答できない人　または　2次予選突破する実力がすでにある人

B – 買い物 2 (Shopping 2)

まずは問題文を正しく理解するところから始めましょう。「N個の商品が左から順番に並んでいて、L番目からR番目までの商品を1個ずつ買ったときの合計金額を求めよ」という問題を、お客さんの数Q人分行ってほしい。ただし、お客さんが来た日Tと商品の種類番号Aが一致する場合は、その商品は半額になる。という設定です。

解法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 i in range(q):
    t, l, r = map(int, input().split())
    l -= 1
    r -= 1
    ans = 0
    for j in range(l, r + 1):
        if a[j] == t:
            ans += p[j] // 2
        else:
            ans += p[j]
    print(ans)

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

解法2: 累積和（47点）

「L番目からR番目までの値の合計の計算をQ回分繰り返す」という問題のパターンでは、累積和というテクニックが非常に有効です。

《参考》累積和を何も考えずに書けるようにする！ https://qiita.com/drken/items/56a6b68edef8fc605821

今回の問題では、T日目には商品番号AがTと同じ商品が半額という条件があるので、通常の累積和に加えてひと工夫が必要になります。例えば、セールはM日間続き、1<=Tk<=Mなので、M日分の累積和を事前に作ることが考えられます。以下はこの方針で作成したプログラムです。

n, m, q = map(int, input().split())
pa = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
for i in range(n):
    p, a = map(int, input().split())
    for j in range(1, m + 1):
        if j == a:
            pa[j][i + 1] = pa[j][i] + p // 2
        else:
            pa[j][i + 1] = pa[j][i] + p

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

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

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

満点まであと少しです。 M日分の累積和を作るところがボトルネックになっているので、その部分を改良しましょう。

先程のプログラムでは、1つの商品に対してセール日以外の累積和の計算も必要になるため無駄が多いプログラムになっています。そこで、

種類数分、同じ種類番号をもつものだけで累積和をとっておく（累積和はm_sumとします）
累積和とは別に、同じ種類番号をもつ商品の商品番号をリストに管理しておく（m_indexesとします）
T日目に、種類番号がTである商品のうち商品番号がLからRの範囲にはいるものをm_indexedから2分探索でしらべ、その値をもとにm_sumから購入した半額対象商品の合計金額を調べる。
全商品の累積和（p_sum）をもとに、購入した商品の定価から、半額対象商品の合計の半分を引いたものが、そのお客さんの購入金額となる

この方針で作成したプログラムが以下になります。

def lower_bound(temp_list, key):
    left = -1
    right = len(temp_list)
    while right - left > 1:
        mid = (left + right) // 2
        if temp_list[mid] >= key:
            right = mid
        else:
            left = mid
    return right


n, m, q = map(int, input().split())
p_sum = [0] * (n + 1)
m_indexes = [[0] for _ in range(m + 1)]  # m_indexes[種類][番目]　全アイテム内での通し番号
m_sum = [[0] for _ in range(m + 1)]  # m_sum[種類][番目] 当該種類番号での累積和

for i in range(n):
    p, a = map(int, input().split())
    p_sum[i + 1] = p_sum[i] + p
    m_indexes[a].append(i + 1)
    m_sum[a].append(m_sum[a][-1] + p)

# print(p_sum)
# print(m_indexes)
# print(m_sum)

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

    left_bound = lower_bound(m_indexes[t], l)
    right_bound = lower_bound(m_indexes[t], r)

    if right_bound == len(m_sum[t]):
        ans -= (m_sum[t][right_bound - 1] - m_sum[t][left_bound - 1]) // 2
    elif r < m_indexes[t][right_bound]:
        ans -= (m_sum[t][right_bound - 1] - m_sum[t][left_bound - 1]) // 2
    else:
        ans -= (m_sum[t][right_bound] - m_sum[t][left_bound - 1]) // 2
    print(ans)

この解法の計算量は O(N + Q log N) です。事前処理が O(N)、各クエリの処理が O(log N) となります。小課題をすべて合格できるので100点が得られます。

ポイント:

「範囲の合計」には累積和が有効

「範囲内の要素を特定」には二分探索が有効

これら2つを組み合わせることで効率的に解ける

計算量の比較

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

まとめ

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