結果

問題 No.295 hel__world
ユーザー Min_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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 24 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

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