#13225 (C++11) No.295 hel__world

提出ソース

結果

問題	No.295 hel__world
ユーザー	shimomire
提出日時	2015-02-18 05:57:25
言語	C++11 (gcc 11.4.0)
結果	TLE
実行時間	-
コード長	4,278 bytes
コンパイル時間	1,444 ms
コンパイル使用メモリ	144,884 KB
実行使用メモリ	15,712 KB
最終ジャッジ日時	2024-06-23 21:03:05
合計ジャッジ時間	9,318 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	1 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	1 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	1 ms 6,940 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	1 ms 6,940 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	1 ms 6,944 KB
testcase_13	AC	1 ms 6,944 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	2 ms 6,944 KB
testcase_17	AC	2 ms 6,944 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	2 ms 6,940 KB
testcase_24	AC	2 ms 6,944 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	2 ms 6,940 KB
testcase_27	AC	1 ms 6,944 KB
testcase_28	AC	2 ms 6,940 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	2 ms 6,940 KB
testcase_31	AC	2 ms 6,940 KB
testcase_32	AC	143 ms 15,712 KB
testcase_33	AC	131 ms 15,712 KB
testcase_34	AC	124 ms 15,584 KB
testcase_35	AC	1 ms 6,944 KB
testcase_36	AC	2 ms 6,944 KB
testcase_37	AC	2 ms 6,944 KB
testcase_38	AC	2 ms 6,940 KB
testcase_39	AC	1 ms 6,940 KB
testcase_40	AC	1 ms 6,940 KB
testcase_41	AC	2 ms 6,940 KB
testcase_42	AC	2 ms 6,940 KB
testcase_43	AC	2 ms 6,944 KB
testcase_44	AC	2 ms 6,944 KB
testcase_45	AC	2 ms 6,940 KB
testcase_46	AC	2 ms 6,940 KB
testcase_47	AC	2 ms 6,940 KB
testcase_48	AC	1 ms 6,940 KB
testcase_49	AC	1 ms 6,944 KB
testcase_50	AC	1 ms 6,940 KB
testcase_51	AC	1 ms 6,944 KB
testcase_52	AC	1 ms 6,940 KB
testcase_53	TLE	-
testcase_54	--	-
testcase_55	--	-
testcase_56	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <cassert>// c
#include <iostream>// io
#include <iomanip>
#include <fstream>
#include <sstream>
#include <vector>// container
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <algorithm>// other
#include <complex>
#include <numeric>
#include <functional>
#include <random>
#include <regex>
using namespace std;

using ll =long long;

#define ALL(c) (begin(c)),(end(c))
#define REP(i,n) FOR(i,0,n)
#define REPr(i,n) FORr(i,0,n)
#define FOR(i,l,r) for(int i=(int)(l);i<(int)(r);++i)
#define FORr(i,l,r) for(int i=(int)(r)-1;i>=(int)(l);--i)
#define EACH(it,o) for(auto it = (o).begin(); it != (o).end(); ++it)
#define IN(l,v,r) ((l)<=(v) && (v)<(r))
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end())
//debug
#define DUMP(x)  cerr << #x << " = " << (x)
#define LINE()    cerr<< " (L" << __LINE__ << ")"


template<typename T,typename U> T pmod(T v,U M){return (v%M+M)%M;}
ll gcd_positive(ll a,ll b) { return b == 0 ? a : gcd_positive(b,a%b); }
ll gcd(ll a,ll b) { return gcd_positive(abs(a), abs(b)); }

// a/b
template<typename T> struct Frac{
	T a,b;
	bool operator <(const Frac& r) const{
		return this->a * r.b < this->b * r.a;
	}
	bool operator > (const Frac& r) const{
		return this->a * r.b > this->b * r.a;
	}
};

bool is_zero_t(map<char,ll>& smap,string& t){
	map<char,ll> tmap;
	for(char c:t)tmap[c]++;
	for(pair<char,ll> sp:tmap){
		char c=sp.first;
		if(smap[c]<tmap[c])return true;
	}
	return false;
}

__int128_t INF =1LL<<62;
ll mult(__int128_t a,__int128_t b){// over flow check
	if(a * b >= INF) throw exception();
	return a * b;
}

