JOI2013本選1 電飾

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2013ho/tasks/joi2013ho1
https://www.ioi-jp.org/joi/2012/2013-ho/index.html

ポイント

• 逐次的に交互列を探す。これはO(N)で求まる。
• 三つの交互列が並んでいる時、中央の交互列を反転させることで全体として一つの交互列となる。

コード

N = int(input())
A = map(int, input().split())

old = ''
cnt = 0
left = []
for a in A:
    if a==old:
        left.append(cnt)
        cnt = 1
    else:
        cnt += 1
    old = a
left.append(cnt)
left+=[0,0] # 要素数が3以上になることを保証

ans = 0
for i in range(len(left)-2):
    ans = max(ans, sum(left[i:i+3]))
print (ans)

記事情報

• 投稿日：2020年5月9日
• 最終更新日：2020年5月9日