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

C++の練習を兼ねて, AtCoder Beginner Contest 062 の問題C（Chocolate Bar), 問題D（3N Numbers) を解いてみた.

■感想.
1. 両問題とも, 解答方針が間違えていたので, 解けなかった.
2. 問題C では, 長方形を, 同じ方向に3分割するパターンが, H or W が 3の倍数という先入観で解いたため, 正答に至らなかった.
-> 例として, [入力例] 5 13 に対し, WA版だと 8, AC版だと, 5 というように出力されるので, WA版のロジック誤りについて, 具体的に理解できた.
3. 問題D では, 中央N項の数列に着目して, 数列a’ の前半N要素の総和, 数列a’ の後半N要素の総和を考えてみたが, 上手く行かなかったので, 解答通りに実装し直した.
※LL ans = -99999999999; からスタートして, 最大値を計算しようとすると, 1_10.txt, 2_02.txt で, Wrong Answerとなるので, LL ans = -100000000000000; (10の5乗 × 10の9乗の符号をマイナスにした数)からスタートして, 最大値を計算する必要があるので注意.
4. 優先順位付きキュー std::priority_queue を使う練習が出来たと思われる(※存在を知らなかった(汗)).

本家のサイトABC #062 / ARC #074 Editorialをご覧下さい.

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

// 1_04.txt, 1_09.txt で, Wrong Answer となった.
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define abs(x) ((x > 0) ? x : (-(x)))

typedef long long LL;

int main() {
    
    // 1. 入力情報取得.
    LL H, W;
    cin >> H >> W;
    
    // 2. Smax - Smin を 計算.
    LL ans = 99999999999;
    
    // 2-1. H or W が 3 の倍数 なら, 0.
    if(H % 3 == 0 || W % 3 == 0) ans = 0;
    
    // 2-2. H and W が 3 の倍数でない なら, 以下のような分岐.
    if(H * W % 3 != 0) {
        if(H % 2 == 0) {
            FOR(i, 1, W) {
                LL Sa = H * i;              // H × i の 長方形.
                LL Sb = H / 2 * (W - i);    // (H / 2) × (W - i) の 長方形.
                ans = min(ans, abs(Sa - Sb));
            }
        }
        if(W % 2 == 0) {
            FOR(i, 1, H) {
                LL Sa = W * i;              // W × i の 長方形.
                LL Sb = W / 2 * (H - i);    // (W / 2) × (H - i) の 長方形.
                ans = min(ans, abs(Sa - Sb));
            }
        }
        // テストケース 1_04.txt, 1_09.txt 対応.
        if(H % 2 != 0 && W % 2 != 0) {
            FOR(i, 1, W) {
                LL Sa = H * i;                    // H × i の 長方形.
                LL Sb = H / 2 * (W - i);          // (H / 2) × (W - i) の 長方形.
                LL Sc = (H / 2 + 1) * (W - i);    // (H / 2 + 1) × (W - i) の 長方形.
                LL Smax = max(Sa, Sb);
                Smax = max(Smax, Sc);
                LL Smin = min(Sa, Sb);
                Smin = min(Smin, Sc);
                ans = min(ans, abs(Smax - Smin));
            }
            FOR(i, 1, H) {
                LL Sa = W * i;                    // W × i の 長方形.
                LL Sb = W / 2 * (H - i);          // (W / 2) × (H - i) の 長方形.
                LL Sc = (W / 2 + 1) * (H - i);    // (W / 2 + 1) × (H - i) の 長方形.
                LL Smax = max(Sa, Sb);
                Smax = max(Smax, Sc);
                LL Smin = min(Sa, Sb);
                Smin = min(Smin, Sc);
                ans = min(ans, abs(Smax - Smin));
            }
        }
    }

    // 4. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;
    
}

// 1_04.txt, 1_09.txt で, Wrong Answer となった.

#include <bits/stdc++.h>

using namespace std;

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

#define abs(x) ((x > 0) ? x : (-(x)))

typedef long long LL;

