結果

問題 No.603 hel__world (2)
ユーザー rickythetarickytheta
提出日時 2017-12-03 14:22:42
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 1,880 bytes
コンパイル時間 460 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 21,632 KB
最終ジャッジ日時 2024-05-06 05:56:22
合計ジャッジ時間 6,666 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 79 ms
17,664 KB
testcase_01 AC 79 ms
12,032 KB
testcase_02 AC 79 ms
12,416 KB
testcase_03 AC 82 ms
12,544 KB
testcase_04 AC 83 ms
12,288 KB
testcase_05 AC 84 ms
12,416 KB
testcase_06 AC 82 ms
12,032 KB
testcase_07 AC 88 ms
12,288 KB
testcase_08 AC 83 ms
12,160 KB
testcase_09 AC 83 ms
12,288 KB
testcase_10 AC 81 ms
12,288 KB
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

MOD = 1000003

def modpow(a,b)
  r = 1
  while b>0
    r = r * a % MOD if b % 2 == 1
    a = a * a % MOD
    b >>= 1
  end
  r
end
def modinv(x)
  modpow(x,MOD-2)
end

def comb(n,k)
  return 0 if k > n
  return 1 if k == n || k == 0
  ret = 1
  for i in 0...k
    ret = ret * (n-i) % MOD
  end
  for i in 1..k
    ret = ret * modinv(i) % MOD
  end
  ret
end

def solve(n,s,t)
  # n : size of t
  # s : max sum
  # t : char count in string T
  return 1 if t.length == 0
  tsum = t.inject(:+)
  return 0 if tsum > s
  return 1 if tsum == s
  # binary search
  la = 1
  lb = 1
  ha = 1048576
  hb = 1
  128.times do
    # get medium
    ta = la*hb + ha*lb
    tb = lb*hb
    if ta % 2 == 0
      ta /= 2
    else
      tb *= 2
    end
    tg = ta.gcd(tb)
    ta /= tg
    tb /= tg
    # calc xs
    xsum = 0
    for i in 0...n
      x = (t[i]*ta + tb - ta) / (ta - tb)
      if x < t[i]
        x = t[i]
      end
      xsum += x
    end
    if xsum <= s
      ha = ta
      hb = tb
    else
      la = ta
      lb = tb
    end
  end
  # (ha, hb) is threshold
  # get max
  maxa = 0
  maxb = 1
  xsum = 0
  for i in 0...n
    x = (t[i]*ha + hb - ha) / (ha - hb)
    xsum += x
    xa = x+1
    xb = x+1-t[i]
    if xa*maxb > maxa*xb
      maxa = xa
      maxb = xb
    end
  end
  # calc ans
  rest = s - xsum
  ans = 1
  for i in 0...n
    x = (t[i]*ha + hb - ha) / (ha - hb)
    xa = x+1
    xb = x+1-t[i]
    if xa*maxb == maxa*xb && rest > 0
      x += 1
      rest -= 1
    end
    ans = ans * comb(x,t[i]) % MOD
  end
  return ans
end

s = gets.chomp.split(" ").map(&:to_i)
t = "$" + gets.chomp + "$"
ans = 1
for i in 0...26
  c = (i + "a".ord).chr
  ts = []
  cnt = 0
  for j in 0...t.length
    if t[j] != c
      if cnt > 0
        ts.push(cnt)
      end
      cnt = 0
    else
      cnt += 1
    end
  end
  x = solve(ts.length, s[i], ts)
  ans = ans * x % MOD
end
puts ans
0