AtCoder Beginner Contest 114
Updated:
Source codes
Solutions
A - 753
$x = 3, 5, 7$ ならば “YES” 、そうでないなら “NO” を出力する。
B - 754
ます s = gets.chomp で受け取る。続けて 3 文字を列挙して to_i して $753$ との最小値を取れば良い。
ポイント
Ruby だと配列に全部突っ込んで最後に min を取る実装の方が Ruby らしい。
s = gets.chomp
ans = []
for i in 0...s.size - 2
ans << (753 - s[i...i + 3].to_i).abs
end
puts ans.min
C - 755
$10$ 桁以下の七五三数を全て列挙して、それらが $N$ 以下であるかどうか調べれば良い。列挙する個数はせいぜい $3^{11}$ 個で押さえられる。列挙する際は、例えば文字列で持っておき、深さ優先探索をする。ただし $7$, $5$, $3$ が全て現れていないといけないので、最終結果を文字列の状態で include?("7") などを用いて判定する必要がある。
ポイント
concat に自信が持てず調べていた。
D - 756
require 'prime' で Prime.prime?(i) で $100$ 以下の素数を hash の index に入れておく。その後 $N!$ を素因数分解した結果をこの hash の中に入れるのだが、順番に素因数分解すればよろしい。例えば以下のようにする。
for i in 1..n
i.prime_division.each{|prime, cnt|
hash[prime] += cnt
}
end
ここで、以下の通りに定める。
$a[i] = $
cntが $i$ 以上であるような素因数の個数
これは逆順に足していけば良い。 Ruby だと以下の通りである。
ary = Array.new(100){0}
hash.each{|prime, cnt|
ary[cnt] += 1
}
98.downto(0){|i|
ary[i] += ary[i + 1]
}
あとは約数の個数が $75 = 3 \times 5^2$ に一致するものを列挙すれば良い。これは相異なる素数 $p, q, r$ を用いて以下の通りに書けるものである。
- $p^{74}$,
- $p^4 q^{14}$,
- $p^2 q^{24}$,
- $p^2 q^4 r^4$.
当然 1. は $a[74]$ 通りである。 2., 3. に関しては若干難しい。まず $q$ から選び、次に $q$ と相異なる $p$ を選べばいいから、 それぞれ $(a[4] - 1)a[14]$ 通り、 $(a[2] - 1)a[24]$ 通りである。最後の 4. も $(q, r)$ の順は区別しないので、まずこれが $a[4] (a[4] - 1)/2$ 通り、あとは $p$ として $a[2] - 2$ 通りであるから、結局答えは以下の通りである。
\[ a[74] + (a[4] - 1)a[14] + (a[2] - 1)a[24] + (a[2] - 2) \frac{a[4] (a[4] - 1)}{2}. \]
ポイント
Prime.prime?(i) を知っていたので簡単に実装できた。 prime_division と downto は知らなかった。
Others
26 位でした。
A - sample: 2, tle: 2.000, time: 01:16, from_submit: 22:41
B - sample: 3, tle: 2.000, time: 01:46, from_submit: 20:55
C - sample: 3, tle: 2.000, time: 07:35, from_submit: 13:20
D - sample: 3, tle: 2.000, time: 13:20, from_submit: 00:00