面白かった！
問題概要
3 つの文字 B, Y, K からなる長さ の文字列
が与えられる。
この文字列をいくつかの区間に分割する。各区間について、
- ランレングス圧縮すると、B -> Y -> K の順になるもの：区間の長さだけスコアを獲得
- ランレングス圧縮すると、K -> Y -> B の順になるもの：区間の長さだけスコアを獲得
- それ以外：スコア獲得なし
区間分割の仕方を最適化したときに、得られるスコアの総和の最大値を求めよ。
制約
考えたこと
仮に の計算量を費やしてもよいならば、いつもの「区間の分割の仕方を走査していく DP」で解ける。それがうまくいかない場合には、耳DPで解けることがよくある。今回は、次のような DP で上手くいった。
dp[i][0]：の先頭から
文字目までを考えて、その終端で一旦区間を区切る場合の、スコアの最大値
dp[i][j = "B", "BY", "BYK", "K", "KY", "KYB"]：になる場合についての、スコアの最大値
なお、わかりやすい図が公式解説にあった。
遷移をちゃんと詰めると AC となった。計算量は と評価できる。
コード
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); } template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); } using pint = pair<int, int>; using pll = pair<long long, long long>; using tint = array<int, 3>; using tll = array<long long, 3>; using vll = vector<long long>; using ll = long long; using u32 = unsigned int; using u64 = unsigned long long; using int128 = __int128; using u128 = unsigned __int128; template <class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>; #define REP(i, a) for (long long i = 0; i < (long long)(a); i++) #define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++) #define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i) #define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i) #define EB emplace_back #define PB push_back #define MP make_pair #define MT make_tuple #define FI first #define SE second #define ALL(x) x.begin(), x.end() #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl // debug stream template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) { return s << '<' << P.first << ", " << P.second << '>'; } template<class T> ostream& operator << (ostream &s, vector<T> P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template<class T> ostream& operator << (ostream &s, deque<T> P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template<class T> ostream& operator << (ostream &s, vector<vector<T> > P) { for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; } template<class T> ostream& operator << (ostream &s, set<T> P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template<class T> ostream& operator << (ostream &s, multiset<T> P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) { for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; } int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); const int NON = 0; const int B = 1; const int BY = 2; const int BYK = 3; const int K = 4; const int KY = 5; const int KYB = 6; int N; string S; cin >> N >> S; N = (int)S.size(); const int INF = 1<<29; vector dp(N+1, vector(7, -INF)); dp[0][0] = 0; REP(i, N) { chmax(dp[i+1][NON], dp[i][NON]); if (S[i] == 'B') { chmax(dp[i+1][B], dp[i][NON] + 1); chmax(dp[i+1][B], dp[i][B] + 1); chmax(dp[i+1][KYB], dp[i][KY] + 1); chmax(dp[i+1][KYB], dp[i][KYB] + 1); } else if (S[i] == 'K') { chmax(dp[i+1][K], dp[i][NON] + 1); chmax(dp[i+1][K], dp[i][K] + 1); chmax(dp[i+1][BYK], dp[i][BY] + 1); chmax(dp[i+1][BYK], dp[i][BYK] + 1); } else { chmax(dp[i+1][KY], dp[i][K] + 1); chmax(dp[i+1][KY], dp[i][KY] + 1); chmax(dp[i+1][BY], dp[i][B] + 1); chmax(dp[i+1][BY], dp[i][BY] + 1); } chmax(dp[i+1][NON], dp[i+1][KYB]); chmax(dp[i+1][NON], dp[i+1][BYK]); } cout << dp[N][NON] << endl; }
