文字列収集 (paizaランク S 相当) Python解説

自己紹介

大阪大学2回生で競技プログラミング部rainbou副部長、Atcoder緑
X:https://x.com/e4h99rhQ7I24670

問題文　文字列収集 (paizaランク S 相当)　URL

所感

初見問題として解くのはかなり難しいと思う。
AtcoderだとC問題くらいでdiff600程度だと予想（ざる予想）

解法

文字列ソート、累積和、二分探索を使う。
まず、文字列と数字のペアを文字列でソートする。順番は文字列が最初に与えられるのできにせずにいつものようにソートすればよい。
次にそのリストの累積和を作っておく。itertoolsでも累積和を作れるという話を聞いたことがあるが、僕は知らないので手作業で作っていく。
あとは、M個のクエリが飛んでくるたびに二分探索を２回して買う必要のある範囲を絞っていく。
ここがボトルネックとなり計算量はO（MNlogN）
必要な範囲が求められれば、あとは先ほど作っておいた累積和をてきとうに出力しておしまい。

import bisect

N, M = map(int, input().split())
A = [list(map(str, input().split())) for _ in range(N)]
S = [0]
A.sort()

for i in range(N):
    A[i][1] = int(A[i][1])
    S.append(S[-1]+A[i][1])


for i in range(M):
    q = input()
    l = bisect.bisect_left(A, [q, -1])
    r = bisect.bisect_right(A, [q+'{', 0])

    print(S[r]-S[l])

以下雑談

paizaではbisectは使えるらしい。
はやいとこsortedcountainersも使えるようにしてほしい。現在は200行くらいコードべたばりしなければ使えない。悲しい。