AtCoder Grand Contest 034 B – ABC をPython3で解く

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典：
AtCoder Grand Contest 034 B – ABC

文字列を操作しやすいように事前に変えておけば、解くのがぐんと楽になる問題。

# AtCoder Grand Contest 034 B - ABC
# https://atcoder.jp/contests/agc034/tasks/agc034_b
# tag: 文字列 置換 最大値 事前操作 正規表現

# 'ABC' を 'BCA' に書き換えるとき、'BC' の並びは変更されない。
# そこで、とりあえず 'BC' を 'D' と書き換えてから考える。

# 文字列全体は、'B' もしくは 'C' によって分割された、
# 'A' 'D' の組み合わせによる文字列と考えられる。
# 'A'と'D'は交換可能だが、'B' 'C' の壁を越えることは出来ない。
# 例えば入力例3 だと、
# ADA C C B ADDAAD B
# となり、この ADA と ADDAAD を考慮することになる。

# それぞれの塊を、DD..DAA..A という状態になるまで
# 操作すれば、それが最大の回数となる。

import re
def main():
    S = input()
    S = S.replace('BC', 'D')

    # 正規表現を用いて AD のグループを探す
    groups = re.findall(r'[AD]+', S)

    result = 0

    for g in groups:
        # 'D' を順番に数えつつ探し、左端に持っていくための
        # 操作回数を足していく。
        cnt_a = 0

        # 具体的には、そこまでに現れた "A" の個数だけ
        # "D" を左に移動することが出来る。
        for idx, c in enumerate(g, start=1):
            if c == 'A':
                cnt_a += 1
            elif c == 'D':
                result += cnt_a

    print(result)

main()

agc034_b.py view raw

関連

コメントを残すコメントをキャンセル