結果
問題 | No.295 hel__world |
ユーザー | te-sh |
提出日時 | 2018-02-01 15:33:27 |
言語 | D (dmd 2.109.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,802 bytes |
コンパイル時間 | 8,529 ms |
コンパイル使用メモリ | 326,796 KB |
実行使用メモリ | 18,492 KB |
最終ジャッジ日時 | 2024-06-12 23:46:10 |
合計ジャッジ時間 | 17,787 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 3 |
other | AC * 27 WA * 26 |
ソースコード
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 y = new int[][](26); foreach (i; 0..26) { auto c = cast(char)('a'+i); y[i] = t.matchAll(regex(c.to!string ~ '+')).map!((m) => m[0].length.to!int).array; if (s[i] < y[i].sum) { writeln(0); return; } } auto d = BigInt(1); foreach (i, si; s) { d = calc(BigInt(si), t, y[i], d); if (d >= inf) { writeln("hel"); return; } } writeln(d); } auto calc(BigInt s, string t, int[] y, BigInt d) { auto ny = y.length.to!int; if (y.empty) return BigInt(1); if (s > 10^^7) { if (ny == 1) { if (y[0] == 1) return d*s; if (y[0] == 2) return d*s*(s-1)/2; } else if (ny == 2) { if (y[0] == 1 && y[1] == 1) return d*s/2*(s-s/2); } return inf; } auto r = new Rat[](ny); foreach (i, yi; y) r[i] = Rat(yi+1, yi); auto h = heapify(r); foreach (i; 0..(s-y.sum).to!int) { auto ri = h.front; d = d * ri.n / (ri.n-ri.r); if (d >= inf) return inf; h.replaceFront(Rat(ri.n+1, ri.r)); } return d; } struct Rat { long n, r; auto opCmp(Rat b) { auto num = n, den = n-r, bnum = b.n, bden = b.n-b.r; auto c = num*bden - den*bnum; return c == 0 ? 0 : c < 0 ? -1 : 1; } }