「 2019年02月 」一覧

ABC114

AtCoder, 競技プログラミング

A – 753

問題

A - 753
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp

解法

入力Xが7, 5, 3かどうかをチェックするだけです

実装

x=gets.to_i
puts (x==7 || x==5 || x==3)  ? "YES" : "NO"

B – 754

問題

B - 754
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp

解法

文字列の長さが最大で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

問題

C - 755
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp

解法

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

問題

D - 756
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp

解法

七五数の条件である、「約数をちょうど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