// C(N,K)
ll C(ll N,ll K){
	ll v=1;
	for(int i=K-1;i>=0;i--){
		ll d = gcd(N - i,K - i);
		v = mult(v/((K-i)/d),(N-i)/d);
	}
	return v;
}

// :問題
// tmap[c] = {a_1,...,a_n} (sorted)
// smap[c] = x_1 + ... + x_n
// C(x_1,a_1) * ... * C(x_n,a_n) の最大化。

// Δ = smap[c] - Σ tmap[c] とする。(Δ <= 10^18)
// 最低限の割り当てをした後n箇所に均等に分配する方針で割り当てると [Δ/n]^n <= MAX が分かる。
// (1) [Δ/n]^n >= 2^62
//   この場合、明らかに hel
// (2) [Δ/n]^n < 2^62
// 　(2.1) n = 1
// 　　割り当て方は一意で最大値 C(smap[c],a_1)
// 　(2.2) n = 2
// 　　Δ < 2 * (2^31 + 1) + 1
//　　 C(x_1,a_1) * C(x_2,a_2) の最大値を三分探索で求める
//   (2.3) n >= 3
// 　　Δ < n * (2^([62/n]+1)+1) + 1 < 7000000
// 　　Δの上限が小さいので、プライオリティーキューで一個ずつ割り当てていく

ll dfs(vector<pair<ll,int>>& tcs,ll delta,int i){
	if(i>=tcs.size())return 1;
	if(delta ==0)return 1;

	ll len;int c;tie(len,c)=tcs[i];
	ll Mv=0;
	ll l = 0,r = delta+1;
	while(true){
		ll lm=(2*l+r)/3,rm=(l+2*r)/3;

		// c個に均等に分配 
		ll lv=1;
		{
			ll v=1;
			for(int i=0;i<lm%c;i++)v=mult(v,C(lm/c+1+len,len));
			for(int i=lm%c;i<c;i++)v=mult(v,C(lm/c+len,len));
			lv=mult(v,dfs(tcs,delta-lm,i+1));
		}
		ll rv=1;
		{
			ll v=1;
			for(int i=0;i<rm%c;i++)v=mult(v,C(rm/c+1+len,len));
			for(int i=rm%c;i<c;i++)v=mult(v,C(rm/c+len,len));
			rv=mult(v,dfs(tcs,delta-rm,i+1));
		}

		if(lv>rv){
			Mv=max(Mv,lv);
			if(r==rm)break;
			r=rm;
		}else{
			Mv=max(Mv,rv);
			if(l==lm)break;
			l=lm;
		}
	}
	return Mv;
}

int main(){
	cout <<fixed<<setprecision(20);
	cin.tie(0);
	ios::sync_with_stdio(false);

	map<char,ll> smap;string t;
	for(char c='a';c<='z';c++)cin >> smap[c];
	cin >> t;
	
	if(is_zero_t(smap,t)){
		cout << 0 <<endl;return 0;
	}

	//cond: res >= 1
	map<char,vector<ll>> tmap;
	for(int i = 0 ; i< t.size();){
		char c=t[i];int count=0;
		while(i<t.size() && c==t[i]){i++;count++;}
		tmap[c].push_back(count);
	}
	for(pair<char,vector<ll>> tp:tmap)sort(ALL(tmap[tp.first]));
	
	ll res = 1;
	try{
		for(pair<char,vector<ll>> tp:tmap){
			char c=tp.first;vector<ll>& tcs=tp.second;
			ll sc=smap[c];
			ll tc=0;for(int v:tcs)tc+=v;
			ll n = tcs.size();
			ll delta = sc - tc;

			// (1)
			{
				ll v = 1,m = delta / n;
				REP(i,n)v = mult(v,m);
			}

			map<ll,int> tcmap;REP(i,tcs.size())tcmap[tcs[i]]++;
			vector<pair<ll,int>> tcv;for(pair<ll,int> p:tcmap)tcv.push_back(p);
			// (2.2)
			res = mult(res,dfs(tcv,delta,0));
		}
		cout << res <<endl;
	}catch(const exception& e){
		cout << "hel"<<endl;return 0;
		
	}

	return 0;
}

yukicoder

結果

テストケース

ソースコード