あるエンジニアのAtCoder奮闘記

東京都港区にあるアミフィアブル株式会社のエンジニアが、AtCoderで解いた問題について振り返ったりしていく会社公認のブログです。

Paiza プログラミング練習問題 S - 文字列収集 (Python)

Paiza プログラミング練習問題 Sランク相当 Python

irisruneです。先週に引き続き2度目のPaiza練習問題記事です。

問題

前回とは対照的に、Sランク相当ではありますが正解率が高めとなっております。とはいえSランク問題に挑戦するような人が母数なのでそこまで簡単なわけではないです。

import sys
import numpy as np


def main():
    n, m = [int(x) for x in input().split()]
    dic = {}
    for i in range(n):
        s, p = input().split()
        for j in range(len(s)):
            subs = s[0:j+1]
            if subs in dic:
                dic[subs] += int(p)
            else:
                dic[subs] = int(p)
    for k in range(m):
        q = input()
        if q in dic:
            print(dic[q])
        else:
            print(0)


main()

複数のクエリに対する解答を求める問題の定石として、前処理を行うことでクエリ1個に対する計算量を $O(1)$ で抑えるという手法があります。問題によっては二分探索などを用いて $O(\log N)$ になることもありますね。

前処理には累積和やソートなどがありますが、今回は辞書型を用います。ある特定の文字列から始まる文字列の価値の和を辞書型として持つことで、クエリ1個に対する計算量を $O(1)$ で抑えることができます。

ではそのような辞書を作ることができるのかについてですが、市場に出回っている文字列それぞれについて、先頭から1文字、2文字、…と繰り返し辞書に登録する、あるいは登録済みであれば価値の和を計算するといった手法で作成が可能です。

計算量についてですが、市場に出回っている文字列の長さの最大値を $L_S(\leq100)$ とおくと辞書を作成する処理について $O(NL_S)$ 、クエリに対する処理について $O(M)$ となるため、全体の計算量は $O(NL_S+M)$ となり十分高速です。

雑記

前処理なしの場合、ある文字列がある別の文字列から始まるかの判定にかかる計算量をとおくととなります。
- これは制限時間に間に合うのでしょうか…？文字列長と $O(\alpha)$ の関係性が分からないので何とも言えませんね。