情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

AtCoder Beginner Contest 114

AtCoder Beginner Contest 114 (ABC114) の解説です。
AtCoder Beginner Contest 114 旧版
AtCoder Beginner Contest 114 beta版

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 114
rated 1200
12/2(日) 21:00 ～ 22:40 (100分)
100-200-300-400 (4問)
ペナルティ: 5分

方針

全完

A - 753

実際にやるだけです。

#include<iostream>
using namespace std;
int main() {
	int X;
	cin >> X;
	cout << (X == 3 || X == 5 || X == 7 ? "YES" : "NO");
	return 0;
}

B - 754

これも、先頭から順に取り出して比較するだけです。
なお、部分的な数字を取り出すときは、最初に文字列にしておいて後で数に変換すると楽です。

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int SUB = 6081; // '0' * 111 + 753
int main() {
	string S;
	cin >> S;
	int diff = 999; // 大きい数字、INFとかで良い
	for (int i = 2, l = S.size();i < l;++ i) diff = min(diff, abs(S[i - 2] * 100 + S[i - 1] * 10 + S[i] - SUB));
	cout << diff;
	return 0;
}

C - 755

先頭から桁を決め打ちしていくと、一種の動的計画法で解くことができます。
まず、簡単のためにNを10^n-1の形であるものとします。
dp_{x,y}を上からx桁まで決め打った時、現れる数字の集合がyである組み合わせの個数とします。
例えば、dp_{2, \{ 3, 5 \}} = dp_{1, \{ 3 \}} + dp_{1, \{5 \}} + dp_{1, \{ 3, 5 \}}のように表すことができますね。
yに関しては2^0, 2^1, 2^2を3, 5, 7と関連付けることでbitDPのようにして扱うことができます。
つまり、例えばdp_{2, \{ 3, 5 \}}を代わりに5=2^1, 3=2^0として、dp_{2, 3}とするわけですね。
これを用いて、上から順に遷移を解き、全てのdp_{x, 7}を合計すれば答えになります。
次に、ちゃんとNが任意の場合について考えられるようにしましょう。
これは、dpの状態にもう一個持たせるようにして、dp2_{x, y}は上からx桁まで決め打った時、現れる数字の集合がyでかつ今までの状態がNの上位x桁と完全一致している場合を考えます。
これを用いて、このdp2はNを超えない遷移しか認めないようにし、またNより小さくなるならその分の値はdpの方に遷移させます(上位の桁から決めてるので、この時点でNより小さいなら以降は全てNより小さいため)
これにより、{\rm O}(\log N)で求めることができます。

#include<iostream>
#include<cstring>
using namespace std;
int main() {
	string N;
	cin >> N;
	int dp[10][8]; // 第x桁目に部分集合y(y:{3,5,7})ができている組み合わせ
	memset(dp, 0, sizeof(dp)); // 全ての初期値は0よね

	bool isCover = true; // 全てNと同じ値を選ぶような選び方が存在するか否か
	for (int i = 0, nowDigit, j, k, cover = 0;i < N.size();++ i) {
		nowDigit = N[i] & 15; // 今見ている桁の値
		dp[i][0] = 1; // 第x桁目が空集合……すなわち今まで0だった、これが最初の桁の組み合わせは当然だが1通り
		for (j = 1;j < 8;j <<= 1) {
			for (k = 0;k < 8;++ k) dp[i + 1][j | k] += dp[i][k];
			if (isCover && (j & 6) + 3 > nowDigit) -- dp[i + 1][j | cover]; // Nを超える場合をちょっと引き算
		}
		cover |= 1 << (nowDigit - 3 >> 1); // 現時点で、Nと同じ値を連続して選んだ時の{3,5,7}の集合
		isCover &= ((nowDigit | nowDigit << 1) & 7) == 7; // これA問題と同じだね、誘導問だったか
	}
	cout << dp[N.size()][7]; // {3,5,7}全てを含む場合のみが答えなので
	return 0;
}

D - 756

まず、約数の個数の関係について知っておきましょう。
ある値が素因数分解の結果\prod_{i=1}^{x} {p_i}^{e_i}という形で表される時、その値の約数は\prod_{i=1}^{x} (e_i + 1)という形になります。
例えば、24=2^3 \cdot 3なので、約数の個数は(3+1) \cdot (1+1)=8個となります。
さて、N!をまずは素因数分解していきましょう。
ここで、100より小さい素数は25個しかないので、2 \leq i \leq Nについてそれぞれ25個の素数で割って個数を数えていけば大丈夫ですね。
さて次に、約数の個数が75=3 \cdot 5^2 = (74+1)=(2+1) \cdot (24+1) = (4+1) \cdot (14+1) = (2+1) \cdot (4+1) \cdot (4+1)個とのことなので、この条件を満たすか調べていきます。
これはまぁ、3重ループでも回しつつ素因数の個数が条件を満たすか調べていけば良いでしょう。
計算量は素因数分解のところで{\rm O}(\frac{N \sqrt N}{(\log N)^2})、数え上げで{\rm O}((\frac{N}{\log N})^3)です……あってるこれ？
ちなみにこのコードでは面倒なので予め出しておいた素数で殴ってます、まぁわざわざ篩で高速化してもねぇ……。

#include<iostream>
#include<cstring>
using namespace std;
int main() {
	int N;
	cin >> N;
	int divisor[25], prime[25] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}; // 約数の素因数分解結果
	memset(divisor, 0, sizeof(divisor));
	for (int i = 2, j, tmp;i <= N;++ i) for (j = 0, tmp = i;tmp > 1;++ j) for (int p = prime[j];tmp % p == 0;tmp /= p) ++ divisor[j]; // 素因数分解していくよー
	int ans = 0;
	for (int i = 0;i < 25;++ i) {
		if (divisor[i] >= 74) ++ ans; // a^74の形
		for (int j = 0;j < 25;++ j) {
			if (i == j) continue;
			if (divisor[i] >= 4 && divisor[j] >= 14) ++ ans; // a^4*b^14の形
			if (divisor[i] >= 2 && divisor[j] >= 24) ++ ans; // a^2*b^24の形
			for (int k = j + 1;k < 25;++ k) if (i != k && divisor[i] >= 2 && divisor[j] >= 4 && divisor[k] >= 4) ++ ans; // a^2*b^4*c^4の形
		}
	}
	cout << ans;
	return 0;
}

結果

oooo 4完(1000点) 01:51-05:53-61:06-75:37 / 75:37
222位

感想

今回は知識と実装がともにやや難しめで、発想力を試されたのではないでしょうか。
ですが、恐らく枝刈りなどの手法で重い計算量でも強引にACできる可能性も高く、案外すんなり解けた人もいるのかもしれません。
まぁ何にせよ今回の問題は全て典型的な問題なので、競プロをやっていこうと思った場合はこの問題セットは確実に正解できるようになっておきたいですね。