n度あることはn+1度ある

書きたいことを書く 統一性はない

ABC114 所感

お疲れさまでした。最近さぼってた割にはそこそこ頑張れたんじゃないのかなと思います。今月はできるだけ復帰していきます。

A - 753

入力が7,5,3のときだけ"YES"をだす。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int x; cin>>x;
    if(x==7||x==5||x==3)
        cout<<"YES";
    else
        cout<<"NO";
}

B - 754

最大の文字列長が10なので、3つずつ見ていけばよいです。C++なのでASCIIコードの性質を利用すれば以下のようにできます。

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s; cin>>s;
    unsigned long min=-1;
    for(int i=0;i<s.size()-2;i++){
        long t= (s[i]-'0')*100+(s[i+1]-'0')*10+(s[i+2]-'0');
        if(abs(t-753)<min)
            min=abs(t-753);
    }
    cout<<min;
}

C - 755

結構悩みましたが、7,5,3が入っている数列を9桁まで列挙したところで大した数にならないので、全ての数列を作り、7,5,3が1つずつはいっている且つ入力した数値以下のものを選択するようにしました。

#include <bits/stdc++.h>
using namespace std;
int main(){
    long n;cin>>n;
    if(n<357){
        cout<<"0";
        return 0;
    }
    
    vector<long> a={3,5,7};
    vector<long> ap=a;
    vector<long> k={3,5,7};
    for(int i=1;i<9;i++){
        vector<long> aa;
        for(auto x:k){
            for(auto y:ap){
                long t=pow(10,i)*x;
                aa.push_back(t+y);
            }
        }
        a.insert(end(a),begin(aa),end(aa));
        ap=aa;
    }
    long count=0;
    for(auto x:a){
        if(x<=n){
            int c[3]={0};
            while(x!=0){
                int t=x%10;
                if(t==3)
                    c[0]=1;
                if(t==5)
                    c[1]=1;
                if(t==7)
                    c[2]=1;
                x/=10;
            }
            if(c[0]==1&&c[1]==1&&c[2]==1)
                count++;
        }
    }
    cout<<count;
}

D - 756

できませんでした。問題を解くどころか、素因数と約数の関係まで忘れている始末なのでできなくて当然だと思います。明日復習します。
(2018/12/4 更新) 解いてみました。
解説の通り、素因数分解して、約数が75個存在する場合の数を数えればよいです。
三重ループの中の比較で本来ならば6通り確認する必要がありますが、p4 q4 r2とq4 p4 r2は同じ数値のため、3通りの確認でよいです。
ここのループでijを見間違えていてそれを発見するのにすごく時間をかけてしまいました。

#include <bits/stdc++.h>
using namespace std;
int main(){
    long n; cin>>n;
    vector<long> v(100,0);
    for(int i=2;i<=n;i++){
        long t=i;
        for(int j=2;j<=t;j++){
            while(t%j==0){
                v[j]++;
                t/=j;
            }
        }
    }
    int count=0;
    for(int i=2;i<=n;i++){
        if(v[i]>=74)
            count++;
        for(int j=i+1;j<=n;j++){
            if(v[i]>=2&&v[j]>=24)
                count++;
            if(v[i]>=24&&v[j]>=2)
                count++;
            if(v[i]>=4&&v[j]>=14)
                count++;
            if(v[i]>=14&&v[j]>=4)
                count++;
            for(int k=j+1;k<=n;k++){
                if(v[i]>=2&&v[j]>=4&&v[k]>=4)
                    count++;
                if(v[i]>=4&&v[j]>=2&&v[k]>=4)
                    count++;
                if(v[i]>=4&&v[j]>=4&&v[k]>=2)
                    count++;
            }
        }
    }
    cout<<count;
}

総括

300点問題を時間内に解くことができるようになってきているのは進歩ですが、400点問題がネックなのでなんとか頑張っていきます。