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個に対する計算量をで抑えるという手法があります。問題によっては二分探索などを用いて
になることもありますね。
前処理には累積和やソートなどがありますが、今回は辞書型を用います。ある特定の文字列から始まる文字列の価値の和を辞書型として持つことで、クエリ1個に対する計算量をで抑えることができます。
ではそのような辞書を作ることができるのかについてですが、市場に出回っている文字列それぞれについて、先頭から1文字、2文字、…と繰り返し辞書に登録する、あるいは登録済みであれば価値の和を計算するといった手法で作成が可能です。
計算量についてですが、市場に出回っている文字列の長さの最大値をとおくと辞書を作成する処理について
、クエリに対する処理について
となるため、全体の計算量は
となり十分高速です。
雑記
- 前処理なしの場合、ある文字列がある別の文字列から始まるかの判定にかかる計算量を
とおくと
となります。
- これは制限時間に間に合うのでしょうか…?文字列長と
の関係性が分からないので何とも言えませんね。
- これは制限時間に間に合うのでしょうか…?文字列長と