atcoder ABC 104 D - We Love ABC

問題

解法

? があると複雑なため、まずは ? 抜きで考えてみる。素朴に3重ループでA->B->Cとなるパターンを総当りしてみる。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
using ll = long long;

int main() {
  string s; cin >> s;
  int n = s.size();

  ll ans = 0;
  REP(i,n) {
    for(int j=i+1; j<n; j++) {
      for(int k=j+1; k<n; k++) {
        ans += (s[i]=='A' && s[j]=='B' && s[k]=='C');
      }
    }
  }
  cout << ans << endl;
}

$O(N{^3})$ では制約に間に合わないためDPで考えてみる。

dp[n][4]; // [n文字までで][1: Aまで, 2: Bまで, 3: Cまでを満たす状態]

ll dp[100000][4];

int main() {
  string s; cin >> s;
  int n = s.size();

  dp[0][0] = 1;
  REP(i,n) {
    REP(j,4) dp[i+1][j] += dp[i][j]; // i+1の各状態にiの状態の数をそのまま足す

    if (s[i] == 'A') dp[i+1][1] += dp[i][0]; // Aにすすめる
    else if (s[i] == 'B') dp[i+1][2] += dp[i][1]; // Bにすすめる
    else if (s[i] == 'C') dp[i+1][3] += dp[i][2]; // Cにすすめる
  }

  cout << dp[n][3] << endl;
}

? の場合を考慮する。

// mint にする
mint dp[100000][4];

int main() {
  string s; cin >> s;
  int n = s.size();

  dp[0][0] = 1;
  REP(i,n) {
    REP(j,4) dp[i+1][j] += s[i]== '?' ? dp[i][j]*3 : dp[i][j]; // ?の場合は3文字ありえる

    if (s[i] == 'A') dp[i+1][1] += dp[i][0];
    else if (s[i] == 'B') dp[i+1][2] += dp[i][1];
    else if (s[i] == 'C') dp[i+1][3] += dp[i][2];
    else if (s[i] == '?') { // ? の場合はA, B, C それぞれ考慮する
      dp[i+1][1] += dp[i][0];
      dp[i+1][2] += dp[i][1];
      dp[i+1][3] += dp[i][2];
    }
  }

  cout << dp[n][3] << endl;
  return 0;
}

雑感

DPムズい