dwangoプログラミングコンテスト B – ニコニコ文字列をPython3で解く

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

出典：
dwangoプログラミングコンテスト B – ニコニコ文字列

真面目に実装していくと、意外と面倒くさい問題。

# dwangoプログラミングコンテスト B - ニコニコ文字列
# https://atcoder.jp/contests/dwango2015-prelims/tasks/dwango2015_prelims_2
# tag: 文字列 正規表現 繰り返し 連続部分列 数え上げ 考察

# "252525..." と N 回 "25" が繰り返されている文字列から、
# 何回部分文字列が取り出せるかを考えてみる。
# "25" は N 回取り出せ、"2525" は N-1 回取り出せ……と
# 順に考えていくと、1 ～ N までの合計回数取り出せることになる。

# あとは、"2525..." をどうやって抽出するのか、という話。

def main():
    S = input()+'0'

    # 2525の連続回数を保存しておくリスト
    seq = []

    # 2525を蓄えるバッファ
    buffer = ''

    for c in S:
        # バッファに文字を加える場合
        if c == '2' and not buffer.endswith('2'):
            buffer += '2'
        elif c == '5' and buffer.endswith('2'):
            buffer += '5'

        # バッファをクリアし、2525の数をseqに加える場合
        else:
            if len(buffer) >= 2:
                seq.append(len(buffer)//2)
            # この処理を忘れがち（個人的戒め）
            if c == '2':
                buffer = '2'
            else:
                buffer = ''

    # 後は連続回数に応じて計算する
    result = 0
    for n in seq:
        result += (n + 1) * n // 2
    
    print(result)

main()

dwango_2015_prelims_b.py view raw

もう少し楽をしたい場合、文字列置換や正規表現を利用して、いろいろとやり方がある。いろいろとやってみたが、実はPython3においては、string.replace()後、split()を利用する方法が、楽な割に最速に近かった。

関連

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