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

AtCoder Beginner Contest 207の解説記事です。私は2100点(91:09)31位でした。Dが銀河最難関で困り果てました。余裕持って解けなかったので解説の公開が遅れました。

A - Repression

思考

3つの整数から大きい2つの和を答える問題です。実装例ではsortしていますが、sumからminを引くなどの実装が、言語によってはかなり簡単にできます。

実装例

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

int main(){
    int a[3]={};
    for(int i{};i<(3);++i){
        cin >> a[i];
    }
    sort(a, a+3);
    cout << a[1] + a[2] << endl;
}

コンテスト中のACコード

B - Hydrate

思考

操作を行なった回数を $T$ 回とすると、水色のボールは $A+TB$ 個、赤色のボールは $TC$ 個となります。目標は $A+TB\leq TCD$ です。 $B\geq CD$ のときは, 明らかに達成できません。逆に $B\lt CD$ のときは、達成可能となり、そのような $T$ は
$A+TB\leq TCD\\ \Leftrightarrow T\geq \frac A{CD-B}\\ \Leftrightarrow T\geq\left\lceil\frac A{CD-B}\right\rceil$
となり、答えは $\left\lceil\frac A{CD-B}\right\rceil$ となります。

実装例

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

int main(){
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    if(b>=c*d){
        cout << -1 << endl;
    }
    else{
        cout << (a-1)/(c*d-b) + 1 << endl;
    }
}

コンテスト中のACコード

C - Many Segments

思考

ちゃんとやるだけなんですが、まともにやろうとすると破滅します。整数の区間だと思って、全て半開区間に帰着させてから解こうとしていたんですが、よく見ると実数の区間の話らしいので、これでは解けません。

ただlとrを2倍してみると、整数の区間だと思って解いても問題なくなるため、簡単に実装できます(偶数しか無くなって、端っこでバグらないためです。証明は各自でお願いします)。

実装例

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

int main(){
    int n;
    cin >> n;
    vector<int> l(n), r(n);
    for(int i{}, t;i<(n);++i){
        cin >> t >> l[i] >> r[i];
        l[i] *= 2, r[i] *= 2;
        if(t==1) ++r[i];
        else if(t==3) ++l[i], ++r[i];
        else if(t==4) ++l[i];
    }
    int ans{};
    for(int i{};i<(n);++i){
        for(int j{};j<(i);++j){
            if(!(r[i]<=l[j] or r[j]<=l[i])) ++ans;
        }
    }
    cout << ans << endl;
}

コンテスト中のACコード

D - Congruence Points

思考

かなり難しいです。

N=1の場合は自明にYesなので、以下Nは2以上とします。

平行移動と回転操作は、可換ではありませんが、回転させたあとに平行移動させるのと同じ動きを、平行移動させた後に回転させることでも達成できます。また平行移動同士、回転移動同士は1回にまとめることができます。

よって1回平行移動させてから1回回転させればいいことがわかります。

またTを平行移動させた集合にSを一致させられることと、SをTに一致させられることは同値です。

よってTは適当に平行移動して、重心は原点にあるとして良いです。

回転操作によって、重心と原点の距離は変わらないため、Sを1回平行移動させた時点で、Sの重心は原点にある必要があります。よってSを平行移動させて、原点に移動させれば、あとはSを回転させてTに一致させられるかを判定すれば良いです。

Sには原点でない点が含まれています。その点が、回転でTのどの点に一致するかを全探索すると、回転の角度の候補がたかだかN個求まります。この全ての角度についてSを回転させて、Tと一致するかを求めれば良いです。

整数だけでこれを処理するのは難しいので、小数に甘えて、誤差に気をつけて計算するといいです(std::complexとかを使うと楽です)。

実装例

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

int main(){
    int n;
    cin >> n;
    int A{}, B{}, C{}, D{};
    vector<int> a(n), b(n), c(n), d(n);
    for(int i{};i<(n);++i){
        cin >> a[i] >> b[i];
        A+=a[i], B+=b[i];
        a[i]*=n, b[i]*=n;
    }
    for(auto&i:a) i-=A;
    for(auto&i:b) i-=B;
    for(int i{};i<(n);++i){
        cin >> c[i] >> d[i];
        C+=c[i], D+=d[i];
        c[i]*=n, d[i]*=n;
    }
    for(auto&i:c) i-=C;
    for(auto&i:d) i-=D;
    if(n==1){
        cout << "Yes" << endl;
        return;
    }
    if(!a[0] and !b[0]){
        swap(a[0], a[1]);
        swap(b[0], b[1]);
    }
    map<pair<int,int>, bool> mp;
    for(int i{};i<(n);++i){
        mp[make_pair(c[i],d[i])] = true;
    }
    using com = complex<double>;
    vector<com> x(n);
    for(int i{};i<(n);++i){
        x[i]=com(a[i], b[i]);
    }
    constexpr double eps = 1e-9;
    for(int i{};i<(n);++i){
        if(a[0]*a[0]+b[0]*b[0]==c[i]*c[i]+d[i]*d[i]){
            com tmp(c[i], d[i]);
            tmp/=x[0];
            map<pair<int,int>, bool> mp2;
            bool fl = true;
            for(int j{};j<(n);++j){
                com y = x[j]*tmp;
                int X = lround(y.real()), Y = lround(y.imag());
                if(abs(y.real()-X)>eps or abs(y.imag()-Y)>eps){
                    fl = false;
                    break;
                }
                if(!mp[make_pair(X, Y)] or mp2[make_pair(X, Y)]){
                    fl = false;
                    break;
                }
                mp2[make_pair(X, Y)] = true;
            }
            if(fl){
                cout << "Yes" << endl;
                return;
            }
        }
    }
    cout << "No" << endl;
}

