Motsu_xe 競プロのhogeやfuga

Motsu_xeが競技プログラミングに関する何かを適当に書き連ねるブログになるはずです。

ABC158 解説

お久しぶりです。参加できなかったり全完できなかったりで、なかなかかけませんでした、ごめんなさい。結果は95:42 121位でした。ちょっとEFでグダリ過ぎましたね。

コンテストページ

A - Station and Bus

思考

最初pythonのノリでsetで1,2種類で判別しようかと思いましたが、よく考えたら、1種類なのは"AAA","BBB"の2種類しかないので、それを見ると早いですね。

実装例

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

int main(){
    string s;
    cin>>s;
    if(s=="AAA"||s=="BBB") puts("No");
    else puts("Yes");
}

コンテスト中のACコード

B - Count Balls

思考

A+B個周期なので、A+Bで割った商だけ周期を考えて、あまりをなんやかんやすればいいです。コードを見たほうが早い。

実装例

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

int main(){
    long long n,a,b;
    cin>>n>>a>>b;
    cout<<n/(a+b)*a+min(n%(a+b),a)<<endl;
}

コンテスト中のACコード

C - Tax Increase

思考

1秒だけ算数を頑張りたい気持ちになりますが、A,Bがとんでもなく小さいので、税抜き価格を総当たりすれば良いです。税金問題はちょいちょい出ますが*108/100みたいな書き方をすると誤差を気にしなくてよくていい感じです。総当たりの範囲はだいぶ大きめに取って損はないです(TLEしないならね)。

実装例

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

int main(){
    int a,b,A,B;
    cin>>a>>b;
    for(int i=0;i<10000;++i){
       A=i*108/100-i;
       B=i*110/100-i;
       if(A==a&&B==b) return cout<<i<<endl,0;
    }
    cout<<-1<<endl;
}

コンテスト中のACコード

D - String Formation

思考

気持ち的には前後に突っ込めるデータ構造さえあれば、あとは今反転状態かどうかだけ管理しておけばよしなにできます。Dequeを知ってますか？僕は知っています(欲しかったデータ構造そのものです)。

実装例

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

int main(){
    string s;
    int q,t,f;
    bool F{};
    char c;
    cin>>s>>q;
    deque<char> ans;
    for(auto C:s) ans.push_back(C);
    for(int i=0;i<q;++i){
        cin>>t;
        if(t==1) F=!F;
        else{
            cin>>f>>c;
            if(F) f=3-f;
            if(f-1) ans.push_back(c);
            else ans.push_front(c);
        }
    }
    if(F){
        for(auto it=ans.rbegin();it!=ans.rend();++it){
            cout<<*it;
        }
        cout<<endl;
    }
    else{
        for(auto it=ans.begin();it!=ans.end();++it){
            cout<<*it;
        }
        cout<<endl;
    }
}

コンテスト中のACコード

E - Divisible Substring

思考

pが2か5の時は簡単で、末尾が2,5の倍数となっているようなやつを数え上げるだけです。今後はpは2,5でない素数だとします。ロリハみたいなノリで、下M桁(0\leq M\lt N)を全て0としたときのあまりを調べることができます。今pは2,5出ない素数なので、「整数Xがpで割り切れる」と「整数Xの後ろに0を適当に加えた整数がpで割り切れる」は同値です。先ほどの余りが一致するようなMの組を考えると、よしなになります(時間がないからあとで追記するかも)。

実装例

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

int main(){
    int n,p;
    string s;
    cin>>n>>p>>s;
    if(p==2||p==5){
        ll ans{};
        for(int i=0;i<n;++i){
            if((s[i]-'0')%p==0){
                ans+=i+1;
            }
        }
        cout<<ans<<endl;
        return 0;
    }
    int tmp{1};
    ll ans{};
    vector<int> V(n+1),v(p);
    for(int i=0;i<n;++i){
        V[i+1]=V[i]*10+s[i]-'0';
        V[i+1]%=p;
    }
    for(int i=n;i>=0;--i){
        ans+=v[(V[i]*tmp)%p]++;
        tmp*=10;
        tmp%=p;
    }
    cout<<ans<<endl;
}

コンテスト中のACコード

F - Removing Robots

思考

ロボットは適当にソートすることで、i\lt j \Rightarrow X_i \lt X_jとして良いです。i番目のロボット以右のロボットに関する問題の答えをdp[i]とします。i番目のロボットを起動した時に、起動しない最も左のロボットをjとすると、dp[i]=dp[i+1]+dp[j]となります。ここで全てのロボットが起動するときはdp[i]=dp[i+1]+1となります。あとはjを求めればいいのですが、これはにぶたんとセグ木使うとよしなになります(追記予定)。

実装例

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

struct STree //一点更新で区間maxを返すセグメント木
{
    void ud(int i,int x); //更新
    int gt(int i,int j); //[i,j)に対するクエリを返す
};

struct modint; //いつもの

int main(){
    int n;
    cin>>n;
    vector<pair<int,int>> xd(n);
    for(auto&p:xd) in>>p.first>>p.second;
    sort(xd.begin(),xd.end());
    vector<int> x(n),d(n);
    for(int i=0;i<n;++i) tie(x[i],d[i])=xd[i];
    vector<modint> dp(n+1);
    dp[n]=1;
    STree<int> st(n,-1);
    for(int i=0;i<n;++i) st.ud(i,i+1);
    for(int i=n-1;i>=0;--i){
        dp[i]=dp[i+1];
        int j=lower_bound(x.begin(),x.end(),x[i]+d[i])-x.begin();
        j=st.gt(i,j);
        st.ud(i,j);
        dp[i]+=dp[j];
    }
    cout<<dp[0]<<endl;
    
}

コンテスト中のACコード

終わりに

ブログをちゃんと書くには余裕を持って全完しなければならない(戒め)。


スポンサードリンク