AtCoder Beginner Contest 114

更新日時:

AtCoder Beginner Contest 114

ソースコード

解法のメモ

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$ を用いて以下の通りに書けるものである。

  1. $p^{74}$,
  2. $p^4 q^{14}$,
  3. $p^2 q^{24}$,
  4. $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_divisiondownto は知らなかった。

その他

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

コメントする