結果

問題 No.294 SuperFizzBuzz
ユーザー code-devocode-devo
提出日時 2016-03-05 13:19:51
言語 Ruby
(3.3.0)
結果
AC  
実行時間 90 ms / 5,000 ms
コード長 1,434 bytes
コンパイル時間 50 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 12,416 KB
最終ジャッジ日時 2024-06-07 20:48:47
合計ジャッジ時間 2,233 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 88 ms
12,160 KB
testcase_01 AC 83 ms
12,160 KB
testcase_02 AC 85 ms
12,160 KB
testcase_03 AC 89 ms
12,160 KB
testcase_04 AC 87 ms
12,160 KB
testcase_05 AC 82 ms
12,288 KB
testcase_06 AC 88 ms
12,288 KB
testcase_07 AC 86 ms
12,416 KB
testcase_08 AC 87 ms
12,160 KB
testcase_09 AC 90 ms
12,288 KB
testcase_10 AC 83 ms
12,288 KB
testcase_11 AC 84 ms
12,160 KB
testcase_12 AC 84 ms
12,160 KB
testcase_13 AC 84 ms
12,288 KB
testcase_14 AC 86 ms
12,416 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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