結果

問題 No.295 hel__world
ユーザー te-shte-sh
提出日時 2018-02-01 14:52:24
言語 D
(dmd 2.106.1)
結果
WA  
実行時間 -
コード長 1,693 bytes
コンパイル時間 10,801 ms
コンパイル使用メモリ 671,376 KB
実行使用メモリ 16,296 KB
最終ジャッジ日時 2023-09-03 18:31:16
合計ジャッジ時間 21,563 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,352 KB
testcase_01 AC 2 ms
4,360 KB
testcase_02 AC 2 ms
4,352 KB
testcase_03 AC 2 ms
4,356 KB
testcase_04 AC 2 ms
4,352 KB
testcase_05 WA -
testcase_06 AC 2 ms
4,356 KB
testcase_07 AC 2 ms
4,356 KB
testcase_08 AC 2 ms
4,356 KB
testcase_09 AC 2 ms
4,352 KB
testcase_10 AC 2 ms
4,356 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 2 ms
4,352 KB
testcase_14 AC 2 ms
4,352 KB
testcase_15 AC 1 ms
4,352 KB
testcase_16 AC 2 ms
4,352 KB
testcase_17 AC 2 ms
4,352 KB
testcase_18 AC 2 ms
4,352 KB
testcase_19 AC 2 ms
4,360 KB
testcase_20 AC 2 ms
4,352 KB
testcase_21 AC 3 ms
4,356 KB
testcase_22 AC 3 ms
4,352 KB
testcase_23 AC 2 ms
4,352 KB
testcase_24 WA -
testcase_25 AC 5 ms
4,352 KB
testcase_26 AC 8 ms
4,568 KB
testcase_27 AC 3,201 ms
4,524 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 # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.container; // SList, DList, BinaryHeap
import std.bigint;    // BigInt
import std.regex;     // Regex

void readV(T...)(ref T t){auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(typeof(v));r.popFront;}}
T[] readArray(T)(size_t n){auto a=new T[](n),r=readln.splitter;foreach(ref v;a){v=r.front.to!T;r.popFront;}return a;}
T[] readArrayM(T)(size_t n){auto a=new T[](n);foreach(ref v;a)v=readln.chomp.to!T;return a;}

const inf = BigInt(1L<<62);

void main()
{
  auto s = readArray!long(26);
  string t; readV(t);

  auto d = BigInt(1);
  foreach (i, si; s) {
    d *= calc(BigInt(si), t, cast(char)('a'+i));
    if (d >= inf) {
      writeln("hel");
      return;
    }
  }

  writeln(d);
}

auto calc(BigInt s, string t, char c)
{
  auto y = t.matchAll(regex(c.to!string ~ '+')).map!((m) => m[0].length.to!int).array;
  auto ny = y.length.to!int;
  if (y.empty || s < y.sum) return BigInt(1);

  if (s > 10^^7) {
    if (ny == 1) {
      if (y[0] == 1) return s;
      if (y[0] == 2) return s*(s-1)/2;
    } else if (ny == 2) {
      if (y[0] == 1 && y[1] == 1) return s/2*(s-s/2);
    }
    return inf;
  }

  auto r = new Rat[](ny);
  foreach (i, yi; y)
    r[i] = Rat(BigInt(yi+1), BigInt(1), yi+1, yi);

  auto h = heapify(r), d = BigInt(1);
  foreach (i; 0..(s-y.sum).to!int) {
    auto ri = h.front;
    d = d * ri.num / ri.den;
    if (d >= inf) return inf;
    h.replaceFront(Rat(BigInt(ri.n+1), BigInt(ri.n+1-ri.r), ri.n+1, ri.r));
  }

  return d;
}

struct Rat
{
  BigInt num, den;
  int n, r;

  auto opCmp(Rat b)
  {
    auto c = num*b.den - b.num*den;
    return c == 0 ? 0 : c < 0 ? -1 : 1;
  }
}
0