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

AtCoder Beginner Contest 206（Sponsored by Panasonic）の解説記事です。私は2100点(61:20)78位でした。

A - Maxi-Buying

思考

消費税の計算、もっと一般に有限小数、もっと一般に有理数の掛け算は、安易にdoubleなどの浮動小数点数を用いると、誤差でバグりやすいため、 $\mathbb{floor}(108N/100)$ などのように実装すると安全です。
まあ正直少数使っても通るとは思います。?:の三項演算子を用いても良いですが, 条件式3つあると頭が壊れるので、安全にif文で書いています。

実装例

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

int main(){
    int n;
    cin >> n;
    n*=108;
    n/=100;
    if(n>206)
        puts(":(");
    else if(n==206)
        puts("so-so");
    else
        puts("Yay!");
}

コンテスト中のACコード

B - Savings

思考

1からMまでの整数の和は $M(M+1)/2$ であることが知られていますから、2分探索などで境界を求めても良いですが、冷静になると $O(\sqrt{N})$ 日程度しかかからないため、愚直にシミュレーションしても十分高速です。

実装例

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

int main(){
    int n;
    cin >> n;
    for(int i{1};;++i){
        n-=i;
        if(n<=0){
            cout << i << endl;
            return;
        }
    }
}

コンテスト中のACコード

C - Swappable

思考

Aが相異なるi, jを探すのは難しいですが, Aが同じi, jを探すのは容易です。よって全体からこれを引くことを考えます。 $A_i=A_j=C$ となる(i, j)の組の総数は、 $A_i=C$ なるiの個数を $n$ として $n(n-1)/2$ となることを利用して、登場する全てのCについてこれを考えれば良いです。これはstd::mapなどを用いて容易に実現可能です。
オーバーフローには気をつけましょう。

実装例

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

int main(){
    ll n;
    cin >> n;
    map<int,ll> mp;
    for(int i{},a;i<(n);++i){
        cin >> a;
        mp[a]++;
    }
    ll ans = n*(n-1)/2;
    for(auto&[a,b]:mp){
        ans-=b*(b-1)/2;
    }
    cout << ans << endl;
}

コンテスト中のACコード

D - KAIBUNsyo

思考

$A_i$ と $A_{N+1-i}$ は同じ色にする必要があります。ここで登場する色を頂点とし、 $A_i$ と $A_{N+1-i}$ を結ぶ辺を追加した、無向グラフを考えます。この連結成分にある色は最終的に同じ色になっている必要があり、逆に同じ連結成分にない色は同じにする必要があります。よって各連結成分を同じ色にするコストを考えればよく、これは(連結成分のサイズ)-1です。よってatcoder::dsuなどを用いて、これを計算すれば良いです。*1

実装例

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto&i:a) cin >> i, --i;
    dsu d(200000);
    for(int i{};;++i){
        if(i>=n-1-i) break;
        d.merge(a[i], a[n-1-i]);
    }
    cout << 200000 - d.groups().size() << endl;
}

コンテスト中のACコード

E - Divide Both

思考

求めたい集合は

$\{(x,y);L\leq x, y\leq R, g=\gcd(x,y), g\neq1, x\neq g, y\neq g\}\\ =\bigsqcup_{g=2}^{R}\{(x,y);L\leq x, y\leq R, \gcd(x,y)=g, x\neq g, y\neq g\}\\ =\bigsqcup_{g=2}^{R}\{(gX,gY);L\leq gX, gY\leq R, \gcd(X,Y)=1, X\gt1, Y\gt1\}\\ =\bigsqcup_{g=2}^{R}\{(X,Y);\max(2, \lceil L/g\rceil)\leq X, Y\leq \lfloor R/g\rfloor , \gcd(X,Y)=1\}$

となり、D以上U以下の互いに素な2以上の自然数の組の数を求める問題に帰着できました。これを $O(U)$ で解くことができれば、調和級数から $O(R\log R)$ で解けて、十分高速です。

実際にこれは前計算 $O(R\log R)$ の下で、 $O(U)$ で計算することができます。あるdに対して、両方dの倍数の組の数を求めるのは容易です。これから、包除原理を用いて、足し引きすることで、求めることができます。このとき、足し引きする際の係数は前計算 $O(R\log R)$ 計算できます*2。

実装例

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

int main(){
    int l, r;
    cin >> l >> r;
    vector<ll> k(r+1, 1);
    for(int i{2};i<=(r);++i){
        for(int j{2*i};j<=r;j+=i){
            k[j] -= k[i];
        }
    }
    ll ans{};
    for(int g{2}; g<=r; ++g){
        ll d = max(1, (l-1)/g), u = r/g;
        ans += (u-d)*(u-d);
        for(int j{2}; j<=u; ++j){
            ans -= k[j] * (u/j-d/j)*(u/j-d/j);
        }
    }
    cout << ans << endl;
}

コンテスト中のACコード

F - Interval Game 2

思考

この手のゲームでは、とりあえずGrundy数を計算できるかどうかを考えることが有効です。

このゲームは、半開区間を頂点に、共通部分がある区間に辺を貼ったグラフで、1つの頂点を取り除いたら、辺で直接繋がっている頂点も取り除かれるとして、操作できなくなった人が負けというゲームになっています。一般のN頂点グラフについて考えると、これはGrundy数を計算するのに、残っている頂点の集合とかを考えないといけなそうで、多項式時間で解くのはかなり困難に見えます*3。

そこで区間であることを利用して、残っている辺の集合がいい感じになるのではないかと予想します。すると、ある区間を取り除くと、その左側、その右側の区間に分離し、それぞれは完全に独立したゲームになることがわかります。独立したゲーム*4のGrundy数は、それぞれのGrundy数のxorになることが知られているため、ある区間に含まれる区間についてのGrundy数を、区間が狭い順に計算してやれば良いことがわかります。*5

Grundy数を計算しているところですが、今回は時間に余裕があるのでlogつけていますが、線形でもできます。

実装例

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

int main(){
    int n;
    cin >> n;
    vector<int> L(n), R(n);
    for(int i{};i<(n);++i){
        cin >> L[i] >> R[i];
    }
    auto G = vector(101, vector(101, 0u));
    for(int len{1};len<=(100);++len){
        for(int l{};l<=(100-len);++l){
            int r = l + len;
            vector<int> tmp;
            for(int i{};i<(n);++i){
                if(l<=L[i] and R[i]<=r) tmp.push_back(i);
            }
            set<unsigned> st;
            for(int i:tmp){
                st.insert(G[l][L[i]]^G[R[i]][r]);
            }
            unsigned nw{};
            for(unsigned u:st){
                if(nw < u){
                    break;
                }
                else{
                    ++nw;
                }
            }
            G[l][r] = nw;
        }
    }
    puts(G[0][100]?"Alice":"Bob");
}