Codeforces Round #678 (Div. 2)

codeforces.com

A. Reorder

総和がと一致していればいい
提出コード

void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    if(accumulate(a.begin(), a.end(), 0) == m) cout << "YES" << endl;
    else cout << "NO" << endl;
}

B. Prime Square

x111
1x11
11x1
111x

のように対角成分にが素数かつが素数以外であるようなを全探索すればいい
提出コード

void solve(){
    int n;
    cin >> n;
    sieve(MAX_N);
    int p = 0;
    for(int i=1;i<=101010;i++){
        if(is_prime[n-1+i] and !is_prime[i]){
            p = i;
            break;
        }
    }
    vector<vector<int>> a(n, vector<int>(n, 1));
    REP(i,n) a[i][i] = p;
    REP(i,n){
        REP(j,n) cout << a[i][j] << " ";
        cout << endl;
    }
}

C. Binary Search

問題文中のコードをシミュレートすると、xより小さい数（l_cnt）とxより大きな数（r_cnt）のそれぞれ使われる個数がわかる
また、それ以外の部分では大小関係なく使うことができるので全体として
が答え
提出コード

void solve(){
    int n, x, pos;
    cin >> n >> x >> pos;

    bc.init(2020);
    int l = 0, r = n;
    int l_cnt = 0, r_cnt = 0;
    while(l < r){
        int m = (r + l) >> 1;
        if(m == pos) l = m + 1;
        else if(m > pos) r = m, r_cnt++;
        else l = m + 1, l_cnt++;
    }

    mint ans = bc.perm(x-1, l_cnt) * bc.perm(n-x, r_cnt) * bc.fact(n-1-l_cnt-r_cnt);
    cout << ans << endl;
}

D. Bandit in a City

各頂点における部分木に注目する
頂点の部分木の葉の数とその部分木に含まれる頂点の総和をとすると、その部分木における問題の答えは
よって各頂点ごとにこの値を求め、そのmaxが答え
提出コード

void solve(){
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    REP(i,n-1){
        int p;
        cin >> p;
        g[p-1].emplace_back(i+1);
    }
    vector<ll> a(n);
    REP(i,n) cin >> a[i];
    vector<ll> leaves(n);
    vector<ll> sum(n);
    auto dfs = [&](auto && self, int cur, int par) -> pair<ll, ll>{
        int l_cnt = 0;
        ll a_sum = a[cur];
        if(g[cur].size() == 0) l_cnt = 1;
        for(auto nv : g[cur]){
            if(nv == par) continue;
            auto [l, s] = self(self, nv, cur);
            l_cnt += l;
            a_sum += s;
        }
        leaves[cur] = l_cnt;
        sum[cur] = a_sum;
        return make_pair(leaves[cur], sum[cur]);
    };
    dfs(dfs, 0, -1);
    ll ans = 0;
    REP(i,n){
        chmax(ans, (sum[i] + leaves[i] - 1) / leaves[i]);
    }
    cout << ans << endl;
}