【AtCoder】ABC 418 D - XNOR Operation | 緑コーダーが解くAtCoder

atcoder.jp

配点: 425 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 821 / NoviSteps: 1Q

問題概要
制約
考察
- 「美しい文字列」となるための条件の言い換え
- 「美しい文字列」の数え上げ
実装例
コメント

問題概要

0, 1からなる空でない文字列 $S$ が次の条件を満たすとき、 $S$ を「美しい文字列」と呼ぶ。

次の一連の操作をの長さがになるまで行い、に残った唯一の文字を1にすることができる。
1. $1 \leq i \leq |S| - 1$ を満たす整数 $i$ を自由に選ぶ。
2. 整数を次のように定義する。
  - $S_i =$ 0かつ $S_{i+1}=$ 0である場合、 $x = 1$ とする。
  - $S_i =$ 0かつ $S_{i+1}=$ 1である場合、 $x = 0$ とする。
  - $S_i =$ 1かつ $S_{i+1}=$ 0である場合、 $x = 0$ とする。
  - $S_i =$ 1かつ $S_{i+1}=$ 1である場合、 $x = 1$ とする。
3. $S_i$ と $S_{i+1}$ を取り除き、それらがあった場所に $x$ を数字とみなしたものを $1$ 個挿入する。

0, 1からなる長さ $N$ の文字列 $T$ が与えられるので、 $T$ の連続部分文字列である美しい文字列の個数を求めよ。ただし、2つの連続部分文字列が文字列として同じでも、取り出す位置が異なるならば別々に数える。

制約

$1 \leq N \leq 2 \times 10^5$
$N$ は整数

考察

「美しい文字列」となるための条件の言い換え

最後の状態である1を頂点として、操作を逆から辿るような木構造を考えることもできるが、1文字から2通りの遷移が考えられるため、状態数は $1 \rightarrow 2 \rightarrow 8 \rightarrow \dots$ と爆発的に増えていってしまう。

このような状態遷移を伴うような操作に関わる問題は、操作の前後で変化しない「不変量」に注目することが有効な場合が多い。

最終的に0を消したいので、0の個数に注目すると、

00 $\rightarrow$ 1 : 2個減少
01 $\rightarrow$ 0 : 変わらない
10 $\rightarrow$ 0 : 変わらない
11 $\rightarrow$ 1 : 変わらない

となるから、この問題の不変量は「0の個数の偶奇」ということになる。

美しい文字列は、最終的に0の個数が偶数である1となる文字列のことだから、 $T$ の空でない連続部分文字列 $t$ について、

$t$ が美しい文字列 $\iff$ $t$ に含まれる0の個数が偶数

という同値関係が成り立つ。

したがって、0の個数が偶数となるような $t$ を数え上げればよい。

「美しい文字列」の数え上げ

$T$ の長さは最大 $2 \times 10^5$ となるので、B問題のように全ての連続部分文字列を愚直に試すことはできない。

そこで、以下のような2次元 DP テーブルを考える。なお、 $T$ の $i$ 文字目から $j$ 文字目までの連続部分文字列を $T[i, j$ ] と表す $(0 \leq i \lt j \lt N)$ 。

$\mathrm{dp}_{j, 0} :=$ $T[i, j] \: (i = 0, 1, \dots, j)$ (末尾が $T$ の $j$ 文字目である連続部分文字列) のうち、0を偶数個含むものの個数。
$\mathrm{dp}_{j, 1} :=$ $T[i, j] \: (i = 0, 1, \dots, j)$ のうち、0を奇数個含むものの個数。

なお、初期値は全て $0$ である。

遷移は、末尾が $T$ の $j+1$ 文字目である連続部分文字列は

長さ $j$ の連続部分文字列 $T[0, j]$ の末尾に $T_{j+1}$ を追加したもの
$T_{j+1}$ のみからなる長さ $1$ の文字列

の2種類からなることを踏まえると、以下のように書くことができる。

$\mathrm{dp}_{j+1, 0} = \left\{ \begin{array}{ll} \mathrm{dp}_{j, 1} & (T_{j+1} = 0) \\ \mathrm{dp}_{j, 0} + 1 & (T_{j+1} = 1) \end{array} \right. \\ \mathrm{dp}_{j+1, 1} = \left\{ \begin{array}{ll} \mathrm{dp}_{j, 0} + 1 & (T_{j+1} = 0) \\ \mathrm{dp}_{j, 1}& (T_{j+1} = 1) \end{array} \right.$

答えは、 $\displaystyle \sum_{j=0}^{N} \mathrm{dp}_{j, 0}$ で計算することができる。

計算量は $O(N)$ となるので、本問の制約下では十分高速。

実装時は答えのオーバーフローに注意すること。

実装例

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

using ll = long long;

// ======================================== //

int main()
{
    int N;
    string T;
    cin >> N >> T;

    vector<vector<int>> dp(N + 1, vector<int>(2, 0));
    rep(j, 0, N)
    {
        if (T[j] == '0')
        {
            dp[j + 1][0] = dp[j][1];
            dp[j + 1][1] = dp[j][0] + 1;
        }
        else
        {
            dp[j + 1][0] = dp[j][0] + 1;
            dp[j + 1][1] = dp[j][1];
        }
    }

    ll ans = 0;
    rep(j, 0, N + 1)
    {
        ans += dp[j][0];
    }

    cout << ans << endl;

    return 0;
}