競プロ参加記035 AtCoder Beginner Contest 192 (ABC192)

Atcoder

はじめに

SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) – AtCoder

A～Eの5完でした。
10分くらい寝坊して参加を迷いましたが、折角なので参加しました。
(Dで11WAくらいしたので、寝坊が誤差になっていました)

最近、考察が難しいDに簡単な最短経路のEというセットが多くなってきましたね。

A – Star

A – Star (atcoder.jp)

X%100で下二桁が取り出せるので、100-X%100をすることで100の倍数にするまでの残りが分かります。

#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>

using namespace std;
//using namespace boost::multiprecision;

int main(){
    int X;
    cin>>X;
    int nx=100-X%100;
    cout<<nx<<endl;
}

B – uNrEaDaBlE sTrInG

B – uNrEaDaBlE sTrInG (atcoder.jp)

問題文の通り実装します。
具体的には、フラグを立てておいて各文字をチェックし、1文字でも”読みにくい文字列”に当てはまらない場合はフラグを降ろすようにします。

#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>

using namespace std;
//using namespace boost::multiprecision;

int main(){
    string S;
    cin>>S;
    bool f=false;

    for(int i=0;i<S.size();i++){
        if(i%2==0){
            if(S[i]>='A'&&S[i]<'Z') f=true;
        }
        if(i%2==1){
            if(S[i]>='a'&&S[i]<'z') f=true;
        }
    }
    if(f) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}

C – Kaprekar Number

C – Kaprekar Number (atcoder.jp)

カプレカ数といえば、

JavaScriptでカプレカ数計算ツールを作ってみた | ぬるからの雑記帳 (nullkara.jp)

前回ツールもどきをJSで作ったやつですね。
入力例 3の6174のように、何回やってもループする面白い性質を持つ数です。
Nを降順ソートしたものから、昇順ソートしたものを引いていけばいいです。私はバケツソートっぽいものを組みました。

#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>

using namespace std;
//using namespace boost::multiprecision;

int main(){
    int N,K;
    cin>>N>>K;

    for(int i=0;i<K;i++){
        int c[10]={0};
        while(N!=0){
            c[N%10]++;
            N/=10;
        }
        int mx=0,mn=0;
        int cn=0;
        for(int j=0;j<=9;j++){
            int cn2=0;
            while(cn2<c[j]){
                mx+=pow(10,cn)*j;
                cn++;
                cn2++;
            }
        }
        cn=0;
        for(int j=9;j>=0;j--){
            int cn2=0;
            while(cn2<c[j]){
                mn+=pow(10,cn)*j;
                cn++;
                cn2++;
            }
        }
        N=mx-mn;
    }
    cout<<N<<endl;
}

D – Base n

D – Base n (atcoder.jp)

考察

nを増やすことで、Xをn進法表記にみなした値も”基本”増えます。
“基本”と書いたのは、Xの大きさが1の場合は増えないからです。
※n進法の計算上、1桁目は0乗を掛けるのでnが増えても増えない

Xの大きさが2の場合、値はnに比例して増えます。
※n進法の計算上、2桁目は1乗を掛けるので2桁目の数分増える
Xが3以上の場合は、値は大きく増えます。
例えば最小の100だと、値はn^2になります。

AC解答(嘘解法)


考察から以下のように場合分けしました。

  • Xの大きさが1の場合
    Mより大きくなるか、小さくなるかで答えは0か1になる
  • Xの大きさが2の場合
    nを増やしたときの増加量が一定なので、計算で求める
  • Xの大きさが3の場合
  • 愚直に計算する
#include<bits/stdc++.h>
//#include<boost/multiprecision/long long.hpp>

using namespace std;
//using namespace boost::multiprecision;

