AtCoder Beginner Contest 114の解説＋α

ABC114の解説とか別解とか．

A 753
B 754
- その他
C 755
D 756
- 素因数の組み合わせの全探索
- DP
その他
- 典型ポイント
- 所感

A 753

はい．

print("YES" if int(input()) in {3, 5, 7} else "NO")

B 754

文字列を切り出して絶対値をとる．

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define int long long
using namespace std;

signed main(){
    string s;
    cin >> s;

    int ans = 1e8;
    rep(i,s.size() - 2){
        ans = min(ans, abs(753LL - stoi(s.substr(i,3))));
    }
    cout << ans << endl;
}

その他

文字列の長さと切り出す長さがともに $10 ^ 5$ ぐらい大きくなっても解ける．しゃくとり法を使えば線形時間である（modを取るのは必須）．

C 755

357のみからなる数値の全列挙

自分が最初に書いた解法は公式の想定解法と同じ． $3, 5, 7$ からなる数値を全列挙し，それが条件を満たすかを調べる．

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define int long long
using namespace std;

int n;
int ans;

vector<int> v = {3,5,7,};

bool check(int number){
    bool res[3] = {};
    while(number != 0){
        rep(i,3){
            if(number % 10 == v[i]) res[i] = true;
        }
        number /= 10;
    }
    return res[0] and res[1] and res[2];
}

void dfs(int number){
    if(number > n) return;
    if(check(number)) ans++;

    number *= 10;
    for(auto i : v){
        dfs(number + i);
    }
}

signed main(){
    cin >> n;
    dfs(0);
    cout << ans << endl;
}

桁DP

公式解説放送でも触れられていたように，別解として桁DPがある．桁DPは $1 〜 N$ までの数値に，ある条件を満たす数値がいくつあるかを $O(\log N)$ で数え上げることができる．つまり，今回の問題の制約が $1 \leq N \leq 10 ^ {100000}$ でも解ける．典型な400点問題っぽい．

DPテーブルの意味は以下である．今回は $0, 3, 5, 7$ 以外の数字は使わないため，数字は $4$ 種類だけ考える．

dp[i][j][k][l][m][n] = 
    [どこまで見たか]
    [Nより小さいことが確定しているか]
    [3が含まれているか]
    [5が含まれているか]
    [7が含まれているか]
    [0が含まれているか（先頭の0を除く）]

桁DPは上位の桁から数字を決定していくため，小さい値は $0$ を先頭に詰める．そのため， $3,7,5$ に加え $0$ も必要になる．また，[0が含まれているか（先頭の0を除く）]は， $00357$ と $03570$ などの区別をつけるために必要である．

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define int long long
using namespace std;

signed main(){
    string s;
    cin >> s;

    int dp[20][2][2][2][2][2] = {};
    dp[0][0][0][0][0][0] = 1;
    rep(i,s.size()) rep(j,2) rep(k,2) rep(l,2) rep(m,2) rep(n,2) {
        int lim = j ? 9 : s[i] - '0';
        for(auto d : {0, 3, 5, 7}){
            if(d > lim) break;
            dp[i + 1][j or d < lim][k or d == 3][l or d == 5][m or d == 7][n or (d == 0 and (k or l or m))]
                += dp[i][j][k][l][m][n];
        }
    }

    int sum = 0;
    rep(i,2){
        sum += dp[s.size()][i][1][1][1][0];
    }
    cout << sum << endl;
}

愚直解（っぽいの）

また，愚直解（っぽいの）を高速化することでも通る．本質は想定解と同じ．

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define int long long
using namespace std;

bool check(int n){
    bool r[3] = {};
    while(n > 0){
        int a = n % 10;
        n /= 10;
        if(a != 3 and a != 5 and a != 7) return false;
        if(a == 3) r[0] = true;
        if(a == 5) r[1] = true;
        if(a == 7) r[2] = true;
    }
    return r[0] and r[1] and r[2];
}

signed main(){
    int n;
    cin >> n;

    int ans = 0;
    for(int i = 3; i <= n; i++){
        for(int j = 1e9; j > 0; j /= 10){
            if(i >= j and  i / j % 2 == 0){
                i += j - 1;
                break;
            }
        }
        if(check(i)) ans++;
    }
    cout << ans << endl;
}

$1 〜 N$ を単純にループさせるとTLEするので以下の部分で高速化を図る．

for(int j = 1e9; j > 0; j /= 10){
    if(i >= j and  i / j % 2 == 0){
        i += j - 1;
        break;
    }
}

$i$ のある桁が偶数なら $i$ は七五三数ではないことが明らかなので，その値を雑に飛ばしている．偶数を使わない $5$ 進数にすることに近い．こんな中途半端に高速化する意味はない．

D 756

素因数の組み合わせの全探索

$N!$ を素因数分解し，素因数の組み合わせを再帰的に全探索すればACする．素因数の数が少なく，約数が $75$ までなので全探索でも十分に間に合う．

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define int long long
using namespace std;

void primeFactor(int n, map<int,int>& m){
    for(int i = 2; i * i <= n; i++){
        while(n % i == 0){
            ++m[i];
            n /= i;
        }
    }
    if(n != 1) m[n] += 1;
}

int ans;

void dfs(int idx, int p, vector<int>& v){
    if(p == 75) ans++;
    if(idx >= v.size() or p >= 75){
        return;
    }

    rep(i,v[idx] + 1){
        dfs(idx + 1, p * (i + 1), v);
    }
}

signed main(){
    int n;
    cin >> n;

    map<int,int> m;
    range(i,1,n + 1){
        primeFactor(i,m);
    }

    vector<int> v;
    for(auto i : m){
        v.emplace_back(i.second);
    }
    dfs(0, 1, v);
    cout << ans << endl;
}

DP

$2 ^ 3 3 ^ 2$ と $2 ^ 2 3 ^ 3$ は，約数の数で見れば同じである．つまり，素因数 $e _ i$ までを用いて表現される値の約数が $x$ 個であるならば，それらをまとめて計算できる．つまり，

$dp[i][j] := e _ i$ までを用いて表現される値の約数の個数が $j$ になる場合の数

としてDPを更新できる．

計算量が計算しにくい． $O(\frac{N ^ 2X}{\ln N})$ よりも結構少なそう（ $X$ は約数の個数）．

$N = 1000, X = 1000$ でも高速に動いた．

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define int long long
using namespace std;

void primeFactor(int n, map<int,int>& m){（略）}

int dp(vector<int>& e, int x = 75){
    vector<vector<int>> dp(e.size() + 1, vector<int>(x + 1,0));
    dp[0][1] = 1;
    rep(i,e.size()){
        range(j,1,x + 1){
            rep(k,e[i] + 1){
                if(j * (k + 1) > x) break;
                dp[i + 1][j * (k + 1)] += dp[i][j];
            }
        }
    }
    return dp[e.size()][x];
}

signed main(){
    int n;
    ...
   （略）
    ...
        v.emplace_back(i.second);
    }
    cout << dp(v) << endl;
}

その他

典型ポイント

巨大な値を素因数の積で表現する
約数を見たら素因数を考える
再帰関数による全列挙

所感

CもDも全探索で解けるので割と難易度は低めだと思う．「とりあえずわからない部分は愚直（ナイーブ，全探索）に考える」ことはかなり重要で，これができると急に解ける問題が増える．

Cを解けるかどうかの境目にいる人は，DFSやBFSのような全探索と，とりあえず全探索する方法を考えることが重要になってきそう．