結果

問題 No.295 hel__world
ユーザー shimomire
提出日時 2015-02-18 05:54:44
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 764 ms / 5,000 ms
コード長 4,490 bytes
コンパイル時間 1,432 ms
コンパイル使用メモリ 141,544 KB
実行使用メモリ 17,936 KB
最終ジャッジ日時 2024-06-23 21:02:47
合計ジャッジ時間 4,689 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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
// 　　Δの上限が小さいので、プライオリティーキューで一個ずつ割り当てていく
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);
            }
            if(n==1){
                // (2.1)
                // C(sc,tc)
                res = mult(res,C(sc,tc));
            }else if (n == 2){
                // (2.2)
                // C(x,a_1) * C(S - x,a_2)
                ll Mv=0;
                ll l = tcs[0],r = sc - tcs[1] + 1;
                while(true){
                    ll lm=(2*l+r)/3,rm=(l+2*r)/3;
                    ll lv=mult(C(lm,tcs[0]),C(sc-lm,tcs[1])),rv=mult(C(rm,tcs[0]),C(sc-rm,tcs[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;
                    }
                }
                res =mult(res,Mv);
            }else{
                // (2.3)
                // delta < 7000000
                ll v = 1;
                priority_queue<pair<Frac<ll>,int> > que;
                vector<ll> scs(n);REP(i,n)scs[i]=tcs[i];
                REP(i,scs.size()){
                    Frac<ll> fr={scs[i]+1,scs[i]+1 - tcs[i]};
                    que.push(make_pair(Frac<ll>(fr),i));
                }
                while(!que.empty() && delta >0){
                    auto p = que.top();que.pop();
                    ll a = p.first.a,b = p.first.b;int i = p.second;
                    ll d = gcd(a,b);
                    v = mult(v/(b/d),a/d);
                    scs[i]++;delta--;
                    Frac<ll> fr={scs[i]+1,scs[i]+1 - tcs[i]};
                    que.push(make_pair(Frac<ll>(fr),i));
                }
                res =mult(res,v);
            }
        }
        cout << res <<endl;
    }catch(const exception& e){
        cout << "hel"<<endl;return 0;
        
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0