Submission #62295125

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    string A;
    cin >> N >> A;
    // 長さは3^N
    int L = 1;
    for (int i = 0; i < N; i++) L *= 3;
    // シミュレーションで元の最終多数決結果を得る
    vector<int> cur(L);
    for (int i = 0; i < L; i++){
        cur[i] = A[i]-'0';
    }
    int tempL = L;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

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

    int N;
    string A;
    cin >> N >> A;
    // 長さは3^N
    int L = 1;
    for (int i = 0; i < N; i++) L *= 3;

    // シミュレーションで元の最終多数決結果を得る
    vector<int> cur(L);
    for (int i = 0; i < L; i++){
        cur[i] = A[i]-'0';
    }
    int tempL = L;
    for (int lvl = 0; lvl < N; lvl++){
        int newL = tempL/3;
        vector<int> nxt(newL,0);
        for (int i = 0; i < newL; i++){
            int sum = cur[3*i] + cur[3*i+1] + cur[3*i+2];
            nxt[i] = (sum >= 2 ? 1 : 0);
        }
        cur = nxt;
        tempL = newL;
    }
    int f = cur[0];  // 元の最終結果
    int target = 1 - f;

    // dp[level][i][bit] : 最小反転数（葉レベルが0, 以降は内部ノード） 
    // レベル0: 各リーフについて
    vector<array<int,2>> dp(L);
    for (int i = 0; i < L; i++){
        int bit = A[i] - '0';
        dp[i][0] = (bit==0?0:1);
        dp[i][1] = (bit==1?0:1);
    }
    
    // 下からあげてdpを計算（各レベル毎にグループ3つ）
    int curSize = L;
    for (int lvl = 1; lvl <= N; lvl++){
        int newSize = curSize / 3;
        vector<array<int,2>> newdp(newSize);
        for (int i = 0; i < newSize; i++){
            // 各グループについて 子は dp[3*i], dp[3*i+1], dp[3*i+2]
            for (int b = 0; b < 2; b++){
                int base = 0;
                vector<int> diffs;
                for (int k = 0; k < 3; k++){
                    int cost_b = dp[3*i+k][b];
                    int cost_other = min(dp[3*i+k][b], dp[3*i+k][1-b]);
                    base += cost_other;
                    diffs.push_back(cost_b - cost_other);
                }
                sort(diffs.begin(), diffs.end());
                int cnt_zero = 0;
                for (int d : diffs) {
                    if(d==0) cnt_zero++;
                }
                int extra = 0;
                if(cnt_zero >= 2){
                    extra = 0;
                } else if(cnt_zero == 1){
                    // 1個が既に b としているため，あと1個必要
                    // diffs[0]は0，次に小さい正の値を選ぶ
                    extra = diffs[cnt_zero];
                } else { // cnt_zero==0
                    extra = diffs[0] + diffs[1];
                }
                newdp[i][b] = base + extra;
            }
        }
        dp = move(newdp);
        curSize = newSize;
    }
    
    cout << dp[0][target] << "\n";
    return 0;
}

Submission Info

Judge Result