Atcoder Beginner Contest 372の学習

Atcoder Beginner Contestも3回目を迎えました。今回こそはCまで解けるかと思いきや、TLEとなりまたもや3冠ならず...

実はしっかり復習できていないのが問題なのではと思いQiita投稿を始めることにしました。今回はC問題で詰まったのでその復習がてら記事を書いていきます。

Atcoder Beginner Contest 372 C問題

さて、以下が私の提出したコードになります。

N, Q = map(int, input().split())
S = input()  
data = [] 

for _ in range(Q):
    X, C = input().split()
    X = int(X)  
    data.append((X, C))  

for i in range(Q):
    X, C = data[i]  
    S = list(S)  
    S[X - 1] = C  
    S = ''.join(S)  
    print(S.count('ABC'))  

はい、まあThe・初心者って感じのコードとなっております。そこでコンテスト終了後に色々試してみた結果、大きく3つの問題点が浮かび上がりました。

わざわざ配列に代入してしまっていた

はい、そんなことしなくてもfor文回してその都度代入からの文字列'ABC'のカウントをすればよかったんですな...

これだと代入してからまた取り出すという二度手間が発生してしまい美しくない。最終的に配列として出力する必要がない問題に関しては気をつけなければと思った次第です。

S = list(S)をfor文の中に入れてしまっていた

これはコンテスト中意識できていませんでしたが、わざわざSを配列型にした後でX番目をCと入れ替えて再度文字列に直す動作を毎回繰り返していたらメモリ食ってしゃーないって話ですよね。でも今のコードのままではどうしようもなさそう...
そこで次の問題に対する対処法が活きてくるのでした。

Sの文字列を毎回全て考慮するのは効率が悪かった

はい、文字列内の変更箇所の前後にさえ注目できていればよかったんです。具体的にはX番目の２つ後ろから2つ後までの中で'ABC'カウントがどう変化するかだけを考えるのです。

こうしてできたコードが以下になりました。

N, Q = map(int, input().split())
S = input()  
counter = S.count('ABC')
S = list(S) 

for _ in range(Q):
    X, C = input().split()
    X = int(X)  
    counter -= ''.join(S[max(X - 3, 0):X + 2]).count('ABC')
    S[X - 1] = C  
    counter += ''.join(S[max(X - 3, 0):X + 2]).count('ABC')
    print(counter)

ここでmax(X-3, 0)としているのは、もしXが1、2番目だった場合にきちんとS[0]を先頭とする文字列として扱いたいからです。

最後に

ただコンテストを受けるだけでなく、今の自分が書ける最大限可読性、計算量に配慮したコードを書けるように学んだことをアウトプットしていこうと思います。