A – 753
問題
解法
入力Xが7, 5, 3かどうかをチェックするだけです
実装
x=gets.to_i puts (x==7 || x==5 || x==3) ? "YES" : "NO"
B – 754
問題
解法
文字列の長さが最大で10なので、前から順番に3文字ずつ選んで整数に変換し、753との差の絶対値をとっていき、その最小値を解とすればよいです。
実装
s=gets.chomp ans=Float::INFINITY 0.upto(s.length-3) do |i| ans = (s[i,3].to_i - 753).abs if ans > (s[i,3].to_i - 753).abs end
C – 755
問題
解法
300点にしては意外と難しかったです。
Nは最大で999999999なので、全ての整数をチェックしていくのは現実的では無いです。
ここで、Nが999999999の時に各桁が7, 5, 3のみからなる数字がどれくらいあるか考えます。
この場合、39なので19,683個しかありません。(なお、七五三数は 7, 5, 3がそれぞれ1回以上現れる必要があるので、これより少なくなります)
よって、全ての七五三数を探索してN以下のものを数え上げればよいです。
実装
「7, 5, 3がそれぞれ1回以上」というのがちょっと面倒です。
ここでは、とりあえず7, 5, 3からなる整数を作っておき、後で各数字が1回以上あるかどうかを判定しています。
N=gets.to_i l = N.to_s.length n = ['3','5','7'] m = ['3','5','7'] 2.upto(l) do |i| tmp = [] m.each do |j| n.each do |k| if k.length == i-1 tmp << k + j end end end n += tmp end ans = 0 n.each do |v| if v.include?('3') && v.include?('5') && v.include?('7') if v.to_i <= N ans += 1 end end end puts ans
D – 756
問題
解法
七五数の条件である、「約数をちょうど75個持つ正の整数」について最初に考えます。
これは素因数分解すると以下の形で表すことができます。
– p74
– p24q2
– p14q4
– p4q4r2
そこで、N!の素因数分解を行い、N!の約数のうち上記のパターンで表せるものを数えていきます。
なお、N!の素因数分解は、1〜Nをそれぞれ素因数分解し、各指数部分を加算していけば求めることが出来ます。
実装
Rubyのpermutationメソッドを使って組み合わせを列挙し、計算結果がN!の約数かどうかをチェックして数え上げていきます。
require 'prime' N=gets.to_i h = Hash.new(0) 1.upto(N) do |i| i.prime_division.each do |a,b| h[a] += b end end nn = 1 1.upto(N) do |i| nn *= i end ans = [] h.keys.permutation(3) do |a,b,c| tmp = a**4 * b**4 * c**2 if nn % tmp == 0 ans << tmp end end h.keys.permutation(2) do |a,b| tmp = a**24 * b**2 if nn % tmp == 0 ans << tmp end tmp = a**14 * b**4 if nn % tmp == 0 ans << tmp end end h.each do |k,v| ans << k ** 74 if v >= 74 end p ans.uniq.size