ARC 086

arc086.contest.atcoder.jp

C - Not so Diverse

  • mapで各数字がいくつあるかカウント
  • 数字の個数を降順にソートして、大きい方から(K+1)番目以降の数字の和が答え
#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N, K;
    cin >> N >> K;
    map<int, int> A;
    REP(i, N) {
        int t;
        cin >> t;
        A[t]++;
    }
    vector<int> v;
    for(auto x : A) {
        v.push_back(x.second);
    }
    sort(v.rbegin(), v.rend());
    int ans = 0;
    for(int i=K; i<=v.size(); ++i) {
        ans += v[i];
    }
    cout << ans << endl;
}

Submission #1858429 - AtCoder Regular Contest 086 | AtCoder

D - Non-decreasing

  • 前から順に最大の正の数を足していくか、後ろから順に最小の負の数を足していけば非減少列が作れる
  • 最大値の絶対値と最小値の絶対値の大小関係によって取れる方針が決まることに注意する(max>0 かつ min>0なら前者、max>0 かつ min<0 かつ |max|<|min| なら後者……のように場合分けして考えると絶対値のみ比較すればよいことが分かる)
#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
    vector<int> a(N);
    REP(i, N) {
        cin >> a[i];
    }
    int Max = a[0];
    int Max_idx = 0;か
    int Min = a[0];
    int Min_idx = 0;
    FOR(i, 1, N) {
        if(a[i] > Max) {
            Max = a[i];
            Max_idx = i;
        }
        if(a[i] < Min) {
            Min = a[i];
            Min_idx = i;
        }
    }
    if(Max == Min) {
        cout << 0 << endl;
        return 0;
    }
    vector<pair<int, int>> ans;
    if(abs(Max) > abs(Min)) {
        for(int i=1; i<N; ++i) {
            a[i] += Max*2;
            ans.push_back({Max_idx+1, i+1});
            ans.push_back({Max_idx+1, i+1});
            Max = a[i];
            Max_idx = i;
        }
    } else {
        for(int i=N-2; i>=0; --i) {
            a[i] += Min*2;
            ans.push_back({Min_idx+1, i+1});
            ans.push_back({Min_idx+1, i+1});
            Min = a[i];
            Min_idx = i;
        }
    }
    cout << ans.size() << endl;
    for(auto x : ans) {
        cout << x.first << " " << x.second << endl;
    }
}

Submission #1861515 - AtCoder Regular Contest 086 | AtCoder

E - Smuggling Marbles (400点解法)

  • 根からの深さごとに木DPで数え上げる
  • 各頂点は「その頂点に来たときにビー玉が0個になるその頂点を根とする部分木のビー玉配置の場合の数」と「その頂点に来たときにビー玉が1個になるその頂点を根とする部分木のビー玉配置の場合の数」の2つの数(x, y)=(dp[v][0], dp[v][1])を持っている(ビー玉が0個になるとは、その頂点に来たときに2個以上になって取り上げられる場合を含む)
  • 根からの深さがdの頂点を(1, 1)で初期化する
  • 根からの深さがk (k < d)の頂点では、
    • xは深さk+1の子のどれか1つからビー玉が1個来て、残りの全ての子から0個来る場合の数
    • yは自分を頂点とする部分木の全ての置き方の場合の数からxを引いた場合の数
  • これを繰り返すとdp[0][1]が深さdの頂点のみに注目したとき、根までビー玉が来る場合の数になる。それ以外の頂点の置き方は自由なので、2を「深さd以外の頂点数」乗した数のビー玉が根まで到達する
  • 取りうる全てのdについて上のDPを行う

maze1230さんのコードを参考に解きました。

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

ll dp[2010][2];
ll nb_depth[2010];

vector<int> G[2010];
const ll MOD = 1e9+7;
 
void count_depth(int v, int depth){
    nb_depth[depth]++;
    REP(i, G[v].size()){
        count_depth(G[v][i], depth+1);
    }
}


ll mpow(ll a, ll b){
    if(b == 0) return 1;
    if(b < 0) return 0;
    if(b%2) return (a*mpow(a, b-1)) % MOD;
    ll ret = mpow(a, b/2);
    return (ret*ret)%MOD;
}

void dfs(int v, int d) {
    if(d == 0) {
        dp[v][0] = dp[v][1] = 1;
        return;
    }
    ll x = 1, y = 1;
    for(auto c: G[v]) {
        dfs(c, d-1);
        x = (x * dp[c][0]) % MOD;
        y = (y * (dp[c][0]+dp[c][1])) % MOD;
    }
    for(auto c: G[v]) {
        // n^{-1} mod p = n^{p-2} mod p
        dp[v][1] += ((x * mpow(dp[c][0], MOD-2)) % MOD * dp[c][1]) % MOD;
        dp[v][1] %= MOD;
    }
    dp[v][0] = (y - dp[v][1] + MOD) % MOD;
}


int main(void) {
    int N;
    cin >> N;
    if(N>2000) return 0;
    REP(i, N) {
        int p;
        cin >> p;
        G[p].push_back(i+1);
    (}
    count_depth(0, 0);
    ll ans = 0;
    REP(d, N+1) {
        REP(j, 2010) {
            REP(k, 2) {
                dp[j][k] = 0;
            }
        }
        dfs(0, d);
        ans = (ans + dp[0][1] * mpow(2, N-nb_depth[d]+1)) % MOD;
    }
    cout << ans << endl;
}

Submission #1883114 - AtCoder Regular Contest 086 | AtCoder

満点解法は解説が理解できないのでパス。