結果

問題 No.294 SuperFizzBuzz
コンテスト
ユーザー code-devo
提出日時 2016-03-05 13:19:51
言語 Ruby
(3.4.1)
結果
AC  
実行時間 110 ms / 5,000 ms
コード長 1,434 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 12,288 KB
最終ジャッジ日時 2024-12-26 06:03:02
合計ジャッジ時間 2,498 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

def combination(n, r)
  r = n - r if n - r < r
  return 1 if r == 0
  num = n.downto(n-r+1).inject(&:*)
  den = r.downto(1).inject(&:*)
  return num / den
end

K = 25
TBL1 = Hash.new{0} #K桁までのSuperFizzBuzzの数を格納する。
TBL2 = {} #K桁までの、3と5の組み合わせの数を格納する（下一桁は5）。
for five in 1..K do
  for three in 0..(K-five) do
    count = combination(three + five - 1, five - 1) #下1桁は5となるので、第二引数から1を引く。
    TBL1[three + five] += count if five % 3 == 0
    TBL2[[three, five]] = count
  end
end

n = gets.to_i

#n番目のSuperFizzBuzzが、何桁目の何番目であるかを求める。
#keta: 何桁目か
#no: 何番目か
keta = 1
sum = 0
loop do
  count = TBL1[keta]
  break if sum + count >= n #n以上になったら、n番目のSuperFizzBuzzがketa桁目にあると判断できる。
  sum += count
  keta += 1
end
no = n - sum

#最上位桁から順に、その桁が"3"なのか"5"なのかを確定していく。
three = 0 #確定した"3"の数。
five = 0 #確定した"5"の数。
sum = 0
ans = []
(keta).downto(1) do |k|
  count = 0 #k桁目を"3"とした場合にできるSuperFizzBuzzの数。
  (3 - five % 3).step(k - 1, 3) do |f|
    t = k - f - 1
    count += TBL2[[t, f]]
  end

  if sum + count < no then
    ans << "5"
    five += 1
    sum += count
  else
    ans << "3"
    three += 1
  end
end

puts ans.join
0