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"; } }