Atcoder 灰diff埋め AGC025~AGC054 振り返り

AGCも全て埋め終わって100%!と思いきやまだ-like系の問題が多く残ってました……

AGC037 A - Dividing a String【AC】

　解説ではDPを使うパターンと漸化式を使うパターンが紹介されていましたが，ここではそのどちらでもない方法で解きます．（と言っても考え方は漸化式のパータンとほぼ同じですが）
　S1S2...Skに文字列を分割し，Kの最大値を求めます．ここでSiの長さが3以上になることはありません．なぜなら，len(Si)=1ならlen(Si+1)=2の文字列を用意すれば必ずSi=Si+1とはならず，len(Si)=2ならばlen(Si+1)=1の文字列を用意すれば必ずSi=Si+1とはならないからです．分割数Kを大きくしたいのでlen(Si)は小さければ小さい方が良く，len(Si)>=3となるようなSiは考える必要がありません．
　Sのi文字目をsiとします．si != si+1ならば，そのままSi, Si+1とするのが最適です．si = si+1ならば，Siの長さに合わせてSi+1を決定します．len(Si)=1ならば，si+1とsi+2を合わせてSi+1とします．これは長さが異なるので必ずSi != Si+1となります．同様にlen(Si)=2ならsi+1をSi+1とします．
　以上の処理をSの末尾まで続ければ分割数の最大値Kが求まります．

S = list(input())
lis = [S[-1]]
S.pop()
while S:
    if S[-1] == lis[-1]:
        if len(S) == 1:
            lis[-1] += S.pop()
        else:
            s = S.pop()
            s += S.pop()
            lis.append(s)
    else:
        lis.append(S.pop())
print(len(lis))