提出 #62301407

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;

void add(int &x, int y) {
    x += y;
    if (x >= mod)  x -= mod;
}
int mul(int x, int y) {
    return (long long) x * y % mod;
}

int n;
string s;
vector<int> pos[26];

vector<int> add_to_state(vector<int> s, int x) {
   for (int i = n - 1; i >= 0; --i) {
       int last = -1;
       if (i) last = min(n, s[i - 1] + 1);
       s[i] = min(s[i], *lower_bound(pos[x].begin(), pos[x].end(), last));
   }
   return s;
}

int main() {
    int n; cin >> n;
    string s; cin >> s;
    
    int N = 1;
    for (int i = 0; i < n; ++i) N *= 3;
    
    vector<int> ppl;
    vector<int> dp(N, 1);
    for (int i = 0; i < N; ++i) ppl.push_back(s[i] - '0');
    while (N != 1) {
        vector<int> npl;
        vector<int> ndp;
        for (int i = 0; i < N; i += 3) {
            npl.push_back((ppl[i] + ppl[i + 1] + ppl[i + 2]) / 2);
            vector<int> bads;
            for (int j = 0; j < 3; ++j) if (ppl[i + j] == npl.back()) bads.push_back(dp[i + j]);
            sort(bads.begin(), bads.end());
            if (bads.size() == 3) ndp.push_back(bads[0] + bads[1]);
            else ndp.push_back(bads[0]);
        }
        N /= 3;
        dp = ndp;
        ppl = npl;
    }
    cout << dp[0] << endl;
}

提出情報

ジャッジ結果