【競技プログラミング】AtCoder Beginner Contest 295_D問題

問題

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

各数字を2のべき乗に対応させ、累積XORを計算することで、部分文字列が嬉しい列かどうかを判定できる。
・任意の数Aに対して、A XOR A = 0となる性質
・0 XOR A = Aとなる性質
を活用する。

解法手順

1. 入力文字列Sを数字のリストに変換する。

2. 長さNを取得する。

3. defaultdictを使用して、XOR和の出現回数を記録する辞書Dを初期化する。

4. フラグ変数flagを0で初期化し、D[0]を1に設定する。

5. 文字列Sを先頭から順に走査し、以下の操作を行う：

   • 現在の数字nを整数に変換する。
   • flagをn番目のビットでXOR演算する（flag ^= 2**n）。
   • 新しいflagの値をDに記録する（出現回数を1増やす）。

6. 辞書Dの各値vに対して、v * (v-1) // 2 を計算し、その合計を答えとする。

7. 最終的な答えを出力する。

ACコード

ac.py

from collections import defaultdict

def solve(S):
    # 2. 長さNを取得する
    N = len(S)

    # 3. defaultdictを使用して、XOR和の出現回数を記録する辞書Dを初期化する
    D = defaultdict(int)

    # 4. フラグ変数flagを0で初期化し、D[0]を1に設定する
    flag = 0
    D[0] = 1

    # 5. 文字列Sを先頭から順に走査し、XOR和を計算する
    for n in S:
        # 現在の数字nを整数に変換する
        n = int(n)
        # flagをn番目のビットでXOR演算する
        flag ^= 2**n
        # 新しいflagの値をDに記録する（出現回数を1増やす）
        D[flag] += 1

    # 6. 辞書Dの各値vに対して、v * (v-1) // 2 を計算し、その合計を答えとする
    answer = 0
    for v in D.values():
        answer += v * (v - 1) // 2

    # 7. 最終的な答えを出力する
    print(answer)

if __name__=="__main__":
    # 1. 入力文字列Sを受け取る
    S = input().strip()
    solve(S)

おまけ(パターン箇所の表示)

問題では、組数しか問われていないけど、パターン発生箇所とパターン文字列も摘出しておきたい。
動的計画法とか、仕事で使うことはたまにある(というより、競プロで身につけたスキルだから使う場面を狙ってる)けど、結果より復元の方が大事なことが多いんですよね。

ac.py

from collections import defaultdict

def solve(S):
    # 2. 長さNを取得する
    N = len(S)

    # 3. defaultdictを使用して、XOR和の出現回数を記録する辞書Dを初期化する
    D = defaultdict(int)

    # 4. フラグ変数flagを0で初期化し、D[0]を1に設定する
    flag = 0
    D[0] = 1

    # ※ XOR和の値とその位置を記録する辞書
    positions = defaultdict(list)  
    positions[0].append(-1)  # 初期位置を-1とする
    patterns = []  # パターンの開始位置と終了位置を記録するリスト

    # 5. 文字列Sを先頭から順に走査し、XOR和を計算する
    # ※ 復元のためにindexを追加
    for i, n in enumerate(S):
        # 現在の数字nを整数に変換する
        n = int(n)
        # flagをn番目のビットでXOR演算する
        flag ^= 2**n
        
        # パターンの開始位置と終了位置を記録
        if flag in positions:
            for start in positions[flag]:
                patterns.append((start + 1, i))  
        positions[flag].append(i)
        
        # 新しいflagの値をDに記録する（出現回数を1増やす）
        D[flag] += 1

    answer = sum(v * (v - 1) // 2 for v in D.values())
    print(f"繰り返しパターンの総数: {answer}")

    print("繰り返しパターンの位置:")
    for start, end in patterns:
        print(f"開始位置: {start}, 終了位置: {end}, パターン: {S[start:end+1]}")

if __name__=="__main__":
    S = input().strip()
    solve(S)