C++ の動作確認をしてみた（２８）

C++の練習を兼ねて, AtCoder Beginner Contest 060 の問題C（Sentou), 問題D（Simple Knapsack) を解いてみた.

■感想.
1. 問題C は, 解答方針が, 見つかったので, 解答出来た.
2. 問題D は, 解答方針が見えなかったので, 解説を読んでから, その日本語を, プログラムに翻訳したが, なかなか大変だった(コンパクトに纏めることが出来なかった).

本家のサイトAtCoder Regular Contest 073 Editorialをご覧下さい.

■C++版プログラム(問題C／AC版).

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

typedef long long LL;

int main() {
    
    // 1. 入力情報取得.
    LL N, T;
    cin >> N >> T;
    LL totalTime = T;
    
    // 2. お湯の出続ける時間をカウント.
    // 前回スイッチを押した時刻.
    LL bti = 0;
    FOR(i, 0, N) {
        // 今回スイッチを押した時刻.
        LL cti;
        cin >> cti;
        if(cti > bti) totalTime += min(cti - bti, T);
        bti = cti;
    }
    
    // 3. 出力 ～ 後処理.
    cout << totalTime << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

typedef long long LL;

int main() {

// 1. 入力情報取得.

LL N, T;

cin >> N >> T;

LL totalTime = T;

// 2. お湯の出続ける時間をカウント.

// 前回スイッチを押した時刻.

LL bti = 0;

FOR(i, 0, N) {

// 今回スイッチを押した時刻.

LL cti;

cin >> cti;

if(cti > bti) totalTime += min(cti - bti, T);

bti = cti;

}

// 3. 出力～後処理.

cout << totalTime << endl;

return 0;

}

■C++版プログラム(問題D／AC版).

// 解き直し.
// AtCoder Regular Contest 073 Editorial
// https://atcoder.jp/img/arc073/editorial.pdf
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

int main() {

    // 1. 入力情報取得.
    LL N, W;
    cin >> N >> W;
    // 解説通り, 4種類の重さのものを, それぞれ, いくつ選ぶかを把握するために使う.
    vector<LL> v1, v2, v3, v4;
    // w1 記録用.
    LL w1 = 0;
    FOR(i, 0, N) {
        LL wi, vi;
        cin >> wi >> vi;
        if(i == 0) w1 = wi;
        if(wi == w1 + 0) v1.push_back(vi);
        if(wi == w1 + 1) v2.push_back(vi);
        if(wi == w1 + 2) v3.push_back(vi);
        if(wi == w1 + 3) v4.push_back(vi);
    }
    
    // 2. バッグの価値を降順sort.
    sort(v1.begin(), v1.end(), greater<LL>());
    sort(v2.begin(), v2.end(), greater<LL>());
    sort(v3.begin(), v3.end(), greater<LL>());
    sort(v4.begin(), v4.end(), greater<LL>());
    
    // 3. バッグの価値の累積和を作成.
    int l1, l2, l3, l4;
    l1 = v1.size();
    l2 = v2.size();
    l3 = v3.size();
    l4 = v4.size();
    // cout << l1 << " " << l2 << " " << l3 << " " << l4 << endl;
    
    LL a1[l1 + 1] = {};
    LL a2[l2 + 1] = {};
    LL a3[l3 + 1] = {};
    LL a4[l4 + 1] = {};
    a1[1] = (l1 > 0) ? v1[0] : 0;
    a2[1] = (l2 > 0) ? v2[0] : 0;
    a3[1] = (l3 > 0) ? v3[0] : 0;
    a4[1] = (l4 > 0) ? v4[0] : 0;
    FOR(i, 2, l1 + 1) a1[i] += (v1[i - 1] + a1[i - 1]);
    FOR(i, 2, l2 + 1) a2[i] += (v2[i - 1] + a2[i - 1]);
    FOR(i, 2, l3 + 1) a3[i] += (v3[i - 1] + a3[i - 1]);
    FOR(i, 2, l4 + 1) a4[i] += (v4[i - 1] + a4[i - 1]);
    
    // FOR(i, 0, l1 + 1) cout << a1[i] << " ";
    // FOR(i, 0, l2 + 1) cout << a2[i] << " ";
    // FOR(i, 0, l3 + 1) cout << a3[i] << " ";
    // FOR(i, 0, l4 + 1) cout << a4[i] << " ";
    
    // 4. バッグに入れた物の価値の総和を最大化するための試行錯誤.
    LL maxValue = 0;
    FOR(i1, 0, l1 + 1) {
        FOR(i2, 0, l2 + 1) {
            FOR(i3, 0, l3 + 1) {
                FOR(i4, 0, l4 + 1) {
                    // v1 から i1個, v2 から i2個, v3 から i3個, v4 から i4個 選んで,
                    // 重さの和が, W を 超えていたら, スキップ.
                    LL w = w1 * i1 + (w1 + 1) * i2 + (w1 + 2) * i3 + (w1 + 3) * i4;
                    // cout << i1 << " " << i2 << " " << i3 << " " << i4 << " " << w << endl;
                    if(w > W) continue;
                    
                    // 最大値更新.
                    LL v = a1[i1] + a2[i2] + a3[i3] + a4[i4];
                    if(maxValue < v) maxValue = v;
                }
            }
        }
    }
    
    // 5. 出力 ～ 後処理.
    cout << maxValue << endl;
    return 0;
    
}

// 解き直し.

// AtCoder Regular Contest 073 Editorial

// https://atcoder.jp/img/arc073/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

int main() {

// 1. 入力情報取得.

LL N, W;

cin >> N >> W;

// 解説通り, 4種類の重さのものを, それぞれ, いくつ選ぶかを把握するために使う.

vector<LL> v1, v2, v3, v4;

// w1 記録用.

LL w1 = 0;

FOR(i, 0, N) {

LL wi, vi;

cin >> wi >> vi;

if(i == 0) w1 = wi;

if(wi == w1 + 0) v1.push_back(vi);

if(wi == w1 + 1) v2.push_back(vi);

if(wi == w1 + 2) v3.push_back(vi);

if(wi == w1 + 3) v4.push_back(vi);

}

// 2. バッグの価値を降順sort.

sort(v1.begin(), v1.end(), greater<LL>());

sort(v2.begin(), v2.end(), greater<LL>());

sort(v3.begin(), v3.end(), greater<LL>());

sort(v4.begin(), v4.end(), greater<LL>());

// 3. バッグの価値の累積和を作成.

int l1, l2, l3, l4;

l1 = v1.size();

l2 = v2.size();

l3 = v3.size();

l4 = v4.size();

// cout << l1 << " " << l2 << " " << l3 << " " << l4 << endl;

LL a1[l1 + 1] = {};

LL a2[l2 + 1] = {};

LL a3[l3 + 1] = {};

LL a4[l4 + 1] = {};

a1[1] = (l1 > 0) ? v1[0] : 0;

a2[1] = (l2 > 0) ? v2[0] : 0;

a3[1] = (l3 > 0) ? v3[0] : 0;

a4[1] = (l4 > 0) ? v4[0] : 0;

FOR(i, 2, l1 + 1) a1[i] += (v1[i - 1] + a1[i - 1]);

FOR(i, 2, l2 + 1) a2[i] += (v2[i - 1] + a2[i - 1]);

FOR(i, 2, l3 + 1) a3[i] += (v3[i - 1] + a3[i - 1]);

FOR(i, 2, l4 + 1) a4[i] += (v4[i - 1] + a4[i - 1]);

// FOR(i, 0, l1 + 1) cout << a1[i] << " ";

// FOR(i, 0, l2 + 1) cout << a2[i] << " ";

// FOR(i, 0, l3 + 1) cout << a3[i] << " ";

// FOR(i, 0, l4 + 1) cout << a4[i] << " ";

// 4. バッグに入れた物の価値の総和を最大化するための試行錯誤.

LL maxValue = 0;

FOR(i1, 0, l1 + 1) {

FOR(i2, 0, l2 + 1) {

FOR(i3, 0, l3 + 1) {

FOR(i4, 0, l4 + 1) {

// v1 から i1個, v2 から i2個, v3 から i3個, v4 から i4個選んで,

// 重さの和が, W を超えていたら, スキップ.

LL w = w1 * i1 + (w1 + 1) * i2 + (w1 + 2) * i3 + (w1 + 3) * i4;

// cout << i1 << " " << i2 << " " << i3 << " " << i4 << " " << w << endl;

if(w > W) continue;

// 最大値更新.

LL v = a1[i1] + a2[i2] + a3[i3] + a4[i4];

if(maxValue < v) maxValue = v;

}

// 5. 出力～後処理.

cout << maxValue << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 060

C++の練習を兼ねて, AtCoder Beginner Contest 060 の 問題C（Sentou), 問題D（Simple Knapsack) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 060 の問題C（Sentou), 問題D（Simple Knapsack) を解いてみた.

コメントを残すコメントをキャンセル