ABC295 D問題 Three Days Ago

atcoder.jp

嬉しい列になる条件

嬉しい列は、「並び替えによって同じ列を2度繰り返すようにできるもの」です。
同じものが2度あらわれることから、列の中の各数字は偶数個になります。
逆に各数字の個数がすべて偶数であれば「並び替えによって同じ列を2度繰り返すようにできる」。
そのため、嬉しい列であることと列の中の各数字の個数が偶数個であることは同値です。

文字目から 文字目までの部分文字列が嬉しい列かどうかを調べたいので、
部分文字列に含まれる各文字の個数を素早く知りたいです。
そのためには、累積和の考え方( 1文字目から 文字目までに含まれる個数を とすると、 文字目から 文字目までに含まれる個数は、 と求められる)　を使います。

偶数か奇数かの表現に ビット配列を利用

各数字の個数が偶数か奇数かを区別すればよいので、ビット配列を利用してみます。
数字は 0 から 9 までの 10 個なので、10桁のビット配列で 10個の数字の数の偶奇を表現できます。
偶数を 0、奇数を 1 で表すことにします。
文字目から 文字目までの部分文字列が嬉しい列になるのは、
つまり の場合です。

求めたいのは、 となる整数の組 の数です。
それには、同じ値の が何個あるか数えて、そこから2個選ぶ場合の数 を加算していくことで求められます。

コード例 (Julia)

function solve()

  # 文字列入力
  S = readline()

  # 文字列の長さ
  N = length(S)

  # 各ビットが偶数回か奇数回かを表す
  B = 0

  # ビット状態が同じものが何個あるか記録するための辞書型データ
  D = Dict()

  # 初期状態を登録
  push!(D, B=>1)

  for i = 1:N
    #  i 文字目が k なら ビット配列の k 番目を反転する
    n = S[i] - '0' + 1
    m = (1 << n)
    B = xor(B, m)
    #  この状態を登録
    if haskey(D,B)
      D[B] += 1
    else
      push!(D, B=>1)
    end
  end

  #  ビット状態が同じペアの組み合わせの数が求める答え
  ans = 0
  for k in keys(D)
    n = D[k]
    ans += (n*(n-1))÷2
  end

  println(ans)

end  # function solve

# main
solve()