C - AtCoderプログラミング講座

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

問題文

AtCoder社では、優秀な競技プログラマーの講座動画を N 個配信しています。初心者競技プログラマーの高橋くんは、AtCoder社が配信している動画を見て修練しようとしています。高橋くんの実力はレートという実数値で表され、レートが高いほど実力が高いことを表します。

高橋くんのレートが C の時に、レート R の競技プログラマーの講座動画を見ると、高橋くんのレートは (C+R)⁄2 に変化します。高橋くんは、講座動画を合計で K 個まで好きな順番で見ることができますが、同じ競技プログラマーの講座動画は一度までしか見ることができません。講座動画を配信している N 人のレートが与えられた時、高橋くんが講座動画を見ることによって達成できるレートの最大値を求めるプログラムを書いてください。ただし、高橋くんの初期レートは 0 です。

#include <iostream>
#include <vector>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    vector<double> nums;
    double ans = 0.0000000;

    for (int i = 0; i < n; ++i)
    {
        double tmp;
        cin >> tmp;
        nums.push_back(tmp);
    }

    std::sort(nums.begin(), nums.end());

    for (int i = n-k; i < n; ++i)
    {
        ans = (ans + nums[i]) / 2.0000000;
    }

    printf("%.6f\n", ans );

}

D - AtCoder社の冬

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

問題文

AtCoder社の社員室は R×C（R 行 C 列）の区画に区切られており、各区画には、社員のデスク、サーバーラックのどちらかがあるか、何もない空きスペースのどれかです。 AtCoder社のある地域の冬は寒く、暖房代をできるだけ節約するため、社員室の必要なスペースのみを区切って使用することに決めました。しかし、資材の問題で、区画に平行な長方形の領域で区切らなければいけません。そこで、デスク、または、サーバーラックのある最も上の行のすぐ上、デスク、または、サーバーラックのある最も下の行のすぐ下、デスク、または、サーバーラックのある最も左の列のすぐ左、デスク、または、サーバーラックのある最も右の列のすぐ右の 4 辺で囲まれた区画を壁で囲みました。すると壁で囲まれた領域は X×Y（X 行 Y 列）の区画になりました。また、AtCoder社の社員室には、D 個のデスクと、L 個のサーバーラックがあります。もともと、社員室に、どのようにデスクとサーバーラックの配置されていたのか、考えうるパターン数を 1000000007=109+7 で割った余りを求めるプログラムを書いてください。

Note

フェルマーの小定理か、パスカルの三角形つかってコンビネーションもとめる。 bit操作と、動的計画法でとける.　次元削減のために捨てれる空間はすてた。

#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long

const ll MOD = 1e9+7;
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 nCk(ll n, ll k){
    int C[30 * 30 + 2];
    int tmp[30 * 30 + 2];
    Fill(C, 0);
    Fill(tmp, 0);
    C[0] = 1;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j <= i+1; ++j)
        {
            tmp[j] = C[j];
        }
        for (int j = 0; j <= i+1; ++j)
        {
            C[j+1] += tmp[j];
            C[j+1] %= MOD;

        }
    }
    C[k] %= MOD;
    return C[k];
}

int main(){
    int r, c, x, y, d, l;
    cin >> r >> c;
    cin >> x >> y;
    cin >> d >> l;

    // ll  dp[30 * 30 + 1][30 * 30 + 1][1 << 4];
    //次元を減らす
    int dp[30 * 30 + 2][(1 << 4)];

    Fill(dp, 0);
    dp[0][0] = 1;

    int dp2[30 * 30 + 2][(1 << 4)];
    Fill(dp2, 0);

    for (int i = 0; i < x * y ; ++i)
    {
        for (int j = 0; j <= d + l ; ++j)
        {
            for (int k = 0; k < (1 << 4); ++k)
            {
                // 上の列
                int bit = k;
                if(i < x){
                    bit |= 1 ;
                }
                // 左の列
                if(i%x == 0){
                    bit |= 1 << 1;
                }
                //右の列
                if(i%x == x-1){
                    bit |= 1 << 2;

                }
                //下の列
                if(i >= x * (y - 1)){
                    bit |= 1 << 3;
                } 
                dp2[j][k] += dp[j][k];
                dp2[j][k] %= MOD;
                dp2[j+1][bit] += dp[j][k];
                dp2[j+1][bit] %= MOD;
            }
        }
        for (int j = 0; j <= d + l ; ++j)
        {
            for (int k = 0; k < (1 << 4); ++k)
            {
                dp[j][k] = dp2[j][k];
                // cout << dp[j][k] << " ";
                dp2[j][k] = 0;
            }
            // cout << endl;
        }
    }

    ll ans = dp[d + l][(1 << 4) -1] % MOD;

    // cout << dp[d + l][(1 << 4) -1] << endl;
    // cout << (r - x + 1) * (c - y + 1) << endl;
    cout << (r - x + 1) * (c - y + 1) % MOD * dp[d + l][(1 << 4) -1] % MOD * nCk(d+l, min(d, l) ) % MOD << endl;
    // cout << nCk(d+l, d) % MOD << endl;   

}

TakefumiYamamura / programming_contest

AtCoder Beginner Contest 003 #24

C - AtCoderプログラミング講座

問題文

D - AtCoder社の冬

問題文

Note