【AtCoder 緑色を目指して】ABC372【競技プログラミング】

技術ブログ 競技プログラミング

はじめに

こんにちは、先週ABC371への参加をサボった駒嶺です。今回はAtCoder Beginner Contest 372の所感です。
今回もPythonで解いていきます。

A – delete .

文字列から”.”を削除します。

S = input()

print(S.replace(".",""))

replaceで”.”を空文字に置換しました。

B – 3^A

正整数Mを3のAi乗の総和で表すことができる非負整数列Aを求めます。

解答

M = int(input())
A = []
three = [3**i for i in range(12)]
while M:
    for i in range(11):
        r = M % three[i+1]
        if r:
            A.extend([j]*(r//three[i]))
            M -= r
            break
        else:
            continue

print(len(A))
print(*A)

下の桁から順にその桁で消化しないといけない数（＝次の桁で割り切れない数）だけ桁数を配列Aに追加していきました。
3のn乗が何回も出てくるので配列化しましたが不要だったと思います。

上記のコードで実装した後に気がつきましたが、これはほとんど3進数への変換ですね。
なので

解答（コンテスト終了後）

M = int(input())
A = []
digit = 0
while M:
    r = M % 3
    M = (M - r) // 3
    A.extend([digit]*r)
    digit += 1
print(len(A))
print(*A)

「整数をnで割って余りを求める」を繰り返して余りを下の桁から順に並べていくとn進法になる。という高校あたりで習ったような基数変換の手順を思い出して実装しました。
基数変換とは違って余りはその数だけ桁数を配列Aに追加していきます。
先ほどのコードよりもスマートですね。

C – Count ABC Again

文字列SのX番目の文字を文字Cに置き換えて、Sに部分文字列”ABC”が何個あるか答える。をQ回繰り返します。

解答

N, Q = map(int, input().split())
S = input()
S_list = ["Z","Z"] + list(S) + ["Z","Z"]

def cnt_ABC(s):
    return (len(s) - len(s.replace("ABC",""))) // 3

cnt = cnt_ABC(S)

for _ in range(Q):
    X, C = input().split()
    x = int(X)
    cnt -= cnt_ABC("".join(S_list[x-1:x+4]))
    S_list[x+1] = C
    cnt += cnt_ABC("".join(S_list[x-1:x+4]))
    print(cnt)

文字の置換を行った際にはその文字の影響範囲で部分文字列”ABC”の増減を調べれば十分ですね。
最初にS全体に部分文字列”ABC”が何個あるか調べておいて、その後は文字の置換をするたびにその前後2文字の範囲で部分文字列”ABC”の増減を調べています。
部分文字列のカウントにreplace()を使用していますがPythonならcount()がありました。
この問題では大丈夫ですが部分文字列が重複する可能性があり重複分もカウントしたい場合は正規表現のfindall()を使用する方法もあります。

コンテスト結果

D問題は解法が思いつかず時間切れでした。
今回B問題で時間がかかったのでパフォーマンスも振るわず…
最近精進を怠っていたのでそれが結果に出てしまっています。緑色目指して精進します。

おわりに

次回はABC373の記事を投稿します。
本ブログを通じて私と一緒に競技プログラミングの世界を楽しんでいただければ幸いです。
また、各種ご支援させていただきますので、お気軽に「お問い合わせフォーム」よりお問い合わせください。

お問い合わせ
業務実績

関連記事