結果

問題 No.3114 0→1
ユーザー k1suxu
提出日時 2025-04-19 18:45:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 5,538 bytes
コンパイル時間 3,505 ms
コンパイル使用メモリ 283,716 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-19 18:45:45
合計ジャッジ時間 5,051 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘std::vector<std::vector<long long int> > Random::tree_generator_using_prufer_code()’:
main.cpp:92:61: warning: no return statement in function returning non-void [-Wreturn-type]
   92 |     vector<vector<int>> tree_generator_using_prufer_code() {}
      |                                                             ^

ソースコード

diff # 

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

using std::cin;
using std::cout;

#define rep(i,n) for(int i = 0; i < (int)n; i++)
#define FOR(n) for(int i = 0; i < (int)n; i++)
#define repi(i,a,b) for(int i = (int)a; i < (int)b; i++)
#define all(x) x.begin(),x.end()
//#define mp make_pair
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vvvvi vector<vvvi>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>

template<typename T>
bool chmax(T &a, const T b) {if(a<b) {a=b; return true;} else {return false;}}
template<typename T>
bool chmin(T &a, const T b) {if(a>b) {a=b; return true;} else {return false;}}

using ll = long long;
using ld = long double;
using ull = unsigned long long;

const ll INF = numeric_limits<long long>::max() / 2;
const ld pi = 3.1415926535897932384626433832795028;
const ll mod = 998244353;
int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};

#define int long long

struct Random {
private:
    struct UnionFind {
        vector<int> r;
        
        UnionFind(int n) {
            r = vector<int>(n, -1);
        }

        int root(int x) {
            if(r[x] < 0) return x;
            return r[x] = root(r[x]);
        }

        bool unite(int x, int y) {
            x = root(x);
            y = root(y);
            if(x == y) return false;
            if(r[x] > r[y]) swap(x, y);
            r[x] += r[y];
            r[y] = x;
            return true;
        }

        bool issame(int x, int y) {
            return root(x) == root(y);
        }
    };

public:
    mt19937_64 rng;
    Random() {
        random_device rnd;
        srand((int)time(0));
        rng = mt19937_64(rnd() * rand());
    }

    vector<vector<int>> tree_generator_using_UF(const int n, const int indexed=0) {
        UnionFind UF(n+indexed);
        vector<vector<int>> g(n+indexed);
        int edge_count = 0;

        while(edge_count < n-1) {
            int u = rng()%n+indexed;
            int v = rng()%n+indexed;

            if(!UF.issame(u, v)) {
                g[u].push_back(v);
                g[v].push_back(u);
                UF.unite(u, v);
                ++edge_count;
            }
        }
        return g;
    }

    vector<vector<int>> tree_generator_using_prufer_code() {}

    // return random non-negative integer in [l, r)
    int get_int(int l, int r) {
        return rng()%(r-l)+l;
    }

    // return random array consisting of non-negatove integer in [l, r)
    vector<int> get_array(const int len, const int l, const int r) {
        vector<int> x;
        for(int i = 0; i < len; ++i) {
            x.push_back(get_int(l, r));
        }
        return x;
    }

    // not debugged (might contain some bugs)
    vector<int> get_permutation(const int len, int start_val = 0) {
        vector<int> x(len);
        iota(all(x), start_val);
        shuffle(x.begin(), x.end(), rng);
        return x;
    }

    string get_string(const int len, bool lower, bool upper, bool number) {
        vector<char> char_set;
        if(lower) for(int i = 0; i < 26; i++) char_set.push_back((char)('a' + i));
        if(upper) for(int i = 0; i < 26; i++) char_set.push_back((char)('A' + i));
        if(number) for(int i = 0; i < 9; i++) char_set.push_back((char)('0' + i));
        return get_string(len, char_set);
    }

    string get_string(const int len, vector<char> char_set) {
        string s;
        for(int i = 0; i < len; i++) s.push_back(char_set[get_int(0, (int)char_set.size())]);
        return s;
    }

    void my_sleep(const int millisec) {
        std::this_thread::sleep_for(std::chrono::milliseconds(millisec));
    }
} rd;

int solve(int n, string s) {
    int ans = 0;
    repi(i, 1, n) {
        if (i >= 2 && s[i-2] == '0' && s[i-1] == '1' && s[i] == '0') {
            ans += (s[i] == '0');
            s[i] = '1';
        }

        if (s[i-1] == '0' && s[i] == '0') {
            ans += (s[i] == '0');
            s[i] = '1';
            if (i < n-1) {
                ans += (s[i+1] == '0');
                s[i+1] = '1';
            }
        }
    }

    // rep(i, n) repi(j, i+2, n+1) {
    //     string t = s.substr(i, j-i);
    //     int one = (int)count(all(t), '1');
    //     if (one * 2 < (int)t.size()) {
    //         cout << i << " " << j << endl;
    //         assert(false);
    //     }
    // }

    return ans;
}

int naive(int n, string s) {
    vi ids;
    FOR(n) if (s[i] == '0') ids.emplace_back(i);
    const int sz = (int)ids.size();
    int ans = INF;
    rep(mask, 1<<sz) {
        string t = s;
        rep(i, sz) if (mask >> i & 1) {
            t[ids[i]] = '1';
        }
        
        bool valid = true;
        rep(i, n) repi(j, i+2, n+1) {
            string x = t.substr(i, j-i);
            int one = (int)count(all(x), '1');
            if (one * 2 < (int)x.size()) {
                valid = false;
            }
        }
        if (valid) chmin(ans, (int)__builtin_popcount(mask));
    }
    return ans;
}

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

    // while (true) {
    //     int n = rd.get_int(1, 10);
    //     string s = rd.get_string(n, vector<char>{'0', '1'});
    //     cout << n << " " << s << endl;
        
    //     int nai = naive(n, s);
    //     int sol = solve(n, s);

    //     if (nai != sol) {
    //         cerr << nai << " vs " << sol << endl;
    //         return 0;
    //     }
    // }

    int n;
    string s;
    cin >> n >> s;
    cout << solve(n, s) << endl;
    return 0;
}
0