結果

問題 No.603 hel__world (2)
ユーザー rickythetarickytheta
提出日時 2017-12-03 14:22:42
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 1,880 bytes
コンパイル時間 72 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 28,544 KB
最終ジャッジ日時 2024-11-28 10:08:30
合計ジャッジ時間 51,838 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 77 ms
18,980 KB
testcase_01 AC 78 ms
28,544 KB
testcase_02 AC 81 ms
19,360 KB
testcase_03 AC 87 ms
18,976 KB
testcase_04 AC 85 ms
19,236 KB
testcase_05 AC 78 ms
19,364 KB
testcase_06 AC 74 ms
19,108 KB
testcase_07 AC 80 ms
18,984 KB
testcase_08 AC 78 ms
19,236 KB
testcase_09 AC 80 ms
18,852 KB
testcase_10 AC 79 ms
19,236 KB
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 AC 81 ms
19,232 KB
testcase_15 WA -
testcase_16 AC 82 ms
18,980 KB
testcase_17 AC 82 ms
19,104 KB
testcase_18 AC 82 ms
19,108 KB
testcase_19 AC 84 ms
18,980 KB
testcase_20 TLE -
testcase_21 TLE -
testcase_22 AC 92 ms
12,416 KB
testcase_23 AC 93 ms
12,288 KB
testcase_24 AC 94 ms
12,416 KB
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 AC 81 ms
12,160 KB
testcase_32 TLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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