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; }
その他
文字列の長さと切り出す長さがともに ぐらい大きくなっても解ける.しゃくとり法を使えば線形時間である(modを取るのは必須).
C 755
357のみからなる数値の全列挙
自分が最初に書いた解法は公式の想定解法と同じ. からなる数値を全列挙し,それが条件を満たすかを調べる.
#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は までの数値に,ある条件を満たす数値がいくつあるかを で数え上げることができる.つまり,今回の問題の制約が でも解ける.典型な400点問題っぽい.
DPテーブルの意味は以下である.今回は 以外の数字は使わないため,数字は 種類だけ考える.
dp[i][j][k][l][m][n] = [どこまで見たか] [Nより小さいことが確定しているか] [3が含まれているか] [5が含まれているか] [7が含まれているか] [0が含まれているか(先頭の0を除く)]
桁DPは上位の桁から数字を決定していくため,小さい値は を先頭に詰める.そのため, に加え も必要になる.また,[0が含まれているか(先頭の0を除く)]は, と などの区別をつけるために必要である.
#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; }
を単純にループさせるとTLEするので以下の部分で高速化を図る.
for(int j = 1e9; j > 0; j /= 10){ if(i >= j and i / j % 2 == 0){ i += j - 1; break; } }
のある桁が偶数なら は七五三数ではないことが明らかなので,その値を雑に飛ばしている.偶数を使わない 進数にすることに近い.こんな中途半端に高速化する意味はない.
D 756
素因数の組み合わせの全探索
を素因数分解し,素因数の組み合わせを再帰的に全探索すればACする.素因数の数が少なく,約数が までなので全探索でも十分に間に合う.
#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
と は,約数の数で見れば同じである.つまり, 素因数 までを用いて表現される値の約数が 個であるならば,それらをまとめて計算できる.つまり,
までを用いて表現される値の約数の個数が になる場合の数
としてDPを更新できる.
計算量が計算しにくい. よりも結構少なそう( は約数の個数).
でも高速に動いた.
#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のような全探索と,とりあえず全探索する方法を考えることが重要になってきそう.