問題概要
小文字または大文字のアルファベットN文字から成る文字列Sがある。これからQ個の操作を行う。
- 操作ごとに(t_i, x_i, c_i)が与えられる。
- t_i = 1の時、Sのx_i文字目をc_iに変更する。(c_iは大文字または小文字)
- t_i = 2の時、Sの文字を全て小文字にする。
- t_i = 3の時、Sの文字を全て大文字にする。
Q回の操作後のSを出力せよ。
解説
愚直に操作を行う際の計算量
t_iが1の時、2・3の時の操作を愚直(工夫せず)に行う際の計算量を考える。
t_i = 1の時
t_iの文字をc_iに変更する動作は、Sを1文字ずつリスト化【S=abcであれば(リスト) = [‘a’, ‘b’, ‘c’]のように】しておくことで、O(1)で行える。
t_i = 2, 3の時
全て大文字または小文字にする操作を実装するためには、Sに含まれる全ての文字N個に対して操作を行う必要がある(動作を行っても変化しないものも確認する必要がある)。よって、これを行うのに必要な計算量はO(N)である。
以上のことより、最悪計算量はO(NQ)となり、(5×105)2 = 25×1010回程度の計算が必要になるので間に合わない。
計算量の削減
そこで、計算の重い 全て大文字/小文字 にする回数を減らすことを考える。
Sを1文字変更する動作を操作(変)、Sを全て大文字にする動作を操作(大)、小文字にする操作を操作(小)とする。
操作(大)の後に、操作(小)という操作をするのなら、操作(大)は行わなくても結果は変わらない。また、操作(大)と操作(小)の前や間に操作(変)があっても、変更した文字は小文字に変換されるので、操作(大)を行わなくてよい。 そして、操作(大)→操作(小)→操作(大)と3つ以上続いていく場合も、結局最後の操作(大)のみを行うのと結果は変わらない。最後の操作(小)あるいは(大)の後にある操作(変)は、普通に変更すれば良い。
よって、操作(大)と操作(小)は、その2種類の操作のうち最も後にある1つを行うだけで良い。また操作(変)は、状況に関わらず普通に行える。
そのため、実装は次のようなものになる。
- あらかじめ全ての操作を読み込んでおき、操作(大)または操作(小)の中で最後のものは何番目か記録しておく。
- 1~N個目の操作を順に見て行く。
- 操作(変)は普通に行う。
- 操作iが最後の操作(大)または操作(小)でないなら、操作(大)・操作(小)は行わない。
- 操作iが最後の操作(大)または操作(小)であれば、全ての文字列を大文字または小文字に変更する。
計算量はO(N+Q)。
実装(Python)
N = int(input()) S = list(input()) Q = int(input()) # 操作の組を保存するリスト Q_L = [] for i in range(Q): t, x, c = input().split() #t, xは数値に変換 t = int(t) x = int(x) # Q_Lに追加 Q_L.append([t, x, c]) # 操作が全て操作(変)のみの場合のために-1にしておく lastchange = -1 # 操作を大きい順に見ていく for i in range(Q - 1, -1, -1): t, x, c = Q_L[i] # もし操作(大)または(小)なら if t == 2 or t == 3: # 最後の操作は i lastchange = i break # 各操作について for i in range(Q): t, x, c = Q_L[i] # もしt == 1[操作(変)]なら if t == 1: # 変更(リストは0始まりなので1を引く) S[x - 1] = c #もしt == 2またはt == 3なら else: # もし最後の操作(大)または(小)なら if i == lastchange: # 操作(小)の時 if t == 2: for i in range(N): S[i] = S[i].lower() #操作(大)の時 else: for i in range(N): S[i] = S[i].upper() else: # そうでなければ何もしない pass # 文字を結合して出力 print("".join(S))
