TakefumiYamamura commented 8 years ago

C - 経路

時間制限 : 2sec / メモリ制限 : 256MB

問題文横 W x 縦 H のグリッドがあります。左から i 番目、下から j 番目のマス目には (i,j) という番号がついています。

高橋君は、マス目 (i,j) から (i+1,j) または (i,j+1) に進むことができます。高橋君が (1,1) から (W,H) まで行く経路の個数を 1,000,000,007 で割ったあまりを求めてください。

note

フェルマーの小定理でnCkを出すたけ

#include <iostream>
#define MOD 1000000007
#define ll long long
#define MAX_N 200003
using namespace std;

template<typename A, size_t N, typename T>

void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

ll fac[MAX_N];
ll revfac[MAX_N];

// ll nCk(ll n, ll k){
//  ll array[200001];
//  array[0] = 1;

//  for (int i = 0; i < n; ++i)
//  {
//      ll tmp[200001];
//      Fill(tmp, 0);
//      for (int j = 0; j < i+1; ++j)
//      {
//          tmp[j] += array[j];
//          tmp[j+1] += array[j];
//          tmp[j] %= MOD; tmp[j+1] %= MOD;
//      }

//      for (int j = 0; j <= i+1; ++j)
//      {
//          array[j] = tmp[j];
//          // cout << array[j] << " ";
//      }
//      // cout << endl;
//  }
//  return array[k];
// }

ll nCk(ll n, ll k){
    return fac[n] * revfac[k] % MOD * revfac[n - k] % MOD;
}

ll pow(ll a, ll e){
    ll ans = 1;
    while(e > 0){
        if(e & 1){
            ans *= a;
            ans %= MOD;
        }
        a *= a;
        a %= MOD;
        e = e >> 1;
    }
    return ans % MOD;
}

void set_fac(){
    fac[0] = 1;
    fac[1] = 1;
    revfac[0] = 1;
    for (int i = 1; i < MAX_N; ++i)
    {
        fac[i] = i * fac[i-1] % MOD;
        revfac[i] = pow(fac[i], MOD - 2) % MOD;
    }
}

int main(){
    ll w, h;
    cin >> w >> h;
    set_fac();
    cout << nCk(w + h - 2, w - 1) << endl;
}

TakefumiYamamura commented 8 years ago

D - 食塩水

時間制限 : 2sec / メモリ制限 : 256MB

問題文

食塩水が入った容器が N 個あります。容器には 1 から N までの番号がついています。 i 番の容器には濃度 pi パーセントの食塩水が wi グラム入っています。高橋君は、K 個の容器を選び、選んだ容器の中に入っている食塩水をすべて混ぜ合わせることにしました。高橋君の混ぜた食塩水の濃度として考えられる最大値を求めてください。入力入力は以下の形式で標準入力から与えられる。

K N w1 p1 … wN pN 1≤K,N≤1000 をみたす。 1≤wi≤109 をみたす。 0≤pi≤100 をみたす。出力高橋君の混ぜた食塩水の濃度として考えられる最大値を出力せよ。出力の末尾には改行を入れること。

note

パーセントを初めに決めてしまってそれを二分探索する。初めてのタイプの問題だったお

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct water
{
    double w;
    double p;
};

//決め打ち二分木探索
int main(){
    int k, n;
    vector<water> water_array;
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
    {
        double w, p;
        cin >> w >> p;
        water tmp = {w, p};
        water_array.push_back(tmp);
    }

    double ok = 0.0;
    double ng = 100.0;
    double middle;

    while( (ng - ok) > 1e-12 )
    {
        middle = (ok + ng) / 2.0;
        vector<double> greedy;
        for (int i = 0; i < water_array.size(); ++i)
        {
            greedy.push_back(water_array[i].w * (water_array[i].p - middle)/ 100.0);
        }

        sort(greedy.begin(), greedy.end(), greater<double>() );

        double sum = 0;

        for (int i = 0; i < k; ++i)
        {
            sum += greedy[i];
        }
        // cout << endl;

        if(sum >= 0){
            ok = middle;
        }else{
            ng = middle;
        }
    }

    printf("%.10f\n", middle);
}

TakefumiYamamura / programming_contest

AtCoder Beginner Contest 034 #36

C - 経路

note

D - 食塩水

問題文

note