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

ここで宣言した通り、ABCの解説記事を書くことにしたので、練習がてら前回の解説記事を書くことにしました。サンプルとしてどうぞ。

A - Strings

思考

サンプルを見ると、二つの文字列を逆に連結するだけみたい。

実装例

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

int main(){
    string s,t;
    cin>>s>>t;
    cout<<t<<s<<endl;
}

コンテスト中のACコード

B - Greedy Takahashi

思考

高橋君の余るかどうかで場合分けをすれば良い。
条件分岐の不等号で、等号を含むかなどはこういう時はどうでもいい。
青木君のが足りなくなった場合も場合分けしてもいいけど、こっち(実装例)のが楽そう。

実装例

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

int main(){
    ll a,b,k;
    cin>>a>>b>>k;
    if(a>k) cout<<a-k<<" "<<b<<endl;
    else cout<<0<<" "<<max(0ll,b-(k-a))<<endl;
}

コンテスト中のACコード

C - Next Prime

思考

$X$ が小さいので、エラトステネスの篩で $2\cdot10^5$ くらいまで計算すれば、 $X$ 以上で最小なものが前から見ればわかる。

実装例

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

int main(){
    int n=200010;
    vector<bool> v(n);
    vector<int> p;
    for(int i=2;i<n;++i) v[i]=true;
    v[0]=v[1]=false;
    for(int i=2;i*i<n;++i) if(v[i]) for(int j=i*i;j<n;j+=i) v[j]=false;
    for(int i=2;i<n;++i) if(v[i]) p.emplace_back(i);
    int x;
    cin>>x;
    cout<<*lower_bound(p.begin(),p.end(),x)<<endl;
}

コンテスト中のACコード

D - Prediction and Restriction

思考

$K$ 回前と同じ手を出せないので、 $i$ 回目を考えるときに、 $i-K$ 回目に出した手がわかっていると嬉しい。 $i$ 回目にグー(/チョキ/パー)を出した時の最高点を持つようなDPをすれば良い。ここで $\mathrm{mod}\ K$ で一致しない回は無関係なので、0をグー、1をチョキ、2をパーとして
$dp_{i,j}=(i$ 回目に $j$ を出したとき、 $i,i-K,i-2K,...$ 回目で得られる最高点)
を簡単なDPで求めることができる。

実装例

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

int main(){
    int n,k,r,s,p;
    string t;
    cin>>n>>k>>r>>s>>p>>t;
    int mp[256]={};
    mp['r']=0;
    mp['s']=1;
    mp['p']=2;
    int x[3][3]={{0,r,0},{0,0,s},{p,0,0}};
    vector<vector<int>> dp(n,vector<int>(3));
    for(int i=0;i<n;++i) for(int j=0;j<3;++j){
        if(i<k) dp[i][j]=x[j][mp[t[i]]];
        else{
            for(int l=0;l<3;++l) if(l!=j){
                dp[i][j]=max(dp[i][j],dp[i-k][l]+x[j][mp[t[i]]]);
            }
        }
    }
    int ans=0;
    for(int i=0;i<k;++i) ans+=max({dp[n-1-i][0],dp[n-1-i][1],dp[n-1-i][2]});
    cout<<ans<<endl;
}

コンテスト中のACコード

E - Handshake

思考

全ての握手の組み合わせをパターンを列挙して、上から $M$ 個取るのが明らかに最適である。しかし、全ての握手の組み合わせは $N^2$ あるため、当然間に合わない。
もし得られる幸福度を固定して、それ以上の幸福度の握手が何通りあるかが分かれば、ある $X$ 以上の幸福度の握手がちょうど $M$ 個あるというような $X$ が求められる(正確には嘘で、後で訂正します)。
これは $O(NlogN)$ で求められます*1。あらかじめ $A$ をソートしておく。幸福度が高い手を固定すると、二分探索で相方の手となる下限を求めることができる。全ての手についてこれを考えると求められる。
これを実装するとサンプルが合わなくて？？？となる。よく考えると幸福度が同じ握手が複数ある場合もあるため、 $X$ 以上の幸福度の握手がちょうど $M$ 個あるというような $X$ が存在しない場合もある。よって $X$ 以上の幸福度の握手が $M$ 個以上あり、 $X$ より大きい幸福度の握手が $M$ 個未満であるような $X$ を求めると、超過分 $X$ を引くことで答えが求まる。

