2019-03-11

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