コンテスト中のACコード

E - Mod i

思考

$\mathrm{dp}_{i,j}=$ (数列の $i$ 番目までを $j$ 個に切り分ける通り数)

とすると、これは次のように $O(N^3)$ で計算できます。

$\mathrm{dp}_{i,j}=\mathrm{sum}\{\mathrm{dp}_{k,j-1}|1\leq k\lt i, \sum_{l=k+1}^{i}A_l$ が $j$ の倍数 $\}$

ただしこれだと間に合いません。ただ、 $\sum_{l=k+1}^{i}A_l$ が $j$ の倍数という条件が、 $A$ の累積和を $S$ として $S_k\equiv S_i \bmod{j}$ であることに気をつけると、 $S_k\equiv S_i \bmod{j}$ なる最も右の $k$ を $k$ とすると

$\mathrm{dp}_{i,j}=\mathrm{dp}_{k,j}+\mathrm{dp}_{k,j-1}$

のように計算できます。これで $O(N^2)$ で計算できました。

実装例

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

int main(){
    int n;
    cin >> n;
    vector<ll> a(n);
    for(auto&i:a) cin >> i;
    auto dp = vector(n+1, vector<modint1000000007>(n+1));
    auto b = vector(n+1, vector(n+1,-1));
    b[1][0] = 0;
    dp[0][0] = 1;
    ll s{};
    for(int i{};i<(n);++i){
        s+=a[i];
        for(int j{1};j<=n;++j){
            if(b[j][s%j]!=-1){
                dp[i+1][j] = dp[b[j][s%j]][j] + dp[b[j][s%j]][j-1];
            }
            b[j][s%j] = i+1;
        }
    }
    modint1000000007 ans;
    for(int j{1};j<=(n);++j){
        ans += dp[n][j];
    }
    cout << ans.val() << endl;
}

コンテスト中のACコード

F - Tree Patrolling

思考

高橋君が自分の頂点しか警備しない場合、これは標準的な二乗の木DPで、DFSしながら、各ノードの部分木で、警備された頂点がK個となる通り数を配列で持つことによって計算できます*1。

これを少し派生させて、各ノードについて、
「自身は警備されていない、部分木について警備された頂点がK個となる通り数」
「自身は警備されているが、高橋君はいない、部分木について警備された頂点がK個となる通り数」
「自身に高橋君がいる、部分木について警備された頂点がK個となる通り数」
を3つの配列で保持してやると、2乗の木DPで計算できます。

実装例

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

using mint = modint1000000007;
struct sq{
    vector<mint> a, b, c;
};

vector<mint> conv(const vector<mint>&a, const vector<mint>&x){
    vector<mint> na(a.size()+x.size()-1);
    for(int i{};i<(a.size());++i){
        for(int j{};j<(x.size());++j){
            na[i+j]+=a[i]*x[j];
        }
    }
    return na;
}

sq square(vector<vector<int>>&e,int i,int p){
    vector<mint> a={1}, b={1}, c={1};
    int ch{};
    for(auto j:e[i]) if(j!=p){
        ++ch;
        auto [A, B, C]=square<T>(e,j,i);
        vector<mint> x=A, y, z=A;
        if(x.size()<B.size()+1) x.resize(B.size()+1);
        for(int k{};k<(B.size());++k) x[k+1]+=B[k];
        y=x;
        if(y.size()<C.size()+1) y.resize(C.size()+1);
        for(int k{};k<(C.size());++k) y[k+1]+=C[k];
        z.resize(max({A.size(), B.size(), C.size()}));
        for(int k{};k<(B.size());++k) z[k]+=B[k];
        for(int k{};k<(C.size());++k) z[k]+=C[k];
        a = conv(a, x), b = conv(b, y), c = conv(c, z);
    }
    if(b.size()<a.size()) b.resize(a.size());
    for(int k{};k<(a.size());++k) b[k]-=a[k];
    c.resize(c.size()+ch);
    for(int k{c.size()};--k>=ch;) c[k]=c[k-ch];
    for(int k{};k<(ch);++k) c[k] = 0;
    return {a, b, c};
}

int main(){
    int n;
    cin >> n;
    auto e = vector(n, vector<int>());
    for(int i{}, u, v;i<(n-1);++i){
        cin >> u >> v;--u, --v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    auto [a,b,c] = square(e, 0, -1);
    a.resize(n+1);b.resize(n);c.resize(n);
    cout << 1 << '\n';
    for(int i{1};i<=n;++i){
        cout << (a[i]+b[i-1]+c[i-1]).val() << '\n';
    }
}