実装例

⚠️カス実装

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

int main(){
    ll n,m;
    cin>>n>>m;
    vector<ll> a(n),s(n+1);
    for(auto&i:a) cin>>i;
    sort(a.begin(),a.end());
    ll l=0,r=2e5+1,d;
    while(r-l>1){
        d=(r+l)>>1;
        ll c{};
        for(int i=0;i<n;++i){
            int j=a.begin()+i+1-upper_bound(a.begin(),a.begin()+i+1,d-a[i]);
            if(j) c+=2*j-1;
        }
        if(c>m) l=d;
        else r=d;
    }
    for(int i=0;i<n;++i) s[i+1]=a[i]+s[i];
    ll ans{},c{};
    for(int i=0;i<n;++i){
        int j=a.begin()+i+1-lower_bound(a.begin(),a.begin()+i+1,r-a[i]);
        if(j) c+=2*j-1;
        if(j) ans+=2*(s[i+1]-s[i+1-j])+a[i]*2*(j-1);
    }
    ans-=(c-m)*r;
    cout<<ans<<endl;
}

コンテスト中のACコード

F - Surrounded Nodes

思考

全塗り分けパターンが等確率で出現するので、結局穴あき度の合計を求めれば良い。
各頂点が穴と認識される回数を考えられれば、それの総和を求めれば良いので良い。穴となるのは、自身が白く、その頂点を根とした根つき木を考えたとき、子の部分木の内2つ以上に黒い頂点が存在することである。これは考え辛いので、穴とならないパターンを考えると、自身が黒いか、その頂点を根とした根つき木を考えたとき、子の部分木の内黒い頂点が存在するのは高々1つであるということである。
よってある頂点を根とした時の、子の部分木のサイズを求められれば良いこととなる。適当な頂点を根として(この木をTとする)、Tでの各頂点を根とする部分木のサイズを覚えておく。頂点Xを根とした時の、子の部分木は、Tでの子の部分木および、TでのXを頂点とした部分木を取り除いたものである。よってこのサイズは簡単に求まる。

実装例

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

struct modint{};//Z/MOD Z
modint pwr(int_fast64_t a,int_fast64_t b);//(a^b)%MOD

struct tree{
    size_t n,r;
    vector<vector<int>> e;
    vector<int> pa,d,sz;
    explicit tree(int n_){
        n=n_;
        e.resize(n);
    }
    void add(int a,int b){
        e[a].emplace_back(b);
        e[b].emplace_back(a);
    }
    void r_dfs(int i,int p=-1,int D=0){
        sz[i]=1;
        pa[i]=p;d[i]=D;++D;
        for(auto j:e[i]) if(j!=p){
                r_dfs(j,i,D);
                sz[i]+=sz[j];
            }
    }
    void r_i(int r_){
        pa.resize(n);d.resize(n);sz.resize(n);r=r_;
        r_dfs(r);
    }
    modint solve(int n,int i){
        modint c;
        for(auto j:e[i]) if(sz[i]>sz[j]){
                c+=pwr(2,sz[j])-1;
            }
        c+=pwr(2,n-sz[i]);
        return pwr(2,n-1)-c;
    }
};

int main(){
    int n,a,b;
    cin>>n;
    tree t(n);
    for(int i=0;i<n-1;++i){
        cin>>a>>b;
        t.add(--a,--b);
    }
    t.r_i(0);
    modint ans{};
    for(int i=0;i<n;++i) ans+=t.solve(n,i);
    ans/=pwr(2,n);
    cout<<ans<<endl;
}