SRM626

久しぶりのC++過ぎて頭からC++の仕様がすっ飛んでいます。 やはり、C++といえど、仕様をまとめた自分用チートシートをつくらないといけませんね

250

ほんとにC++?と疑うようなコードです。 いちいち配列0埋めしてるし、まあいいけど。

#include <cstring>
class FixedDiceGameDiv1
{
public:
    double getExpectation(int a, int b, int c, int d) {
        if(a*b<=c)return -1.0;
        double dp[2501][2];//this is not dp
        for(int i=0; i<2501; i++)
            for(int j=0; j<2; j++)
                dp[i][j]=0;
        auto makedp=[&](int a, int b, int tar) {
            double tempdp[2501][2];
            for(int i=0; i<2501; i++)
                for(int j=0; j<2; j++)
                    tempdp[i][j]=0;
            int point=0;
            tempdp[0][0]=1;
            for(int pa=0; pa<a; pa++){
                for(int pb=1; pb<=b; pb++){
                    for(int i=0; i<=a*b; i++){
                        tempdp[i+pb][1-point]+=tempdp[i][point];
                    }
                }
                point=1-point;
                for(int i=0; i<2501; i++)
                    tempdp[i][1-point]=0;
            }
            for(int i=0; i<2501; i++)
                dp[i][tar]=tempdp[i][point];
        };
        makedp(a, b, 0);
        makedp(c, d, 1);
        double sum=0;
        double cnt=0;
        for(int pa=0; pa<2501; pa++){
            for(int pb=0; pb<pa; pb++){
                sum+=pa*dp[pa][0]*dp[pb][1];
                cnt+=dp[pa][0]*dp[pb][1];
            }
        }
        return (double)sum/(double)cnt;
    }
};

600

これに時間が残っていれば解けたであろうLevel2

一瞬1000000000*50nodesのグラフの最短路問題かと思ったがもちろんそんなの無理

これは、行列の高速２乗法で解きます。

Mat_x,y=xからyへのコスト

積Mat1*Mat2_x,y=min(zがnode) Mat1_x,z + Mat2_z,y

和Mat1+Mat2_x,y=min (Mat1_x,y , Mat2_x,y)

と行列演算を定義

Dist_x,y=min(from=x_i to=y_i) weight_i 無かったら無限大

Base=Dist+Dist²+Dist³+..+Dist~N

Nbase_x,y=min(from=x_i to=y_i) -weight_i 無かったら無限大

Cost_1=BaseNbaseBase

Cose_2n=Cost_n*Cost_n

で高速冪乗法を使ってCost_chargesを求めて、

答えはCost_charges_1,N

追記

っていうか600の問題はtropical mathematicsじゃん

追記2

誤字つらい

追記3

Baseはワーシャルフロイド使うかN乗するかしてならしとかないと