結果

問題 No.295 hel__world
ユーザー Min_25Min_25
提出日時 2017-05-04 20:40:19
言語 PyPy2
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,308 bytes
コンパイル時間 1,449 ms
コンパイル使用メモリ 76,672 KB
実行使用メモリ 90,616 KB
最終ジャッジ日時 2024-09-14 07:15:16
合計ジャッジ時間 12,561 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 112 ms
78,848 KB
testcase_01 AC 109 ms
78,464 KB
testcase_02 AC 172 ms
81,536 KB
testcase_03 AC 110 ms
78,592 KB
testcase_04 AC 111 ms
78,464 KB
testcase_05 AC 111 ms
78,464 KB
testcase_06 AC 112 ms
78,976 KB
testcase_07 AC 111 ms
78,592 KB
testcase_08 AC 110 ms
79,104 KB
testcase_09 AC 110 ms
78,720 KB
testcase_10 AC 110 ms
78,336 KB
testcase_11 AC 109 ms
78,464 KB
testcase_12 AC 110 ms
78,336 KB
testcase_13 AC 148 ms
80,512 KB
testcase_14 AC 151 ms
80,896 KB
testcase_15 AC 111 ms
78,592 KB
testcase_16 AC 112 ms
78,720 KB
testcase_17 AC 112 ms
78,336 KB
testcase_18 AC 112 ms
78,592 KB
testcase_19 AC 109 ms
78,592 KB
testcase_20 AC 110 ms
78,592 KB
testcase_21 AC 109 ms
78,976 KB
testcase_22 AC 109 ms
78,976 KB
testcase_23 AC 110 ms
78,592 KB
testcase_24 AC 109 ms
78,336 KB
testcase_25 AC 256 ms
81,792 KB
testcase_26 AC 212 ms
81,408 KB
testcase_27 AC 108 ms
78,592 KB
testcase_28 TLE -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
testcase_53 -- -
testcase_54 -- -
testcase_55 -- -
testcase_56 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
import sys

def solve():
  input = sys.stdin.readline

  lim = 2 ** 62
  pre_size = 500

  bin_table = [[1]]
  for i in range(1, pre_size):
    t = [1] * (i + 1)
    p = bin_table[-1]
    for j in range(1, i):
      t[j] = min(lim, p[j - 1] + p[j])
    bin_table += [t]

  def binom(n, k):
    assert(0 <= k and k <= n)
    if n < pre_size:
      return bin_table[n][k]
    ret = 1
    for i in range(k):
      ret = ret * (n - i) // (i + 1)
      if ret >= lim: return lim
    return ret

  def estimate(rest, now, lens, cumu):
    n = len(lens) - now
    needed = lens[now] + cumu[now]
    q, r = divmod(rest - needed, n)
    ret = 1
    for i in range(n):
      ret *= binom(lens[now + i] + q + (i < r), lens[now + i])
      if ret >= lim: return lim
    return ret

  def rec(rest, now, lens, cumu, memo):
    if now + 1 == len(lens):
      return binom(rest, lens[now])
    if not (rest, now) in memo:
      ret = estimate(rest, now, lens, cumu)
      if ret < lim:
        for i in range(rest - cumu[now], lens[now] - 1, -1):
          cnt = binom(i, lens[now])
          if cnt >= lim: 
            ret = lim
            break
          cnt *= rec(rest - i, now + 1, lens, cumu, memo)
          if cnt >= lim:
            ret = lim
            break
          ret = max(ret, cnt)
      memo[rest, now] = ret
    return memo[rest, now]

  for line in sys.stdin:
    counts = map(int, line.split())
    st = input().rstrip()

    freqs = [0] * 26
    lens = [[] for i in range(26)]
    i = 0
    while i < len(st):
      c = st[i]
      j = i + 1
      while j < len(st) and st[j] == c:
        j += 1
      k = ord(c) - ord("a")
      lens[k] += [j - i]
      freqs[k] += j - i
      i = j

    ans = 0
    for i in range(26):
      if freqs[i] > counts[i]:
        break
    else:
      ans = 1
      for i in range(26):
        if len(lens[i]) > 0:
          lens[i] = sorted(lens[i])
          cumu = [0] + lens[i][:-1]
          for j in range(1, len(cumu)):
            cumu[j] += cumu[j - 1]
          lens[i] = lens[i][::-1]
          cumu = cumu[::-1]
          memo = defaultdict(int)
          cnt = rec(counts[i], 0, lens[i], cumu, memo)
          ans = ans * cnt
          if ans >= lim:
            break
    print(ans if ans < lim else "hel")

solve()
0