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

2100 67:34 178位でした。酒が入っているので注意力が若干落ちていますが、ここ3週間飲酒ABCで全完できてるので、まあ大した問題ではない(ペナは増えがち)。言語が変わって、しょっぱなCE出しました、カス。

A - Lucky 7

思考

ここ数日LINE BOT作るのにPython使ってたので、文字列に7が含まれているかをさくっと書いて終了です。三項演算子に自信がなかった。

実装例

if  "7" in input():
  print("Yes")
else:
  print("No")

コンテスト中のACコード

B - FizzBuzz Sum

思考

実際にN個試しても間に合います。やるだけです。

実装例

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

int main(){
    int n;
    cin>>n;
    ll s{};
    Fr(i,n) if(i%3&&i%5) s+=i;
    cout<<s<<endl;
}

コンテスト中のACコード

C - Sum of gcd of Tuples (Easy)

思考

やるだけです。せっかくなのでC++17の新機能std::gcdを使いましょう。添字はちゃんと考えようね*1。

実装例

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

int main(){
    int k;
    cin>>k;
    ll s{};
    for(int i{1};i<=k;++i) for(int i{1};i<=k;++i) for(int i{1};i<=k;++i) s+=gcd(gcd(i,j),l);
    cout<<s<<endl;
}

コンテスト中のACコード

D - RGB Triplets

思考

ややっこいので、余事象を考えましょう。R,G,Bの数をそれぞれ把握しておけば、2つ一致、1つ一致、3つ異なるがj-i=k-jとかは簡単にわかります(それぞれO(1), O(1), O(N^2)です)。

実装例

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

int main(){
    ll n;
    string s;
    in>>n>>s;
    ll ans=n*(n-1)*(n-2)/6;
    int c[256]={};
    fr(i,n) c[s[i]]++;
    ll r=c['R'],g=c['G'],b=c['B'];
    ans-=r*(r-1)/2*(n-r);
    ans-=g*(g-1)/2*(n-g);
    ans-=b*(b-1)/2*(n-b);
    ans-=r*(r-1)*(r-2)/6;
    ans-=g*(g-1)*(g-2)/6;
    ans-=b*(b-1)*(b-2)/6;
    fr(i,n) fr(j,i){
        int k=i+(i-j);
        if(k<n&&s[i]!=s[j]&&s[j]!=s[k]&&s[i]!=s[k]) --ans;
    }
    cout<<ans<<endl;
}

コンテスト中のACコード

E - Sum of gcd of Tuples (Hard)

思考

N=3の場合がEasyですね。EasyとHardの割にはぱっと見の見た目が異なってあれです。k=gcd(A_1,..,A_N)となるような{A_i}の数がわかれば良いのですが、ちょっと難しいです。ここでk|gcd(A_1,..,A_N)となるような{A_i}の数を考えます。これ自体は簡単で、A_iが全てkの倍数ならいいので $floor(K/k)^N$ です。これをB_kとする。
ここで{C_k}={1,1,2,2,4,2,6,4,..}を $\sum_{l|k}C_l=k$ となるような数列とすると、 $\sum_{k=1}^{K}B_k*C_k$ が答えとなります*2。
後は{C_k}をどのように定めるかですが、C_k=kと初期化した後に、k=1,..,Kの順番に、 $C_{lk}-=C_k (l=2,3,..)$ としてやればいいです。これは調和級数を考えて $O(KlogK)$ で終了します。典型なので何度かやればできるようになります。

実装例

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

struct modint;
modint pwr(int,int);

int main(){
    int n,k;
    cin>>n>>k;
    modint ans;
    vector<modint> c(k+1);
    iota(c.begin(),c.end(),modint(0));
    for(int i{1};i<=k;++i){
        ans+=c[i]*pwr(k/i,n);
        for(int j=i*2;j<=k;j+=i) c[j]-=c[i];
    }
    cout<<ans<<endl;
}

コンテスト中のACコード

F - Select Half

思考

100回誤読して、終了していた。基本的には1個飛ばしで取っていかないと $floor\left(\frac{N}{2}\right)$ 個など取れません。
dp_i,j=(i個目を取って、j個余分に飛ばした中の最大値)
とかにしてDPするとOKです*3。なんかnが偶数の時に累積和っぽくやってたらREが出たのでnが偶数の時も耳DPで解いてました。
ところで実装がカスすぎる。

実装例

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

struct modint; //いつもの

int main(){
    int n;
    cin>>n;
    vector<ll> a(n);
    for(auto&i:a) cin>>i;
    if(n&1){
        if(n==3) return cout<<max({a[0],a[1],a[2]})<<endl,0;
        auto c=vector(3,vector(n,-(1ll<<60)));
        c[0][0]=a[0];
        c[1][1]=a[1];
        c[0][2]=a[0]+a[2];
        c[2][2]=a[2];
        c[1][3]=max(a[0]+a[3],a[1]+a[3]);
        for(int i=4;i<n;++i){
            chmax(c[0][i],c[0][i-2]+a[i]);
            chmax(c[1][i],max(c[1][i-2]+a[i],c[0][i-3]+a[i]));
            chmax(c[2][i],max({c[2][i-2],c[1][i-3],c[0][i-4]})+a[i]);
        }
        cout<<max({c[2][n-1],c[1][n-2],c[0][n-3]})<<endl;
    }
    else{
        if(n==2) return cout<<max({a[0],a[1]})<<endl,0;
        auto c=vector(2,vector(n,-(1ll<<60)));
        c[0][0]=a[0];
        c[1][1]=a[1];
        c[0][2]=a[0]+a[2];
        for(int i=3;i<n;++i){
            chmax(c[0][i],c[0][i-2]+a[i]);
            chmax(c[1][i],max(c[1][i-2],c[0][i-3])+a[i]);
        }
        cout<<max({c[1][n-1],c[0][n-2]})<<endl;
    }
}