Submission #60443297

Source Code Expand

DEBUG = (ENV['ATCODER'] != '1')
# Disable the method because too often arrays were mistakenly used in the dfs cache.
class Array
  undef_method :member?
end
PACK_SIZE, RARE_CARD_BORDER = gets.split.map!(&:to_i)
PACK = gets.split.map!(&:to_i)
# パック一個を丸ごとダイス扱いして、どの目がどの確率で出るか配るdp
dice_dp = [1]
PACK.each do |hit_percentage|
  new_dice_dp = Array.new(dice_dp.size + 1, 0.0)
  hit_probability = hit_percentage / 100.0
  dice_dp.each_with_index do |v, i|
    new_dice_dp[i + 1] += v * hit_probability
    new_dice_dp[i] += v * (1 - hit_probability)
  end
  dice_dp = new_dice_dp
end
p dice_dp if DEBUG
# 0の目が出る確率
DICE_DP_FIRST = dice_dp.shift
# 1以上の目が出るまでの投擲回数の期待値
NOT_ZERO_EXPECTED = 1.0 / (1 - DICE_DP_FIRST)
# 0の目を消して、その分他の目の確率を上げて確率合計を1になるよう整える
recast_dice_dp = dice_dp.map { |v| v * NOT_ZERO_EXPECTED }
# レアカードがi枚足りなくなるまでに必要な投擲の期待値
rare_card_shortage_dp = Array.new(RARE_CARD_BORDER + 1 + PACK_SIZE, 0)

p recast_dice_dp.to_a if DEBUG
p rare_card_shortage_dp.to_a if DEBUG
# もらうdp
(RARE_CARD_BORDER - 1).downto(0) do |i|
  rare_card_shortage_dp[i] =
    # 1以上の目が出るまで投げると、
    NOT_ZERO_EXPECTED +
    # (i+x)枚足りない状況になるまでの期待値 * ダイスでxの目が出る確率
    # rare_card_shortage_dp[(i + 1)..(i + PACK_SIZE)].mulsum(recast_dice_dp)
    rare_card_shortage_dp[(i + 1)..(i + PACK_SIZE)].zip(recast_dice_dp).sum { |a, b| a * b }
  p rare_card_shortage_dp.to_a if DEBUG
end
# 不足0枚の期待値
puts rare_card_shortage_dp[0]

Submission Info

Submission Time
Task E - Expansion Packs
User HalMat
Language Ruby (ruby 3.2.2)
Score 0
Code Size 1766 Byte
Status TLE
Exec Time 2213 ms
Memory 88072 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 475
Status
AC × 3
AC × 22
TLE × 13
Set Name Test Cases
Sample sample00.txt, sample01.txt, sample02.txt
All sample00.txt, sample01.txt, sample02.txt, testcase00.txt, testcase01.txt, testcase02.txt, testcase03.txt, testcase04.txt, testcase05.txt, testcase06.txt, testcase07.txt, testcase08.txt, testcase09.txt, testcase10.txt, testcase11.txt, testcase12.txt, testcase13.txt, testcase14.txt, testcase15.txt, testcase16.txt, testcase17.txt, testcase18.txt, testcase19.txt, testcase20.txt, testcase21.txt, testcase22.txt, testcase23.txt, testcase24.txt, testcase25.txt, testcase26.txt, testcase27.txt, testcase28.txt, testcase29.txt, testcase30.txt, testcase31.txt
Case Name Status Exec Time Memory
sample00.txt AC 44 ms 17040 KiB
sample01.txt AC 44 ms 17196 KiB
sample02.txt AC 44 ms 17152 KiB
testcase00.txt TLE 2213 ms 75888 KiB
testcase01.txt AC 46 ms 17520 KiB
testcase02.txt AC 1087 ms 88072 KiB
testcase03.txt AC 44 ms 17316 KiB
testcase04.txt TLE 2209 ms 21980 KiB
testcase05.txt AC 46 ms 17432 KiB
testcase06.txt AC 1267 ms 21852 KiB
testcase07.txt AC 44 ms 17212 KiB
testcase08.txt AC 1660 ms 19892 KiB
testcase09.txt TLE 2208 ms 20052 KiB
testcase10.txt TLE 2133 ms 19816 KiB
testcase11.txt AC 1995 ms 19616 KiB
testcase12.txt AC 86 ms 23780 KiB
testcase13.txt AC 72 ms 34404 KiB
testcase14.txt AC 83 ms 23544 KiB
testcase15.txt AC 73 ms 29240 KiB
testcase16.txt AC 77 ms 26912 KiB
testcase17.txt TLE 2209 ms 20688 KiB
testcase18.txt AC 72 ms 35100 KiB
testcase19.txt TLE 2209 ms 20920 KiB
testcase20.txt AC 75 ms 18452 KiB
testcase21.txt TLE 2208 ms 19888 KiB
testcase22.txt AC 917 ms 19160 KiB
testcase23.txt TLE 2208 ms 19588 KiB
testcase24.txt AC 854 ms 19064 KiB
testcase25.txt TLE 2209 ms 19836 KiB
testcase26.txt AC 278 ms 19112 KiB
testcase27.txt TLE 2208 ms 19744 KiB
testcase28.txt TLE 2208 ms 19744 KiB
testcase29.txt TLE 2208 ms 19940 KiB
testcase30.txt AC 1053 ms 19452 KiB
testcase31.txt TLE 2208 ms 19776 KiB