int main(){
    string X;
    long long Xn[100];

    long long M;
    cin>>X>>M;
      for(int i=0;i<X.size();i++){
        Xn[i]=X[i]-'0';
     // cout<<Xn[i]<<endl;
    }
    long long d=0;
    for(int i=0;i<X.size();i++){
        d=max(d,Xn[i]);
    }

    if(X.size()==1){
        if(Xn[0]<=M) cout<<"1"<<endl;
        else cout<<"0"<<endl;
        return 0;
    }
    long long ans=0;
    d++;
    long long bef=-1;
    long long bef2=-1;
    int sz=X.size();
    while(1){
        long long m=0;
        long long dd=1;
        for(int i=sz-1;i>=0;i--){
            m+=dd*Xn[i];
            dd*=d;
        }
        if(m>=0&&m<=M) ans++;
        else break;
        d++;
        if(sz==2){
            if(bef==-1) bef=m;
            else  {
                bef2=m;
                long long sa=bef2-bef;
                long long no=M-bef2;
                ans+=no/sa;
                break;
            }
        }
    }
    cout<<ans<<endl;
}

最悪計算量は、X=”100″、M=10^8のときです。
n^2ずつ増えるので、答えは約10^9です。n進変換でO(|X|=3)かかっているので、3*10^9かかります。
簡易な処理だとC++は10^9で1secと言われてるので、3secかかります。(実際コードテストで動かしたら、2964 msでした)
….のはずですが、1981msでACしてました。嘘解法ですね！！！

エデュ解

考察で書いた通り、Xの大きさが2以上の場合はnが増えるごとに単調増加します。
単調増加するということは、あいつが使えそうです….そう二分探索です。

そのため、以下のように場合分けします。

  • Xの大きさが1の場合
  • Mより大きくなるか、小さくなるかで答えは0か1になる
  • Xの大きさが2以上の場合
    二分探索で、M以下になるときに最大のnを求めて、max(最大のn-d-1,0)を取る
#include<bits/stdc++.h>
#include<boost/multiprecision/cpp_int.hpp>

using namespace std;
using namespace boost::multiprecision;

int main(){
    string X;
    cpp_int Xn[100];

    cpp_int M;
    cin>>X>>M;
      for(int i=0;i<X.size();i++){
        Xn[i]=X[i]-'0';
    }
    cpp_int d=0;
    for(int i=0;i<X.size();i++){
        d=max(d,Xn[i]);
    }

    if(X.size()==1){
        if(Xn[0]<=M) cout<<"1"<<endl;
        else cout<<"0"<<endl;
        return 0;
    }

    cpp_int l=1;
    cpp_int r=M*2;
    while(1){
        cpp_int n=0;
        cpp_int m=(l+r)/2;
        //cout<<m<<endl;
        cpp_int dd=1;
        for(int i=X.size()-1;i>=0;i--){
            n+=dd*Xn[i];
            dd*=m;
        }
        if(n<=M){
            if(l==m) break;
            l=m;
        }
        else{
            if(r==m) break;
            r=m;
        }
    }
    if(r-d-1>=0) cout<<r-d-1<<endl;
    else cout<<"0"<<endl;
}

オーバーフローが怖いので、boostの多倍長を使いました。

余談

D問題、どうやらclarがたくさん飛んでたらしいです。
何かというと、”Xの大きさが1のとき、答えが∞になるじゃないか！”というものです。
“M以下であるようなものは何種類あるでしょうか？”を”何個あるでしょうか”と誤読したっぽいですね。
私も一瞬誤読していましたが、どうせ誤読してると思って問題文を丁寧に読み返したら解決しました。
自分のことをあんまり信用しない性格がここで活きましたね。

E – Train

E – Train (atcoder.jp)

無向グラフに対してダイクストラやるだけ…ですね。
Kの倍数時間でしか移動できないため、次のマスに移動するときに”次のマス=今のマス+辺の時間”とはならず、加えて移動までの待ち時間が加わります。
そこさえ上手く落とし込めば単純なダイクストラになります。

#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>

using namespace std;
//using namespace boost::multiprecision;

