前書き
みなさんこんにちはあるるーです！
本日2記事目です!
今回は ABC300-F を解いていきます。
問題
考えたこと
今回の問題では、x を o に変えられる数がちょうど K 個という制約があります。
ここに注目して考えてみます。
この性質を使うとS を M 個つなげた文字列に対して、一番左の o に変える場所を決めたら、右端もおのずと決まってくれます。
そのため、最初は左端をすべて試して、それぞれについて K 個の x を含む範囲を調べればよいのではないかと考えました。
しかし、この方法では S を M 個つなげた文字列全体を調べることになるので、計算量は
$$
O(NM)
$$
となってしまいます。
今回の制約では、これでは全然間に合いません。
そこで、もう少し効率よく計算できないか考えてみます。
実装の工夫
ここでさらに考えてみます。
K がある程度大きければ、どんな左端の決め方をしても、S の塊がいくつか必ず入ってしまいます。
例えば、次のようなイメージです。
この「どんな場合でも必ず入る S の塊」については、毎回調べる必要はありません。
あらかじめ、必ず入る S の個数を計算しておき、その部分については先に x を o に変えたことにしてしまいます。
S に含まれる x の個数を cnt_x とすると、完全に含められる S の個数は、
K // cnt_x
で求められます。
ただし、残りの部分を調べるためには S の両端を考える必要があるので、最大でも M - 2 個までにしておきます。
したがって、
cnt_set = min(K // cnt_x, M - 2)
とすることができます。
そして、この完全な S の塊ですでに使用した分を K から引きます。
K -= cnt_set * cnt_x
これで、残りの部分だけを考えればよくなります。
残りの部分をどうするか
残った左右の部分については、S + S だけを考えれば十分です。
あとは、残りの x を o に変えられる数を K として、尺取り法を使います。
右端を1つずつ右に伸ばしていき、区間内の x の個数が K を超えたら、左端を右に動かして条件を満たすようにします。
これによって、x が K 個以下となる最長の区間を求めることができます。
最後に、最初に完全に含めた S の塊の長さを足せば答えになります。
なお、実装上の注意点として、M = 1 の場合だけ少し違う処理が必要です。
M = 1 の場合は S を2個つなげる必要がないので、T = S とします。
実際の実装
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N,M,K=map(int,input().split())
S=list(input().strip())
cnt_x=S.count("x") #Sのxの個数
if M>=2:
cnt_set=min(K//cnt_x,M-2) #完全に埋められる文字列Sの個数
T=S+S
else:
cnt_set=0
T=S
K-=cnt_set*cnt_x
ans=0
left=0
right=0
cnt=0
while right<len(T):
if T[right]=="x":
cnt+=1
while cnt>K:
if T[left]=="x":
cnt-=1
left+=1
ans=max(ans,right-left+1)
right+=1
print(ans+N*cnt_set)
今回のポイントは、最初から S を M 個すべて並べて考えるのではなく、
- どの区間にも必ず入る
Sの塊を先に処理する - 残った部分だけを
S + Sで考える - 残りは尺取り法で最大値を求める
というように分けて考えることでした。
これによって、巨大な M 個分の文字列を実際に作ることなく答えを求めることができます。