SRM642-644 Div1E

45問目まで来たよ

 ・SRM642 Div1E WaitingForBus

n台のバスがある.ランダムに選ばれた1台のバスが時刻0にバスターミナルを出る.バスターミナルを出たバスが帰ってきたと同時にまたランダムに選ばれた1台のバスが出る,ということが繰り返される.i番目のバスが選ばれる確率はprob[i]/100で,バスターミナルを出てから帰ってくるまでの時間はtime[i]である.このとき,時刻sにやってきた人が,次のバスに乗るまでの待ち時間の期待値を求めよ,という問題.

待ち時間がtである,すなわち,はじめてバスが帰ってくるのが時刻s+tである確率を求めたい.時刻s+tに帰ってくるバスがi番目のバスであるのは,時刻s+t-time[i]にバスが帰ってきて,次のバスに選ばれたのがi番目のバスであるとき(ただしtime[i]<tのときは時刻s+tより前に帰ってくるバスが存在することになるのでダメ).よって時刻xにバスが帰ってくる確率が求まっていれば,求めたい確率がわかる.これはDPで計算できるので終わり.

ソースコード

double dp[200001];
class WaitingForBus {
    public:
    
    double whenWillBusArrive(vector<int> time, vector<int> prob, int s) {
        int n=time.size();
        dp[0]=1;
        for(int i=1;i<=200000;i++) {
            for(int j=0;j<n;j++) {
                if(time[j]>i) continue;
                dp[i]+=dp[i-time[j]]*prob[j]/100;
            }
        }
        double ans=0;
        for(int i=0;i<100000;i++) {
            for(int j=0;j<n;j++) {
                if(i>=time[j]||s+i<time[j]) continue;
                ans+=i*dp[s+i-time[j]]*prob[j]/100;
            }
        }
        return ans;
    }
};

・SRM643 Div1E TheKingsFactorization

N(1≦N≦10^18)の素因数分解せよ.ただしヒントとして,素因数分解したときに出てくる素因数を昇順に並べたときの奇数番目の要素が与えられる(例えばN=60なら素因数のリストは{2,2,3,5}となるので{2,3}が与えられる).

N≦10^18ということは10^7以上の巨大な素因数というのは高々2個しか現れない.そこで,まず10^7未満の素数を列挙してNを割れるだけ割っていくことで10^7未満の素因数を列挙する.この時点でNが1になっていれば終了.そうでないときは,Nが10^7以上の素数であるか,10^7以上の素数2つの積になっている.後者の場合,ヒントとして片方の素数が与えられるはずであるから,リストの末尾の数でNが割れるかどうかを調べればどちらの場合かがわかるので,とけた.

ソースコード

bool is_prime[10000001];
class TheKingsFactorization {
    public:
    vector<long long> getVector(long long N, vector<long long> primes) {
        memset(is_prime,-1,sizeof(is_prime));
        sort(primes.begin(),primes.end());
        for(int i=2;i<=10000000;i++) {
            if(!is_prime[i]) continue;
            for(int j=i*2;j<=10000000;j+=i) is_prime[j]=0;
        }
        vector<int> p;
        for(int i=2;i<=10000000;i++) if(is_prime[i]) p.push_back(i);
        vector<long long> ans;
        for(int i=0;i<p.size();i++) {
            while(N%p[i]==0) {
                ans.push_back(p[i]);
                N/=p[i];
            }
        }
        if(N==1) return ans;
        if(N%primes.back()==0) {
            N/=primes.back();
            if(N>1) ans.push_back(N);
            ans.push_back(primes.back());
            sort(ans.begin(),ans.end());
        }else {
            ans.push_back(N);
        }
        return ans;
    }
};

SRM644 Div1E OkonomiyakiParty

N個のおこのみやきがあり,i番目のおこのみやきの大きさはosize[i]である.今,最小のおこのみやきと最大のおこのみやきの大きさの差がK以下となるよう,ちょうどM個のおこのみやきを選びたい.選び方は何通りあるか.

osizeをソートしておき,i番目+i番目よりうしろのおこのみやきからM-1個選ぶときの選び方を計算することをかんがえる.こうすると,最小のおこのみやきの大きさが固定されていることから最大で何番目のおこのみやきまで選べるかがにぶたんで簡単に求まる.また,i番目のおこのみやきと同じ大きさのおこのみやきがあったとしても重複して数え上げることがない.あとは,候補のおこのみやきがK個あったとするとK個からM-1個選ぶ方法の数がわかればいいので普通に組合せを計算してあげると終わり.

ソースコード

const int MOD=1000000007;
int comb[51][51];
class OkonomiyakiParty {
    public:
    int count(vector<int> osize, int M, int K) {
        comb[0][0]=1;
        for(int i=1;i<=50;i++) {
            comb[i][0]=comb[i][i]=1;
            for(int j=1;j<i;j++) {
                (comb[i][j]+=comb[i-1][j])%=MOD;
                (comb[i][j]+=comb[i-1][j-1])%=MOD;
            }
        }
        sort(osize.begin(),osize.end());
        int ans=0;
        for(int i=0;i<osize.size();i++) {
            int j=upper_bound(osize.begin(),osize.end(),osize[i]+K)-osize.begin();
            if(j-i<M) continue;
            (ans+=comb[j-i-1][M-1])%=MOD;
        }
        return ans;
    }
};