ABC418Dを解いた【DP】

筆者はレート800前後の茶～緑コーダ

ABC418当日にACできなかったD問題を解いていく

実装コード

操作による0の個数は偶数奇数変化しない点を利用して動的計画法すればいいらしい

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    N = rI()
    S = rS()
    
    dp = [0,0]
    
    ans = 0
    for s in S:
        ndp = [0,0]
        if s == "0":
            ndp[0] = dp[1]
            ndp[1] = dp[0] + 1
        else:
            ndp[0] = dp[0] + 1
            ndp[1] = dp[1]
        ans += ndp[0]
        dp = ndp
    print(ans)
    
if __name__ == '__main__':
    main()

まとめ

コンステスト中に落ち着いて問題文読めなかったが、
おちついた今読んでもよくわからない。

結局解説見るまでDPを使うことなんて思いつかなかった。

(おまけ)GPT5にコメントしてもらった

開く

いいね、そのDPはちゃんと正答出るやつ。
要点だけズバッとまとめるね。

• この演算は隣接 2 文字の XNOR（同じなら1、違えば0）。これを畳み込み続けた最終ビットは0 の個数が偶数なら 1になる（演算が結合的なので順序に依らない）。ゆえに「美しい文字列＝0 が偶数個の部分文字列」。([AtCoder][1])
• だから数え上げは「各 prefix までの 0 の偶奇」を管理して、同じ偶奇の組み合わせ数を足せば OK（偶奇別の個数から C(n,2)）。この発想は解説・ブログでも触れられてる。([AtCoder][1], [Codeforces][2])

あなたの実装は「各位置で偶数/奇数の部分文字列本数をDPで更新→偶数分を加算」という形で、きっちり要件を満たしてる。サンプルも一致するはず。

もう少しだけスッキリ版（O(1) メモリ／一発集計）も置いとく：

# prefix 偶奇カウント解
import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rS(): return sys.stdin.readline().rstrip()

N = rI()
T = rS()

cnt = [1, 0]   # prefix の偶数/奇数の個数（空文字の偶数=1を含める）
par = 0        # ここまでの 0 の偶奇
for ch in T:
    if ch == '0':
        par ^= 1
    cnt[par] += 1

ans = cnt[0]*(cnt[0]-1)//2 + cnt[1]*(cnt[1]-1)//2
print(ans)

DP派なら、あなたのコードで十分。競プロ的には上の prefix 法が短くて速い、ってくらいの差だね。

「“きれい”の正体は“0の偶奇”。わかった瞬間、世界が急に単純になるやつ。」