ABC104 D - We Love ABC

解説ではDPが想定解。また他の記事にBを固定してA,C をカウントする方法もあったが、累積和を使っても比較的きれいにかける(実際には累積和しか浮かばなかった)。

解法

まず、Sの中からA, B, Cを選ぶときにたとえばAならAを選ぶ場合と?をAに変えてそれを選ぶ場合の2通りある。そのため3つの文字にどちらの方法で選ぶのか固定しChar(A)などと置く。 累積和SUM_C[i]をChar(C)がSのi番目以降で現れる個数とする。また、SUM_Bを部分列(Char(B), Char(C))がSのi番目以降で現れる個数、SUM_Aを部分列(Char(A), Char(B), Char(C))がSのi番目以降で現れる個数としておく。 すると、Char(-)を固定した場合には SUM_A[0] * 3使われていない'?'の個数 が答えになる。 あとはChar(-)を変えた8バターンを足し合わせればよい。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    string S;
    cin >> S;


    ll N = S.size();
    vll res;
    rep(useQ, 0, 8) {
        vll Q(S.size() + 1);
        vll C(S.size() + 1);
        vll B(S.size() + 1);
        vll A(S.size() + 1);
        rrep(i, 0, N) {
            Q[i] = Q[i + 1] + (S[i] == '?' ? 1 : 0);
        }
        rrep(i, 0, N) {
            if (at_bit(useQ, 0)) {
                C[i] = (C[i + 1] + (S[i] == '?' ? 1 : 0)) % MOD;

            }
            else {
                C[i] = (C[i + 1] + (S[i] == 'C' ? 1 : 0)) % MOD;

            }

        }
        rrep(i, 0, N) {
            if (at_bit(useQ, 1)) {
                B[i] = (B[i + 1] +(S[i] == '?' ? C[i + 1] : 0)) % MOD;

            }
            else {
                B[i] = (B[i + 1] + (S[i] == 'B' ? C[i + 1] : 0)) % MOD;

            }

        }
        rrep(i, 0, N) {
            if (at_bit(useQ, 2)) {
                A[i] = (A[i + 1] +( S[i] == '?' ? B[i + 1] : 0)) % MOD;


            }
            else {
                A[i] = (A[i + 1] + (S[i] == 'A' ? B[i + 1] : 0)) % MOD;


            }
        }
        ll cntQ = Q[0] - (at_bit(useQ, 0) + at_bit(useQ, 1) + at_bit(useQ, 2));

        if (cntQ >= 0) {
            res.push_back((A[0] * POW_3(3LL, cntQ)) % MOD);

        }
    }

    ll out = 0;
    for (ll i : res)
        out = (out + i) % MOD;

    cout << out % MOD << endl;

    return 0;
}

深さ優先探索

ABC015-C-高橋くんのバグ探し

再帰を使った解答

#include "bits/stdc++.h"

using namespace std;
//debug

#define rep(i, N, M) for (ll i = N; i < M; ++i)
#define rrep(i, N, M) for (ll i = N; i < M; --i)
#define pb push_back


typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<string> vs;
typedef priority_queue<ll> pqll;
typedef priority_queue<pll, vector<pll>> pqpll;
typedef priority_queue<ll, vll, greater<ll>> pqll_greater;
typedef priority_queue<pll, vector<pll>, greater<pll>> pqpll_greater;


#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define vec(a) vector<a>
#define _CRT_SECURE_NO_WARNINGS

template<class T, class S>
T atbit(T n, S i) {
    return (n >> i) % i;
}

template<class T>
T getbit(T i) {
    return 1LL << i;
}

//#define TRANSFORM(v,w,func) decltype(v) w ; transform((v).begin(),(v).end(),back_inserter(w),func);

using namespace std;


ll N,K;
vvll T(N, vll(K));
bool dfs(ll n, ll t) {
    bool flg = true;
    rep(i, 0, K*N) {
        if (n ==-1) {
            flg &= t != 0;
        }
        else {
            flg &= dfs(n - 1, t ^ (T[n][i]));

        }
    }
    return flg;
}
int main() {
    cin >> N >> K;
    rep(i, 0, N) {
        rep(j, 0, K) {
            cin>>T[i][j];
        }
    }


    bool flg = true;
    rep(i, 0, N) {
        rep(j, 0, K) {
            
        }
    }

    if (dfs(N - 1, 0)) {
        cout<<"Nothing";
    }
    else {
        cout << "Found";
    }
}

for文による解答

#include "bits/stdc++.h"

using namespace std;
//debug

#define rep(i, N, M) for (ll i = N; i < M; ++i)
#define rrep(i, N, M) for (ll i = N; i < M; --i)
#define pb push_back


typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<string> vs;
typedef priority_queue<ll> pqll;
typedef priority_queue<pll, vector<pll>> pqpll;
typedef priority_queue<ll, vll, greater<ll>> pqll_greater;
typedef priority_queue<pll, vector<pll>, greater<pll>> pqpll_greater;


#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define vec(a) vector<a>
#define _CRT_SECURE_NO_WARNINGS

template<class T, class S>
T atbit(T n, S i) {
    return (n >> i) % i;
}

template<class T>
T getbit(T i) {
    return 1LL << i;
}
template<class T>
T POW(T n, T m) {
    T res=1;
    rep(i, 0, m) {
        res *= n;
    }
    return res;
}

using namespace std;


ll N, K;
vvll T;

int main() {
    cin >> N >> K;
    vvll T(N, vll(K));
    rep(i, 0, N) {
        rep(j, 0, K) {
            cin>>T[i][j];
        }
    }

    
    bool flg = true;
    rep(i, 0, POW(K,N)) {
        ll t = 0;
        rep(n, 0, N) {
            t^=(T[n][(i/POW(K,n))%K]);
        }
        flg =flg && t; // &= とは省略できない。(bit演算と解釈されてしまうため。flg&=bool(t)と書くことは可能)。
    }
    
    

    if (flg) {
        cout<<"Nothing";
    }
    else {
        cout << "Found";
    }
}