ABC163 解説 - Motsu_xe 競プロのhogeやfuga

今回割と難しかったっと思うんですが、めちゃくちゃすんなり考察できて、なんか最強になってました。結果は44:00 4位!!。ところでunratedになったらから、人々がTwitterに戻ったという説もあるし、単純に鯖が崩壊してて遅い人もいるかもで、4位は額面通りではなさそう。でも私も3分くらい問題見れなかったし、まあ感覚的にも成功なので、まあ喜んでいいんじゃないかな。

コンテストページ

A - Circle Pond

思考

周長は半径に比例するので、サンプル1の答えに半径をかければ良いです。

実装例

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

int main(){
    double r;
    cin>>r;
    cout<<setprecision(20)<<r*6.28318530717958623200<<endl;
}

コンテスト中のACコード

B - Homework

思考

宿題をやる日以外全部遊べばいいです。宿題だけで夏休みが

実装例

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

int main(){
    int n,m,a;
    ll s{};
    cin>>n>>m;
    for(int i{};i<m;++i){
        cin>>a;
        s+=a;
    }
    cout<<max(n-s,-1)<<'\n';
}

コンテスト中のACコード

C - management

思考

A_iでの出現回数が、部下の数です。

実装例

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

int main(){
    int n,x;
    cin>>n;
    vector<int> c(n);
    for(int i{1};i<n;++i){
        cin>>x;
        --x;
        c[x]++;
    }
    for(auto&i:c) cout<<i<<'\n';

コンテスト中のACコード

D - Sum of Large Numbers

思考

ベースの数が大きすぎて、足す個数が異なれば、必ず和は異なります。そんでもって、足す個数をLとすると $0+..+(L-1)=\frac{L(L-1)}{2}$ から $(N-L+1)+..+N=\frac{L(2n+1-L)}{2}$ の間の数は全て作れます*1。よってK<=L<=N+1について、 $\frac{L(2n+1-L)}{2}-\frac{L(L-1)}{2}+1$ を足し合わせればいいです*2。

実装例

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

struct modint{}; //いつもの

int main(){
    int n,k;
    cin>>n>>k;
    modint ans;
    for(int j=k;j<=n+1;++j){
        ans+=modint(j)*(2*n+1-j)/2-modint(j)*(j-1)/2+1;
    }
    cout<<ans<<endl;
}

コンテスト中のACコード

E - Active Infants

思考

原則として、でかい方から貪欲に一番遠いところに置くのが良いです。貪欲に詰めてないやつが最適だとすると、でかい方から置いていって、一番遠くじゃないところに置いた初めてのやつを、一番遠いところとswapすると、悪くはならないことからわかります。ですが、遠いところは2通りある場合があり、両方試してると、最悪 $O(2^N)$ みたいななります*3。なので、条件を緩和すると、左右の余ってるどっちかの端に置くと言うことは言えています。なのでdp_i,jを「大きい方からi+j個を左からi個, 右からj個詰めたときの最大のうれしさ」と定義すると、簡単にDPが回って $O(N^2)$ で解けて、うれしさが最大になります。

実装例

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 inline bool chmax(ll&x,ll y);
ll dp[2001][2001]={};

int main(){
    int n;
    cin>>n;
    vector<pair<ll,int>> a(n);
    fr(i,n){
        cin>>a[i].first;
        a[i].second=i;
    }
    sort(a.rbegin(),a.rend());
    ll ans{};
    for(int i{};I<=n;++i) for(int j{};i+j<=n;++j){
        if(i==0&&j==0) continue;
        if(i) chmax(dp[i][j],dp[i-1][j]+a[i+j-1].first*abs(a[i+j-1].second-i+1));
        if(j) chmax(dp[i][j],dp[i][j-1]+a[i+j-1].first*(n-j-a[i+j-1].second));
        if(i+j==n) chmax(ans,dp[i][j]);
    }
    cout<<ans<<'\n';
}

コンテスト中のACコード

F - path pass i

思考

単純パス全体の数は、 $\frac{N(N+1)}{2}$ で簡単にわかるので、色kが塗られている頂点を通らない単純パスの数を求めれば良い。これは色kが塗られている頂点を除いたときの連結成分上のパス全体が該当する。よって各連結成分の要素数がわかれば良い。ただ、各色ごとに愚直にそれを計算すると、 $O(N^2)$ になってしまい、普通に間に合いません。
よって、木DPしながらなんやかんやしたいなぁとなる。適当に根付き木にして、DFSをしていくことを考える。例えばある色kの頂点を根とする部分木に、根以外の頂点が色kで塗られていないとする。このとき、子の部分木は考えたい連結成分になっている。この時は、子のサイズをもってきて、なんやかんやすればいい。
もし根以外にも頂点が色kで塗られていたとすると、その部分木は連結成分から除いておきたい。これを達成するにはDFS中に、部分木の色kの除くべき連結成分の合計個数を常に覚えておけば良い。
これ以上は説明が難しいので、あとはコードを読んで理解してください(は？)。

実装例

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

struct tree{
    size_t n,r,md;
    vector<vector<int>> e;
    vector<int> c,sz;
    vector<ll> ans,C;
    explicit tree(int n):n(n),e(n),c(n),C(n),ans(n, ll(n)*(n+1)/2){}
    void built(){
        static int a,b;
        for(auto&i:c) cin>>i,--i;
        for(int i{1};i<n;++i){
            cin>>a>>b;
            --a,--b;
            e[a].emplace_back(b);
            e[b].emplace_back(a);
        }
    }
    void dfs(int i=0,int p=-1){
        ll tmp = C[c[i]];
        for(auto j:e[i]) if(j!=p){
            C[c[i]]=0;
            dfs(j,i);
            sz[i]+=sz[j];
            ans[c[i]]-=(sz[j]-C[c[i]])*(sz[j]-C[c[i]]+1)/2;
        }
        C[c[i]] = tmp+sz[i];
    }
    void solve(){
        sz.assign(n,1);
        dfs();
        for(int i{};i<n;++i) cout<<ans[i]-(n-C[i])*(n-C[i]+1)/2<<'\n';
    }
};

int main(){
    int n;
    cin>>n;
    tree t(n);
    t.built();
    t.solve();
}