TakefumiYamamura commented 8 years ago

C - 列

Time limit : 2sec / Memory limit : 256MB

問題文

長さ N の非負整数列 S=s1,s2,…,sN と整数 K があります。あなたの仕事は、以下の条件を満たす S の連続する部分列のうち、最も長いものの長さを求めることです。部分列の長さは 1 以上の列でないといけません。

その部分列に含まれる全ての要素の値の積は、K 以下である。もし条件を満たす部分列が一つも存在しないときは、0 を出力してください。

Note

典型的なしゃくとり法で解けます　http://d.hatena.ne.jp/komiyam/20120802/1343894601

#include <iostream>
#include <algorithm> 

#define ulli unsigned long long int
using namespace std;

ulli N;
ulli K;
ulli s[100001];

int main(){
    cin >> N >> K;

    for (int i = 0; i < N; ++i)
    {
        cin >> s[i];
        if (s[i] == 0){
            cout << N << endl;
            return 0;
        } 
    }

    int first, last;
    first = 0;
    last = -1;
    ulli mul = 1;
    int ans = 0;

    for (int last = 0; last < N; ++last)
    {
        mul *= s[last];
        while(mul > K && first <= last){
            mul /= s[first];
            first++;
        }
        ans = max(ans, last - first + 1);

    }

    cout << ans << endl;
    return 0;

}

TakefumiYamamura commented 8 years ago

D - ナップサック問題

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

問題文

0/1ナップサック問題を解いてください。0/1ナップサック問題とは以下のような問題のことです。

N 個の荷物があり、i(1≦i≦N) 番目の荷物には価値 vi と重さ wi が割り当てられている。許容重量 W のナップサックが1つある。重さの和が W 以下となるように荷物の集合を選びナップサックに詰め込むとき、価値の和の最大値を求めよ。ただし、同じ荷物は一度しか選ぶことができない。

note

サイズによってアルゴリズムを使い分ける必要あり。蟻本に解法がありまふ。

半分全列挙 -> p148 w[i] <= 1000 (一番シンプルなやつ) -> p52 v[i] <= 1000 -> p60

シンプルなdp、これだと33点しか取れない(w[i] <= 1000 の時だけ解答可能)

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

using namespace std;

int N, W;
long long v[201];
long long w[201];
long long ans = 0;
vector<vector<long long> > dp;

int main(){
    cin >> N >> W;
    v[0] = 0;
    w[0] = 0;
    for (int i = 1; i <= N; ++i)
    {
        cin >> v[i] >> w[i];
    }

    dp = vector<vector<long long> >(N+1, vector<long long>(W+1, 0));

    for (int i = 1; i <= N; ++i)
    {
        dp[i][0] = 0;
    }
    for (int i = 0; i <= W; ++i)
    {
        dp[0][i] = 0;
    }

    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= W; ++j)
        {
            if(j - w[i] >= 0){
                dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i-1][j]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << endl;

}

この後がものすごく長かった、、、、つまずいたポイント

INFが小さいとtestcase5で落ちる
v が 1000以下caseは後ろからdpやって空間的計算量を減らさないと、メモリ足らなくなる

ちなみに計算量のオーダーは半分全列挙 -> O(n_2^(n/2) ) = 30_32768 = 10^5 (2_30　が10桁だからい感じで全列挙だと間に合わない) w[i] <= 1000 (一番シンプルなやつ) -> O(NW) = 200 * 1000 = 10^5 v[i] <= 1000 -> p60 ->O(NVmax)=O(N_NV) = 200 * 200 *1000 = 10^7

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
//INFが小さいとtestcase5で落ちる
#define INF (long long)30000000005
#define ll long long
using namespace std;

int N, W;
ll v[201];
ll v_max = 0; 
ll w[201];
ll ans = 0;

void compute_low_n(){
    //wとvが大きすぎるがnが小さいので半分全列挙で解く
    pair<ll, ll> ps[1 << 16];
    ll sw, sv;
    // 前半の列挙
    int n2 = N/2;
    if(n2 == 0){
        ans = 0;
        return;
    }
    for (int i = 0; i < 1 << n2; ++i)
    {
        sw = 0;
        sv = 0;
        for (int j = 0; j < n2; ++j)
        {
            if(i >> j & 1){
                sw += w[j+1];
                sv += v[j+1];
            }
        }
        ps[i] = make_pair(sw, sv);
    }

    // 無駄な要素の消去
    sort(ps, ps + (1 << n2));
    int m = 1;
    for (int i = 1; i < (1 << n2); ++i)
    {
        if(ps[i - 1].second < ps[i].second){
            ps[m++] = ps[i];
        }
    }

    //後半の列挙
    for (int i = 0; i < (1 << (N - n2) ); ++i)
    {
        sw = 0;
        sv = 0;
        for (int j = 0; j < N - n2; ++j)
        {
            if(i >> j & 1){
                sw += w[n2 + j + 1];
                sv += v[n2 + j + 1];
            }
        }
        if (W >= sw){
            ans = max(ans, sv + (lower_bound(ps, ps+m, make_pair( W - sw, INF)) - 1)->second );
        }
    }

}

void compute_low_v(){
    //dp[i][j]で管理するものはi番目までの商品を使って価値がjの時の重さの最小値
    vector<ll > dp;
    dp = vector<ll>(v_max+1, 0);
    for (int i = 0; i <= v_max; ++i)
    {
        dp[i]= INF;
    }
    dp[0] = 0;

    for (int i = 1; i <= N; ++i)
    {
        //価値の逆順にめぐって小メモリ化
        for (ll j = v_max; j >= 1; --j)
        {
            if(j - v[i] >= 0 && dp[j - v[i]] + w[i] <= W){
                dp[j] = min(dp[j - v[i]] + w[i], dp[j]);
            }
            if(dp[j] <= W){
                ans = max(ans, j);
            }
        }
    }

}

void compute_low_w(){
    vector<vector<ll> > dp;
    dp = vector<vector<ll> >(N+1, vector<ll>(W+1, 0));
    for (int i = 1; i <= N; ++i)
    {
        dp[i][0] = 0;
    }
    for (int i = 0; i <= W; ++i)
    {
        dp[0][i] = 0;
    }
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= W; ++j)
        {
            if(j - w[i] >= 0){
                dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i-1][j]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
            ans = max(ans, dp[i][j]);
        }
    }
}

int main(){
    cin >> N >> W;
    v[0] = 0;
    w[0] = 0;
    bool flag_v = true;
    bool flag_w = true;
    ll large_v = 0;
    for (int i = 1; i <= N; ++i)
    {
        cin >> v[i] >> w[i];
        large_v = max(large_v, v[i]);
        if(v[i] > 1000) flag_v = false;
        if(w[i] > 1000) flag_w = false;
    }
    if(N <= 30){
        compute_low_n();
    }else if(flag_w){
        compute_low_w();
    }else if(flag_v){
        v_max = large_v * N;
        compute_low_v();
    }
    cout << ans << endl;
}

TakefumiYamamura / programming_contest

AtCoder Beginner Contest 032 #4

C - 列

問題文

Note

D - ナップサック問題

問題文

note