結果

問題 No.294 SuperFizzBuzz
ユーザー code-devocode-devo
提出日時 2016-03-05 13:19:51
言語 Ruby
(3.3.0)
結果
AC  
実行時間 85 ms / 5,000 ms
コード長 1,434 bytes
コンパイル時間 226 ms
コンパイル使用メモリ 11,524 KB
実行使用メモリ 15,304 KB
最終ジャッジ日時 2023-08-27 01:33:43
合計ジャッジ時間 2,340 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 78 ms
15,056 KB
testcase_01 AC 85 ms
15,116 KB
testcase_02 AC 78 ms
15,052 KB
testcase_03 AC 79 ms
15,116 KB
testcase_04 AC 77 ms
15,120 KB
testcase_05 AC 75 ms
15,264 KB
testcase_06 AC 78 ms
15,060 KB
testcase_07 AC 76 ms
15,124 KB
testcase_08 AC 75 ms
15,224 KB
testcase_09 AC 77 ms
15,008 KB
testcase_10 AC 76 ms
15,244 KB
testcase_11 AC 77 ms
15,304 KB
testcase_12 AC 75 ms
15,236 KB
testcase_13 AC 78 ms
15,060 KB
testcase_14 AC 79 ms
15,208 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