AtCoder ARC 059 F - バイナリハック / Unhappy Hacking (橙色, 800 点)

面白かった

問題へのリンク

問題概要

長さ の '0' と '1' と 'B' からなる文字列 として、以下の条件を満たすものが何通りあるか、1000000007 で割ったあまりを求めよ。

• 空文字列に対し、 を左から順に見て、以下の操作を順に行ってえられる文字列が に一致する
  • '0' ならば '0' を末尾に追加
  • '1' ならば '1' を末尾に追加
  • 'B' ならば末尾を削除 (空文字列の場合はなにもしない)

制約

• 
• 
• は '0' と '1' のみからなる

考えたこと

とても面白そう。ふと思ったのが、

---

として考えるべきは 'B' の位置だけではないか？

---

ということだった。なぜなら、 のうち、'B' の位置を決めると、

• できあがる文字列が何文字か？
• できあがる文字列の各文字が、 の中のどの index に対応するか？

が自動的に決まるのだ。もっというと、作りたい文字列 は文字数のみが重要であって、 の具体的な中身は関係ないのだ。 の文字数を とおこう。

B の位置を決めると

それでは 'B' の位置を決めたときに、何通りあるか？それは簡単で、

• のうち、'B' によって削除される箇所が 箇所であるとき、 通り

ということになる。'B' によって削除される箇所については '0' と '1' を好きなように選べるからだ。逆に 'B' によって削除されずに残る部分については、 と合わせる必要があるため、一意に決まることとなる。

DP へ

以上の考察に基づいて、以下の DP で回せるであろう。

• dp[ i ][ j ] := のうち最初の i 文字分について、'B' によって消されずに残る部分が j 個分であるような場合の数

こうしたとき、遷移は以下のようになる。

i 文字目に 'B' を追加するとき

j > 0 のとき、削除が行われるので

• dp[ i + 1 ][ j - 1 ] += dp[ i ][ j ] * 2;

j == 0 のときは、削除がおこわなれないので

• dp[ i + 1 ][ 0 ] += dp[ i ][ 0 ]

i 文字目が 'B' でないとき

• dp[ i + 1 ][ j + 1 ] += dp[ i ][ j ]

まとめ

の文字数のみが重要で、 のうちの 'B' の位置のみが重要という考察によって、シンプルな DP で解けることがわかる。計算量は 。

#include <iostream>
#include <vector>
using namespace std;


// modint: mod 計算を int を扱うように扱える構造体
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

// 二項係数ライブラリ
template<class T> struct BiCoef {
    vector<T> fact_, inv_, finv_;
    constexpr BiCoef() {}
    constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) noexcept {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        int MOD = fact_[0].getmod();
        for(int i = 2; i < n; i++){
            fact_[i] = fact_[i-1] * i;
            inv_[i] = -inv_[MOD%i] * (MOD/i);
            finv_[i] = finv_[i-1] * inv_[i];
        }
    }
    constexpr T com(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n-k];
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};

const int MOD = 1000000007;
using mint = Fp<MOD>;
BiCoef<mint> bc;

mint solve(int N, const string &S) {
    int K = (int)S.size();
    vector<vector<mint>> dp(N+2, vector<mint>(N+2, 0));
    dp[0][0] = 1;
    for (int i = 0; i <= N; ++i) {
        // from j
        dp[i+1][0] += dp[i][0]; // B
        dp[i+1][1] += dp[i][0]; // add

        for (int j = 1; j <= i; ++j) {
            dp[i+1][j-1] += dp[i][j] * 2;
            dp[i+1][j+1] += dp[i][j];
        }
    }
    return dp[N][K];
}

int main () {
    int N; string S;
    while (cin >> N >> S) cout << solve(N, S) << endl;
}
``At`