int main(){
    long long N,M,X,Y;
    cin>>N>>M>>X>>Y;

    vector<pair<long long,pair<long long,long long>>> v[N+1];
    for(int i=0;i<M;i++){
        long long A,B,T,K;
        cin>>A>>B>>T>>K;
        v[A].push_back(make_pair(B,make_pair(T,K)));
        v[B].push_back(make_pair(A,make_pair(T,K)));
    }

    queue<long long> q;
    q.push(X);

    long long ans[N+1];
    for(int i=0;i<N+1;i++) ans[i]=-1;
    ans[X]=0;
    while(!q.empty()){
        long long n=q.front();
        long long nn=ans[n];
        q.pop();
        for(int i=0;i<v[n].size();i++){
            long long t=v[n][i].first;
            long long tt=v[n][i].second.first;
            long long tk=v[n][i].second.second;
            long long nt;
            if(nn%tk==0) nt=nn;
            else{
                nt=nn+tk-nn%tk;
            }
            //    cout<<nn<<","<<tk<<","<<nt<<endl;
            nt+=tt;
            if(ans[t]==-1||ans[t]>nt){
                ans[t]=nt;
                q.push(t);
            }
        }
    }
    cout<<ans[Y]<<endl;
}

次の列車がくるまでの時間はA問題と同じ要領で求めることができます。
注意点は、倍数きっかりのときに次の倍数まで待たなくていい点です。

F – Potion

F – Potion (atcoder.jp)

エデュ解見て通しました。

kを固定して考えるとします。
その場合、”X”から”Aからk個選んだときの和”を引いたときにkの倍数となるような選び方の中で、”Aからk個選んだときの和”の最大を求める問題。
と言い換えることができます。
※”X”から”Aからk個選んだときの和”を引いたときにkの倍数とならないと、kを何回増やしてもXにならない。
　また、kの倍数となるとき”Aからk個選んだときの和”が大きいほどkを足す回数(=時間)は少なくなる。

kの倍数かどうかが知りたいため、これは
dp[何個目の素材か][素材をいくつ加えたか][素材の合計%k]
が最大になるように更新していくことで求められます。

また、素材数は最大100しかないため、1～100の全パターンの種類数に対してdpを行っても十分間に合います。(dpの更新にO(Nk^2)かかるので、N回やっても高々O(N^4)くらいで収まる)

#include<bits/stdc++.h>
//#include<boost/multiprecision/long long.hpp>

using namespace std;
//using namespace boost::multiprecision;

int main(){
    long long N,X;
    cin>>N>>X;

    long long A[N];
    for(int i=0;i<N;i++){
        cin>>A[i];
    }

    long long ans=LLONG_MAX;
    for(int K=1;K<=N;K++){
        long long dp[N+1][K+1][K];
        for(int i=0;i<N+1;i++){
            for(int j=0;j<K+1;j++){
                for(int k=0;k<K;k++){
                    dp[i][j][k]=-1;
                }
            }
        }

        dp[0][0][0]=0;
        for(int i=0;i<N;i++){
            for(int j=0;j<K+1;j++){
                for(int k=0;k<K;k++){
                    if(dp[i][j][k]!=-1){
                        if(j!=K) dp[i+1][j+1][(k+A[i])%K]=max(dp[i+1][j+1][(k+A[i])%K],dp[i][j][k]+A[i]);
                        dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]);
                    }
                }
            }
        }
        //cout<<K<<","<<dp[N][K][X%K]<<endl;
        if(dp[N][K][X%K]!=-1) ans=min(ans,(X-dp[N][K][X%K])/K);
    }
    cout<<ans<<endl;
}

この問題、F問題らしくて好きです。

おわりに

最近、社内で開催された機械学習のコンペに取り組んでいたのですが…
見事にハマりました＼(^o^)／
来月からはKaggle等の機会学習コンペにも手を出していきたいですね。
(atcoderのヒューリスティックがあるので、本格的な取り組みは来年度になりそう？)

コメント

タイトルとURLをコピーしました