noyのブログ

健康なエンジニアを目指す人のブログ

AtCoder Beginner Contest 114の解説+α

ABC114の解説とか別解とか.

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のような全探索と,とりあえず全探索する方法を考えることが重要になってきそう.