AtCoder Beginner Contest 163（ABC163） - 接着剤の精進日記

unratedになっちゃったね、悲しい
Dが普通にわからなかったのでもっと悲しい…

A - Circle Pond

$2 \pi R$ を出力すればいい
$10^{-2}$ 以下は許容されるから $\pi = 3.14$ とかでも大丈夫そう（多分）
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    double R;
    cin >> R;
    printf("%.12lf\n", 2 * R * PI);
}

B - Homework

$N \lt sum$ なら $-1$
そうでないなら $N - sum$
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    ll sum = 0;
    vector<int> A(M);
    REP(i,M){
        cin >> A[i];
        sum += A[i];
    }
    if(sum > N) cout << -1 << endl;
    else cout << N - sum << endl;
}

C - management

一瞬Cで部分木のサイズ求めさせるの？と誤読した
ちゃんと問題を見ると出てきたものをカウントしてあげればいい
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> cnt(N+1);
    REP(i,N-1){
        int a;
        cin >> a;
        cnt[a]++;
    }
    for(int i=1;i<=N;i++) cout << cnt[i] << endl;
}

D - Sum of Large Numbers

これ難しくないですか？全然わからなかった
まず、i個取ったときのことを考える
この時、小さい順にi個取って出来る最小値と、大きい順に取った最大値を作る
そうするとその[最小値, 最大値]の区間の数字は全て作ることが出来る
これ、非自明だと思うんだけどAtCoderの民強い…
終わった後に思い出したんだけど同じような考え方の過去問が次のやつ
こういう発想全然出来ないなあ
atcoder.jp

提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    vector<ll> left(N+1), right(N+1);
    REP(i, N+1){
        left[i] = i;
        right[i] = N - i;
        if(i > 0) left[i] += left[i-1], right[i] += right[i-1];
    }
    ll ans = 0;
    for(int i=K;i<=N+1;i++){
        ans += right[i-1] - left[i-1] + 1;
        ans %= MOD;
    }
    cout << ans << endl;
}

E - Active Infants

これも難しい
制約的に $\mathcal{O}(N^2)$ が出来る
基本的には大きい方から決めていけば良さそうだけど貪欲だと死ぬなあと考えていた
実際その通りで、大きい順から左右に割り振っていったときの状態を持ちながらDPすればいい
ここまでわかってもコードに起こすの中々しんどいのでDP特訓が必要…
提出コード

ll dp[2020][2020];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<pair<ll, ll>> A(N);
    REP(i,N){
        cin >> A[i].first;
        A[i].second = i + 1;
    }
    sort(A.rbegin(), A.rend());
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    REP(i,N){
        for(int l=0;l<=i;l++){
            int r = (i - l);
            if(l + 1 <= N && ~dp[l][r]) chmax(dp[l+1][r], dp[l][r] + A[i].first * abs(A[i].second - l - 1));
            if(r + 1 <= N && ~dp[l][r]) chmax(dp[l][r+1], dp[l][r] + A[i].first * abs(A[i].second - (N - r)));
        }
    }
    ll ans = 0;
    REP(i,N+1) chmax(ans, dp[i][N-i]);
    cout << ans << endl;
}