ABC391E

問題

ABC391E

解法

min を求める問題なので，余分に計算する分には正しく求まる．
実行制限時間に間に合うのなら，実装を簡単にする方が良い．
0, 1 の取り方は $2^3$ 通りある．本来は全ては試さなくても最適解は求まるが，
全て求める方が実装は楽．

再帰的な実装になるが，for や while のループで代用可能．

コード

main.cpp

int main() {
  ll n; cin >> n;
  string s; cin >> s;
  
  const ll inf = 1e18;
  vvll dp(s.size(), vll(2, inf)); // dp[v][i] := (vertex v の値を i in 2 にするためのコスト)
  rep(i,s.size()) {
    dp[i][s[i]-'0'] = 0;
    dp[i][(s[i]-'0')^1] = 1;
  }

  while(dp.size() > 1){
    vvll old(dp.size()/3, vll(2, inf));
    swap(old,dp);
    
    for(ll l = 0; l < old.size(); l += 3){
      rep(msk, 8){
        ll cost = 0; rep(i,3) cost += old[l+i][msk >> i & 1];

        ll x = __builtin_popcountll(msk)>=2 ? 1 : 0;
        chmin(dp[l/3][x], cost);
      }

    }
  }

  cout << max(dp[0][0], dp[0][1]) << endl;
  assert(min(dp[0][0], dp[0][1]) == 0);

  return 0;
}