int main() {

// 1. 入力情報取得.

LL H, W;

cin >> H >> W;

// 2. Smax - Smin を計算.

LL ans = 99999999999;

// 2-1. H or W が 3 の倍数なら, 0.

if(H % 3 == 0 || W % 3 == 0) ans = 0;

// 2-2. H and W が 3 の倍数でないなら, 以下のような分岐.

if(H * W % 3 != 0) {

if(H % 2 == 0) {

FOR(i, 1, W) {

LL Sa = H * i; // H × i の長方形.

LL Sb = H / 2 * (W - i); // (H / 2) × (W - i) の長方形.

ans = min(ans, abs(Sa - Sb));

}

if(W % 2 == 0) {

FOR(i, 1, H) {

LL Sa = W * i; // W × i の長方形.

LL Sb = W / 2 * (H - i); // (W / 2) × (H - i) の長方形.

ans = min(ans, abs(Sa - Sb));

}

// テストケース 1_04.txt, 1_09.txt 対応.

if(H % 2 != 0 && W % 2 != 0) {

FOR(i, 1, W) {

LL Sa = H * i; // H × i の長方形.

LL Sb = H / 2 * (W - i); // (H / 2) × (W - i) の長方形.

LL Sc = (H / 2 + 1) * (W - i); // (H / 2 + 1) × (W - i) の長方形.

LL Smax = max(Sa, Sb);

Smax = max(Smax, Sc);

LL Smin = min(Sa, Sb);

Smin = min(Smin, Sc);

ans = min(ans, abs(Smax - Smin));

}

FOR(i, 1, H) {

LL Sa = W * i; // W × i の長方形.

LL Sb = W / 2 * (H - i); // (W / 2) × (H - i) の長方形.

LL Sc = (W / 2 + 1) * (H - i); // (W / 2 + 1) × (H - i) の長方形.

LL Smax = max(Sa, Sb);

Smax = max(Smax, Sc);

LL Smin = min(Sa, Sb);

Smin = min(Smin, Sc);

ans = min(ans, abs(Smax - Smin));

}

// 4. 出力～後処理.

cout << ans << endl;

return 0;

}

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

// 解き直し.
// ABC #062 / ARC #074 Editorial
// https://atcoder.jp/img/arc074/editorial.pdf
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define abs(x) ((x > 0) ? x : (-(x)))

typedef long long LL;

int main() {
    
    // 1. 入力情報取得.
    LL H, W;
    cin >> H >> W;
    
    // 2. Smax - Smin を 計算(4ケース確認).
    LL ans = 99999999999;
    
    // 2-1. 縦方向で, 3分割するパターン.
    FOR(ha, 1, H) {
        LL Sa = ha * W;          // ha × W の 長方形.
        LL hb = (H - ha) / 2;
        LL Sb = hb * W;          // hb × W の 長方形.
        LL hc = H - ha - hb;
        LL Sc = hc * W;          // hc × W の 長方形.
        LL Smax = max(Sa, Sb);
        Smax = max(Smax, Sc);
        LL Smin = min(Sa, Sb);
        Smin = min(Smin, Sc);
        ans = min(ans, abs(Smax - Smin));
    }
    
    // 2-2. 縦方向で, 2分割し, B, C を横方向で, 2分割するパターン.
    FOR(ha, 1, H) {
        LL Sa = ha * W;          // ha × W の 長方形.
        LL wb = W / 2;
        LL hbc = H - ha;
        LL Sb = hbc * wb;        // hbc × wb の 長方形.
        LL wc = W - wb;
        LL Sc = hbc * wc;        // hbc × wb の 長方形.
        LL Smax = max(Sa, Sb);
        Smax = max(Smax, Sc);
        LL Smin = min(Sa, Sb);
        Smin = min(Smin, Sc);
        ans = min(ans, abs(Smax - Smin));
    }
    
    // 2-3. 2-1. で 縦横入れ替えしたパターン.
    FOR(wa, 1, W) {
        LL Sa = H * wa;          // H × wa の 長方形.
        LL wb = (W - wa) / 2;
        LL Sb = H * wb;          // H × wb の 長方形.
        LL wc = W - wa - wb;
        LL Sc = H * wc;          // H × wc の 長方形.
        LL Smax = max(Sa, Sb);
        Smax = max(Smax, Sc);
        LL Smin = min(Sa, Sb);
        Smin = min(Smin, Sc);
        ans = min(ans, abs(Smax - Smin));
    }
    
    // 2-4. 2-2. で 縦横入れ替えしたパターン.
    FOR(wa, 1, W) {
        LL Sa = H * wa;          // H × wa の 長方形.
        LL hb = H / 2;
        LL wbc = W - wa;
        LL Sb = hb * wbc;        // hb × wbc の 長方形.
        LL hc = H - hb;
        LL Sc = hc * wbc;        // hc × wbc の 長方形.
        LL Smax = max(Sa, Sb);
        Smax = max(Smax, Sc);
        LL Smin = min(Sa, Sb);
        Smin = min(Smin, Sc);
        ans = min(ans, abs(Smax - Smin));
    }
    
    // 4. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;
    
}

// 解き直し.

// ABC #062 / ARC #074 Editorial

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

#include <bits/stdc++.h>

using namespace std;

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

#define abs(x) ((x > 0) ? x : (-(x)))

typedef long long LL;

int main() {

// 1. 入力情報取得.

LL H, W;

cin >> H >> W;

// 2. Smax - Smin を計算(4ケース確認).

LL ans = 99999999999;

// 2-1. 縦方向で, 3分割するパターン.

FOR(ha, 1, H) {

LL Sa = ha * W; // ha × W の長方形.

LL hb = (H - ha) / 2;

LL Sb = hb * W; // hb × W の長方形.

LL hc = H - ha - hb;

LL Sc = hc * W; // hc × W の長方形.

LL Smax = max(Sa, Sb);

Smax = max(Smax, Sc);

LL Smin = min(Sa, Sb);

Smin = min(Smin, Sc);

ans = min(ans, abs(Smax - Smin));

}

// 2-2. 縦方向で, 2分割し, B, C を横方向で, 2分割するパターン.

FOR(ha, 1, H) {

LL Sa = ha * W; // ha × W の長方形.

LL wb = W / 2;

LL hbc = H - ha;

LL Sb = hbc * wb; // hbc × wb の長方形.

LL wc = W - wb;

LL Sc = hbc * wc; // hbc × wb の長方形.

LL Smax = max(Sa, Sb);

Smax = max(Smax, Sc);

LL Smin = min(Sa, Sb);

Smin = min(Smin, Sc);

ans = min(ans, abs(Smax - Smin));

}

// 2-3. 2-1. で縦横入れ替えしたパターン.

FOR(wa, 1, W) {

LL Sa = H * wa; // H × wa の長方形.

LL wb = (W - wa) / 2;

LL Sb = H * wb; // H × wb の長方形.

LL wc = W - wa - wb;

LL Sc = H * wc; // H × wc の長方形.

LL Smax = max(Sa, Sb);

Smax = max(Smax, Sc);

LL Smin = min(Sa, Sb);

Smin = min(Smin, Sc);

ans = min(ans, abs(Smax - Smin));

}

// 2-4. 2-2. で縦横入れ替えしたパターン.

FOR(wa, 1, W) {

LL Sa = H * wa; // H × wa の長方形.

LL hb = H / 2;

LL wbc = W - wa;

LL Sb = hb * wbc; // hb × wbc の長方形.

LL hc = H - hb;

LL Sc = hc * wbc; // hc × wbc の長方形.

LL Smax = max(Sa, Sb);

Smax = max(Smax, Sc);

LL Smin = min(Sa, Sb);

Smin = min(Smin, Sc);

ans = min(ans, abs(Smax - Smin));

}

// 4. 出力～後処理.

cout << ans << endl;

return 0;

}

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

// 1_03.txt, 1_05.txt, 1_10.txt - 1_11.txt, 1_13.txt, 1_16.txt - 1_23.txt, 2_02.txt - 2_03.txt 
// 2_05.txt, 2_08.txt - 2_15.txt で, Wrong Answer となった.
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

#define FOR(i, a, b) for(LL i = (a); i < (b); ++i)
#define FORR(i, a, b) for(LL i = (a); i >= (b); --i)

int main() {

    // 1. 入力情報取得.
    LL N;
    cin >> N;
    LL As[N], Am[N], Ae[N];
    LL AsTotal[N + 1] = {};
    LL AeTotal[N + 1] = {};

    FOR(i, 0, N) {
        LL ai;
        cin >> ai;
        // 数列a の 前半N項.
        As[i] = ai;
        // 数列a の 前半N項の総和 を保存.
        AsTotal[0] += ai;
    }
    FOR(i, 0, N) cin >> Am[i];    // 数列a の 中央N項.
    FOR(i, 0, N) {
        LL ai;
        cin >> ai;
        // 数列a の 後半N項.
        Ae[i] = ai;
        // 数列a の 後半N項の総和 を保存.
        AeTotal[N] += ai;
    }
    
    // 2. sort.
    // As … 昇順sort.
    // Am … sort無し.
    // Ae … 降順sort.
    sort(As, As + N);
    sort(Ae, Ae + N, greater<LL>());
    // FOR(i, 0, N) cout << As[i] << " ";
    // FOR(i, 0, N) cout << Am[i] << " ";
    // FOR(i, 0, N) cout << Ae[i] << " ";
    
    // 3. 残った数列a'について, スコアを確認.
    // 3-1. 数列a' の前半N要素の総和を, 順次保存.
    LL minAs = As[0];
    FOR(i, 1, N + 1) {
        // Am[i - 1] が, minAs よりも大きいか確認.
        if(Am[i - 1] > minAs) {
            AsTotal[i] = AsTotal[i - 1] + Am[i - 1] - minAs;
            minAs = max(minAs, As[i]);
            minAs = min(minAs, Am[i - 1]);
        } else {
            AsTotal[i] = AsTotal[i - 1];
        }
        // cout << i << " " << Am[i - 1] << " " << minAs << " " << AsTotal[i - 1] << " -> " << AsTotal[i] << endl;
    }

    // 3-2. 数列a' の後半N要素の総和を, 順次保存.
    LL maxAe = Ae[0];
    FORR(i, N - 1, 0) {
        // Am[i] が, maxAe よりも小さいか確認.
        if(Am[i] < maxAe) {
            AeTotal[i] = AeTotal[i + 1] + Am[i] - maxAe;
            maxAe = min(maxAe, Ae[N - i]);
            maxAe = max(maxAe, Am[i]);
        } else {
            AeTotal[i] = AeTotal[i + 1];
        }
    }
    // FOR(i, 0, N + 1) cout << AsTotal[i] << " ";
    // FOR(i, 0, N + 1) cout << AeTotal[i] << " ";

    // 4. 出力 ～ 後処理.
    LL ans = -99999999999;
    FOR(i, 0, N) ans = max(ans, AsTotal[i] - AeTotal[i]);
    cout << ans << endl;
    return 0;
    
}

// 1_03.txt, 1_05.txt, 1_10.txt - 1_11.txt, 1_13.txt, 1_16.txt - 1_23.txt, 2_02.txt - 2_03.txt

// 2_05.txt, 2_08.txt - 2_15.txt で, Wrong Answer となった.

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

#define FORR(i, a, b) for(LL i = (a); i >= (b); --i)

int main() {

// 1. 入力情報取得.

LL N;

cin >> N;

LL As[N], Am[N], Ae[N];

LL AsTotal[N + 1] = {};

LL AeTotal[N + 1] = {};

FOR(i, 0, N) {

LL ai;

cin >> ai;

// 数列a の前半N項.

As[i] = ai;

// 数列a の前半N項の総和を保存.

AsTotal[0] += ai;

}

FOR(i, 0, N) cin >> Am[i]; // 数列a の中央N項.

FOR(i, 0, N) {

LL ai;

cin >> ai;

// 数列a の後半N項.

Ae[i] = ai;

// 数列a の後半N項の総和を保存.

AeTotal[N] += ai;

}

// 2. sort.

// As … 昇順sort.

// Am … sort無し.

// Ae … 降順sort.

sort(As, As + N);

sort(Ae, Ae + N, greater<LL>());

// FOR(i, 0, N) cout << As[i] << " ";

// FOR(i, 0, N) cout << Am[i] << " ";

// FOR(i, 0, N) cout << Ae[i] << " ";

// 3. 残った数列a'について, スコアを確認.

// 3-1. 数列a' の前半N要素の総和を, 順次保存.

LL minAs = As[0];

FOR(i, 1, N + 1) {

// Am[i - 1] が, minAs よりも大きいか確認.

if(Am[i - 1] > minAs) {

AsTotal[i] = AsTotal[i - 1] + Am[i - 1] - minAs;

minAs = max(minAs, As[i]);

minAs = min(minAs, Am[i - 1]);

} else {

AsTotal[i] = AsTotal[i - 1];

}

// cout << i << " " << Am[i - 1] << " " << minAs << " " << AsTotal[i - 1] << " -> " << AsTotal[i] << endl;

}

// 3-2. 数列a' の後半N要素の総和を, 順次保存.

LL maxAe = Ae[0];

FORR(i, N - 1, 0) {

// Am[i] が, maxAe よりも小さいか確認.

if(Am[i] < maxAe) {

AeTotal[i] = AeTotal[i + 1] + Am[i] - maxAe;

maxAe = min(maxAe, Ae[N - i]);

maxAe = max(maxAe, Am[i]);

} else {

AeTotal[i] = AeTotal[i + 1];

}

// FOR(i, 0, N + 1) cout << AsTotal[i] << " ";

// FOR(i, 0, N + 1) cout << AeTotal[i] << " ";

// 4. 出力～後処理.

LL ans = -99999999999;

FOR(i, 0, N) ans = max(ans, AsTotal[i] - AeTotal[i]);

cout << ans << endl;

return 0;

}

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

// 解き直し.
// ABC #062 / ARC #074 Editorial
// https://atcoder.jp/img/arc074/editorial.pdf
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

#define FOR(i, a, b) for(LL i = (a); i < (b); ++i)
#define FORR(i, a, b) for(LL i = (a); i >= (b); --i)

int main() {

    // 1. 入力情報取得.
    LL N;
    cin >> N;
    // How can I create Min stl priority_queue?
    // https://stackoverflow.com/questions/2439283/how-can-i-create-min-stl-priority-queue
    priority_queue<LL, vector<LL>, greater<LL>> Qs;
    LL Am[N];
    priority_queue<LL> Qe;
    LL QsTotal[N + 1] = {};
    LL QeTotal[N + 1] = {};

    FOR(i, 0, N) {
        LL ai;
        cin >> ai;
        // 数列a の 前半N項.
        Qs.push(ai);
        // 数列a の 前半N項の総和 を保存.
        QsTotal[0] += ai;
    }
    FOR(i, 0, N) cin >> Am[i];    // 数列a の 中央N項.
    FOR(i, 0, N) {
        LL ai;
        cin >> ai;
        // 数列a の 後半N項.
        Qe.push(ai);
        // 数列a の 後半N項の総和 を保存.
        QeTotal[N] += ai;
    }

    // 2. 数列a の 中央N項 について, 順次確認.
    // 2-1. 数列a' の前半N要素の総和を, 順次保存.
    FOR(i, 0, N) {
        LL ai = Am[i];
        Qs.push(ai);
        QsTotal[i + 1] = QsTotal[i] + ai - Qs.top();
        Qs.pop();
    }
    
    // 2-2. 数列a' の後半N要素の総和を, 順次保存.
    FORR(i, N - 1, 0) {
        LL ai = Am[i];
        Qe.push(ai);
        QeTotal[i] = QeTotal[i + 1] + ai - Qe.top();
        Qe.pop();
    }
    
    // FOR(i, 0, N + 1) cout << QsTotal[i] << " ";
    // FOR(i, 0, N + 1) cout << QeTotal[i] << " ";

    // 3. 出力 ～ 後処理.
    // LL ans = -99999999999;    // 1_10.txt, 2_02.txt で, Wrong Answer.
    LL ans = -100000000000000;
    FOR(i, 0, N + 1) ans = max(ans, QsTotal[i] - QeTotal[i]);
    cout << ans << endl;
    return 0;
    
}

// 解き直し.

// ABC #062 / ARC #074 Editorial

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

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

#define FORR(i, a, b) for(LL i = (a); i >= (b); --i)

int main() {

// 1. 入力情報取得.

LL N;

cin >> N;

// How can I create Min stl priority_queue?

// https://stackoverflow.com/questions/2439283/how-can-i-create-min-stl-priority-queue

priority_queue<LL, vector<LL>, greater<LL>> Qs;

LL Am[N];

priority_queue<LL> Qe;

LL QsTotal[N + 1] = {};

LL QeTotal[N + 1] = {};

FOR(i, 0, N) {

LL ai;

cin >> ai;

// 数列a の前半N項.

Qs.push(ai);

// 数列a の前半N項の総和を保存.

QsTotal[0] += ai;

}

FOR(i, 0, N) cin >> Am[i]; // 数列a の中央N項.

FOR(i, 0, N) {

LL ai;

cin >> ai;

// 数列a の後半N項.

Qe.push(ai);

// 数列a の後半N項の総和を保存.

QeTotal[N] += ai;

}

// 2. 数列a の中央N項について, 順次確認.

// 2-1. 数列a' の前半N要素の総和を, 順次保存.

FOR(i, 0, N) {

LL ai = Am[i];

Qs.push(ai);

QsTotal[i + 1] = QsTotal[i] + ai - Qs.top();

Qs.pop();

}

// 2-2. 数列a' の後半N要素の総和を, 順次保存.

FORR(i, N - 1, 0) {

LL ai = Am[i];

Qe.push(ai);

QeTotal[i] = QeTotal[i + 1] + ai - Qe.top();

Qe.pop();

}

// FOR(i, 0, N + 1) cout << QsTotal[i] << " ";

// FOR(i, 0, N + 1) cout << QeTotal[i] << " ";

// 3. 出力～後処理.

// LL ans = -99999999999; // 1_10.txt, 2_02.txt で, Wrong Answer.

LL ans = -100000000000000;

FOR(i, 0, N + 1) ans = max(ans, QsTotal[i] - QeTotal[i]);

cout << ans << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 062

C++の練習を兼ねて, AtCoder Beginner Contest 062 の 問題C（Chocolate Bar), 問題D（3N Numbers) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 062 の問題C（Chocolate Bar), 問題D（3N Numbers) を解いてみた.

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