個人用メモ帳

2018年10月24日2018年10月24日

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

2018年10月20日

■感想.
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

2018年10月17日

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

C++の練習を兼ねて, AtCoder Beginner Contest 064 の問題D（Insertion) を解いてみた.

■感想.
1. 左括弧 ‘)’ を軸に考えてみたところ, 何とか解答できた.
2. 標準ライブラリ std::deque を使う練習が出来たと思われる.

本家のサイトAtCoder Beginner Contest 064 解説をご覧下さい.

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

#include <bits/stdc++.h>

using namespace std;

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

int main() {

    // 1. 入力情報取得.
    int N;
    string S;
    cin >> N;
    cin >> S;
    
    // 2. 正しい括弧列を構成.
    // 文字列S を左から確認して, 
    // '(' なら, 左括弧のカウンターを +1 する.
    // ')' なら, 左括弧のカウンターを -1 するか, 右括弧を追加する.
    //
    deque<char> dq;
    int l = 0;    // '('カウンター(※左括弧が, どのくらい出現し過ぎているかチェック)
    FOR(i, 0, S.size()) {
        char c = S[i];
        dq.push_back(c);
        if(c == '(') l++;
        if(c == ')') {
            if(l == 0) dq.push_front('(');
            else       l--;
        }
    }
    
    // 3. 出力文字列を作成.
    // l が 0 より大きい場合に, 注意が必要.
    string ans;
    for(auto &c : dq) ans += c;
    FOR(i, 0, l) ans += ')';
    
    // 4. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

int main() {

// 1. 入力情報取得.

int N;

string S;

cin >> N;

cin >> S;

// 2. 正しい括弧列を構成.

// 文字列S を左から確認して,

// '(' なら, 左括弧のカウンターを +1 する.

// ')' なら, 左括弧のカウンターを -1 するか, 右括弧を追加する.

deque<char> dq;

int l = 0; // '('カウンター(※左括弧が, どのくらい出現し過ぎているかチェック)

FOR(i, 0, S.size()) {

char c = S[i];

dq.push_back(c);

if(c == '(') l++;

if(c == ')') {

if(l == 0) dq.push_front('(');

else l--;

}

// 3. 出力文字列を作成.

// l が 0 より大きい場合に, 注意が必要.

string ans;

for(auto &c : dq) ans += c;

FOR(i, 0, l) ans += ')';

// 4. 出力～後処理.

cout << ans << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 064

2018年10月14日2018年10月27日

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

C++の練習を兼ねて, AtCoder Grand Contest 028 の問題B（Removing Blocks) を解いてみた.

■感想.
1. 時間内で, 解答方針が全く分からなかったので, コンテスト終了後に, 解答を確認して, コーディングしてみた.
2. ブロックの連結についての解説が, なるほどと感心したが, 実際に答案へ反映する作業は, かなり大変だった(汗).

本家のサイトAGC 028 解説をご覧下さい.

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

// 解き直し.
// AGC 028 解説.
// https://img.atcoder.jp/agc028/editorial.pdf
#include <bits/stdc++.h>

using namespace std;

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

typedef long long LL;

const LL MOD = 1000000007;

// Fermat's little theorem を 適用するため, 大きな冪乗の計算ができるようにする.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL inverse(LL a, LL b){
    LL t = 1;
    while(b) {
        if(b & 1) t = (t * a) % MOD;
        a *= a;
        a %= MOD;
        b >>= 1;
    }
    return t % MOD;
}

int main() {
    
    // 1. 入力情報取得.
    LL N;
    cin >> N;
    LL A[N + 1] = {};
    FOR(i, 1, N + 1) cin >> A[i];
    
    // 解説通り.
    // ------------------------------------------------------------------------------------------
    // 2. 1/1, 1/2, 1/3, ... , 1/N の 累積和を保管.
    // Fermat's Little Theorem から, 1/x = x の (p - 2)乗 で 計算可能(※本問では, p = 1000000007).
    // 例) 1/2 = 500000004, 1/3 = 333333336, ..., 1/9 = 111111112, ...などと計算される.
    LL INV[100001] = {};
    FOR(i, 1, 100001) {
        INV[i] += INV[i - 1];
        INV[i] += inverse(i, MOD - 2) % MOD;
    }
    
    // 3. block[i] を取り除くとき, block[i], block[j] が連結である確率を, 
    // P(i, j) と置いて, P(j) = ΣP(i, j) を, 計算する.
    // P(i, j) は, P(i, j) = 1 / (abs(i - j) + 1) で, 計算可能とのこと.
    LL P[N + 1] = {};
    FOR(i, 1, N + 1) {
        LL r = abs(i - 1 + 1);    // 左端までの距離(1 ～ i).
        LL l = abs(N - i + 1);    // 右端までの距離(i ～ N).
        P[i] += INV[r];
        P[i] %= MOD;
        P[i] += INV[l];
        P[i] %= MOD;
        P[i] -= INV[1];
        P[i] %= MOD;
    }
    
    // 4. 総コスト = Σ(A[j] × P(j)) × N! で, N回の操作のコストの合計(期待値)を求める.
    LL total = 0;
    // 4-1. Σ(A[j] × P(j)) の 部分 を 計算.
    FOR(i, 1, N + 1) {
        total += A[i] * P[i];
        total %= MOD;
        // cout << i << " " << A[i] << " " << P[i] << endl;
    }
    
    // 4-2. × N! の 部分 を 計算.
    FOR(i, 1, N + 1) {
        total *= i;
        total %= MOD;
    }
    // ------------------------------------------------------------------------------------------
    
    // 5. 後処理.
    cout << total << endl;
    return 0;
    
}

// 解き直し.

// AGC 028 解説.

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

#include <bits/stdc++.h>

using namespace std;

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

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

typedef long long LL;

const LL MOD = 1000000007;

// Fermat's little theorem を適用するため, 大きな冪乗の計算ができるようにする.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL inverse(LL a, LL b){

LL t = 1;

while(b) {

if(b & 1) t = (t * a) % MOD;

a *= a;

a %= MOD;

b >>= 1;

}

return t % MOD;

}

int main() {

// 1. 入力情報取得.

LL N;

cin >> N;

LL A[N + 1] = {};

FOR(i, 1, N + 1) cin >> A[i];

// 解説通り.

// ------------------------------------------------------------------------------------------

// 2. 1/1, 1/2, 1/3, ... , 1/N の累積和を保管.

// Fermat's Little Theorem から, 1/x = x の (p - 2)乗で計算可能(※本問では, p = 1000000007).

// 例) 1/2 = 500000004, 1/3 = 333333336, ..., 1/9 = 111111112, ...などと計算される.

LL INV[100001] = {};

FOR(i, 1, 100001) {

INV[i] += INV[i - 1];

INV[i] += inverse(i, MOD - 2) % MOD;

}

// 3. block[i] を取り除くとき, block[i], block[j] が連結である確率を,

// P(i, j) と置いて, P(j) = ΣP(i, j) を, 計算する.

// P(i, j) は, P(i, j) = 1 / (abs(i - j) + 1) で, 計算可能とのこと.

LL P[N + 1] = {};

FOR(i, 1, N + 1) {

LL r = abs(i - 1 + 1); // 左端までの距離(1 ～ i).

LL l = abs(N - i + 1); // 右端までの距離(i ～ N).

P[i] += INV[r];

P[i] %= MOD;

P[i] += INV[l];

P[i] %= MOD;

P[i] -= INV[1];

P[i] %= MOD;

}

// 4. 総コスト = Σ(A[j] × P(j)) × N! で, N回の操作のコストの合計(期待値)を求める.

LL total = 0;

// 4-1. Σ(A[j] × P(j)) の部分を計算.

FOR(i, 1, N + 1) {

total += A[i] * P[i];

total %= MOD;

// cout << i << " " << A[i] << " " << P[i] << endl;

}

// 4-2. × N! の部分を計算.

FOR(i, 1, N + 1) {

total *= i;

total %= MOD;

}

// ------------------------------------------------------------------------------------------

// 5. 後処理.

cout << total << endl;

return 0;

}

■入力／出力例

[入力例]
2
1 2

[総コスト]
ブロック1: 1/1 + 1/2 = 3/2
ブロック2: 1/2 + 1/1 = 3/2
-> 各操作に関するコストの期待値: 3/2 * 1 + 3/2 * 2 = 9/2
-> 2!倍すると, 総コスト9 となる.

[入力例]
4
1 1 1 1

[総コスト]
ブロック1: 1/1 + 1/2 + 1/3 + 1/4 = 25/12
ブロック2: 1/2 + 1/1 + 1/2 + 1/3 = 7/3
ブロック3: 1/3 + 1/2 + 1/1 + 1/2 = 7/3
ブロック4: 1/4 + 1/3 + 1/2 + 1/1 = 25/12
-> 各操作に関するコストの期待値: 25/12 * 1 + 7/3 * 1 + 7/3 * 1 + 25/12 * 1 = 53 / 6
-> 4!倍すると, 総コスト212 となる.

[入力例]
5
3 4 5 2 1

[総コスト]
ブロック1: 1/1 + 1/2 + 1/3 + 1/4 + 1/5 = 137/60
ブロック2: 1/2 + 1/1 + 1/2 + 1/3 + 1/4 = 31/12
ブロック3: 1/3 + 1/2 + 1/1 + 1/2 + 1/3 = 8/3
ブロック4: 1/4 + 1/3 + 1/2 + 1/1 + 1/2 = 31/12
ブロック5: 1/5 + 1/4 + 1/3 + 1/2 + 1/1 = 137/60
-> 各操作に関するコストの期待値: 137/60 * 3 + 31/12 * 4 + 8/3 * 5 + 31/12 * 2 + 137/60 * 1 = 1139 / 30
-> 5!倍すると, 総コスト4556 となる.

[入力例]
10
1 2 4 8 16 32 64 128 256 512

[出力例]
880971923

[入力例]

1 2

[総コスト]

ブロック1: 1/1 + 1/2 = 3/2

ブロック2: 1/2 + 1/1 = 3/2

-> 各操作に関するコストの期待値: 3/2 * 1 + 3/2 * 2 = 9/2

-> 2!倍すると, 総コスト9 となる.

[入力例]

1 1 1 1

[総コスト]

ブロック1: 1/1 + 1/2 + 1/3 + 1/4 = 25/12

ブロック2: 1/2 + 1/1 + 1/2 + 1/3 = 7/3

ブロック3: 1/3 + 1/2 + 1/1 + 1/2 = 7/3

ブロック4: 1/4 + 1/3 + 1/2 + 1/1 = 25/12

-> 各操作に関するコストの期待値: 25/12 * 1 + 7/3 * 1 + 7/3 * 1 + 25/12 * 1 = 53 / 6

-> 4!倍すると, 総コスト212 となる.

[入力例]

3 4 5 2 1

[総コスト]

ブロック1: 1/1 + 1/2 + 1/3 + 1/4 + 1/5 = 137/60

ブロック2: 1/2 + 1/1 + 1/2 + 1/3 + 1/4 = 31/12

ブロック3: 1/3 + 1/2 + 1/1 + 1/2 + 1/3 = 8/3

ブロック4: 1/4 + 1/3 + 1/2 + 1/1 + 1/2 = 31/12

ブロック5: 1/5 + 1/4 + 1/3 + 1/2 + 1/1 = 137/60

-> 各操作に関するコストの期待値: 137/60 * 3 + 31/12 * 4 + 8/3 * 5 + 31/12 * 2 + 137/60 * 1 = 1139 / 30

-> 5!倍すると, 総コスト4556 となる.

[入力例]

1 2 4 8 16 32 64 128 256 512

[出力例]

880971923

■参照サイト
AtCoder Grand Contest 028

2018年10月7日2018年10月7日

PyTorch の動作確認をしてみた（７）

1. 環境は、Window 10 Home (64bit) 上で行った。

2. Anaconda3 (64bit) – Spyder上で、動作確認を行った。

3. python のバージョンは、python 3.6.5 である。

4. pytorch のバージョンは、pytorch 0.4.1 である。

5. GPU は, NVIDIA社の GeForce GTX 1050 である。

6. CPU は, Intel社の Core(TM) i7-7700HQ である。

今回確認した内容は、現場で使える! PyTorch開発入門深層学習モデルの作成とアプリケーションへの実装 (AI & TECHNOLOGY) の 4.2.2 CNNの構築と学習(P.067 – P.071) である。
前回に引き続き, Fashion-MNIST を使った, CNN の画像分類について, 少し動作確認を行った.
前回の課題として, 書籍上には, 正誤判定の結果に関する, 具体的な情報が未記載だったので, 今回は, 実際に, 画像を出力させるようにプログラムを書き換えて確認することになった.

※プログラムの詳細は、書籍を参考(P.067 – P.071)にして下さい。

■Fashion-MNISTの学習(正誤判定の画像出力版).

# -*- coding: utf-8 -*-
# tqdm を 下記コマンドで, install.
# conda install -c conda-forge tqdm
# 1. library import.
from __future__ import print_function
import torch
import torchvision
from torchvision.datasets import FashionMNIST
from torchvision import transforms
from torch.utils.data import DataLoader
import os, time
from torch import nn, optim
from tqdm import tqdm
import numpy as np
import matplotlib.pyplot as plt

# 2. declare functions.
# 2-1. display image function.
def imshow(inp, title=None):
    """Imshow for Tensor."""
    inp = inp.numpy().transpose((1, 2, 0))
    mean = np.array([0.485, 0.456, 0.406])
    std = np.array([0.229, 0.224, 0.225])
    inp = std * inp + mean
    inp = np.clip(inp, 0, 1)
    plt.axis('off')
    plt.imshow(inp)
    if title is not None:
        plt.title(title)
    # plt.pause(0.001)  # pause a bit so that plots are updated

# 2-2. A layer that stretches a Tensor of the (H, C, H, W) type to (N, C * H * W).
# required to pass the output of convolution layer to MLP.
class FlattenLayer(nn.Module):
    def forward(self, x):
        sizes = x.size()
        return x.view(sizes[0], - 1)

～(略)～

# 2-4. eval helper function.
def eval_net(net, data_loader, device="cpu"):
    # invalidate Dropout and BatchNorm.
～(略)～
    # a = [1, 2, 3, 4, 5]
    # b = [1, 3, 4, 3, 5]
    # c = [i for i, j in zip(a, b) if i == j]
    # print(c) # [1, 5]
    # [index, i, j] は, 誤検知画像のindex, 正解ラベル, 予測ラベル の意味.
    correct, wrong = [], []
    for index, (i, j) in enumerate(zip(ys, ypreds)):
        if i == j:
            correct.append([index, i, j])
        else:
            wrong.append([index, i, j])
    return acc.item(), correct, wrong
    

～(略)～

# 2-5. train net helper function.
def train_net(net, train_loader, test_loader, optimizer_cls=optim.Adam, 
              loss_fn=nn.CrossEntropyLoss(), n_iter=10, device="cpu"):
    train_losses, train_acc, val_acc = [], [], []
    optimizer = optimizer_cls(net.parameters())
    correct_list, wrong_list = [], []
～(略)～
        e = eval_net(net, test_loader, device)
        val_acc.append(e[0])
        if epoch + 1 == n_iter:
            correct_list.append(e[1])
            wrong_list.append(e[2])
        print(epoch, train_losses[-1], train_acc[-1], val_acc[-1], flush=True)
    return correct_list, wrong_list


～(略)～

# 5. execute training.
net.to("cuda:0")
correct_list, wrong_list = train_net(net, train_loader, test_loader, n_iter=1, device="cuda:0")

# 6. display processing time.
end = time.time()
# images: torch.Size([128, 1, 28, 28])
# images, labels: <class 'torch.Tensor'>
# images[0]: torch.Size([1, 28, 28])
images, labels = next(iter(test_loader))
# print(images.size())

# check the data size.
print('--- display 9 wrong answers ------------------------------------------')
# wrong_list[0][0:9][0]: <class 'list'>, wrong_list[0][0:9][0][1]: <class 'torch.Tensor'>
print(wrong_list[0][0:9])
indexes_for_wrong_list_image = [x[0] for x in wrong_list[0][0:9]]
print(str(indexes_for_wrong_list_image)) # ex. [17, 23, 40, 42, 46, 49, 68, 74, 98]
wrong_images_list = []
for i, v in enumerate(images):
    if i in indexes_for_wrong_list_image:
        # print(i)
        # 検証用画像 の サイズ(28 × 28)
        # v[0].size(): torch.Size([28, 28])
        # print(v[0].size())
        # Adding a dimension to a tensor in PyTorch.
        # http://blog.outcome.io/adding-a-dimension-to-a-tensor-in-pytorch/
        # uv: torch.Size([28, 28]) -> torch.Size([1, 28, 28])
        uv = v[0][None, :, :]
        wrong_images_list.append(uv)
# How to turn a list of tensor to tensor?
# https://discuss.pytorch.org/t/how-to-turn-a-list-of-tensor-to-tensor/8868/4
# -> convert list to torch.Tensor by torch.stack.
wrong_images_list = torch.stack(wrong_images_list)
print(wrong_images_list.size()) # torch.Size([9, 1, 28, 28])
wrong_images = torchvision.utils.make_grid(wrong_images_list, nrow=3, padding=1)
plt.subplot(121)
plt.title('wrong')
imshow(wrong_images)

print('--- display 9 correct answers ----------------------------------------')
print(correct_list[0][0:9])
indexes_for_correct_list_image = [x[0] for x in correct_list[0][0:9]]
print(str(indexes_for_correct_list_image)) # ex. [0, 1, 2, 3, 4, 5, 6, 7, 8]
correct_images_list = []
for i, v in enumerate(images):
    if i in indexes_for_correct_list_image:
        uv = v[0][None, :, :]
        correct_images_list.append(uv)        
correct_images_list = torch.stack(correct_images_list)
# print(correct_images_list.size())
correct_images = torchvision.utils.make_grid(correct_images_list, nrow=3, padding=1)
plt.subplot(122)
plt.title('correct')
imshow(correct_images)        

print('--------------------------------------------------')
print('Elapsed Time: ' + str(end - start) + "[sec]")

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

# -*- coding: utf-8 -*-

# tqdm を下記コマンドで, install.

# conda install -c conda-forge tqdm

# 1. library import.

from __future__ import print_function

import torch

import torchvision

from torchvision.datasets import FashionMNIST

from torchvision import transforms

from torch.utils.data import DataLoader

import os, time

from torch import nn, optim

from tqdm import tqdm

import numpy as np

import matplotlib.pyplot as plt

# 2. declare functions.

# 2-1. display image function.

def imshow(inp, title=None):

"""Imshow for Tensor."""

inp = inp.numpy().transpose((1, 2, 0))

mean = np.array([0.485, 0.456, 0.406])

std = np.array([0.229, 0.224, 0.225])

inp = std * inp + mean

inp = np.clip(inp, 0, 1)

plt.axis('off')

plt.imshow(inp)

if title is not None:

plt.title(title)

# plt.pause(0.001) # pause a bit so that plots are updated

# 2-2. A layer that stretches a Tensor of the (H, C, H, W) type to (N, C * H * W).

# required to pass the output of convolution layer to MLP.

class FlattenLayer(nn.Module):

def forward(self, x):

sizes = x.size()

return x.view(sizes[0], - 1)

～(略)～

# 2-4. eval helper function.

def eval_net(net, data_loader, device="cpu"):

# invalidate Dropout and BatchNorm.

～(略)～

# a = [1, 2, 3, 4, 5]

# b = [1, 3, 4, 3, 5]

# c = [i for i, j in zip(a, b) if i == j]

# print(c) # [1, 5]

# [index, i, j] は, 誤検知画像のindex, 正解ラベル, 予測ラベルの意味.

correct, wrong = [], []

for index, (i, j) in enumerate(zip(ys, ypreds)):

if i == j:

correct.append([index, i, j])

else:

wrong.append([index, i, j])

return acc.item(), correct, wrong

～(略)～

# 2-5. train net helper function.

def train_net(net, train_loader, test_loader, optimizer_cls=optim.Adam,

loss_fn=nn.CrossEntropyLoss(), n_iter=10, device="cpu"):

train_losses, train_acc, val_acc = [], [], []

optimizer = optimizer_cls(net.parameters())

correct_list, wrong_list = [], []

～(略)～

e = eval_net(net, test_loader, device)

val_acc.append(e[0])

if epoch + 1 == n_iter:

correct_list.append(e[1])

wrong_list.append(e[2])

print(epoch, train_losses[-1], train_acc[-1], val_acc[-1], flush=True)

return correct_list, wrong_list

～(略)～

# 5. execute training.

net.to("cuda:0")

correct_list, wrong_list = train_net(net, train_loader, test_loader, n_iter=1, device="cuda:0")

# 6. display processing time.

end = time.time()

# images: torch.Size([128, 1, 28, 28])

# images, labels: <class 'torch.Tensor'>

# images[0]: torch.Size([1, 28, 28])

images, labels = next(iter(test_loader))

# print(images.size())

# check the data size.

print('--- display 9 wrong answers ------------------------------------------')

# wrong_list[0][0:9][0]: <class 'list'>, wrong_list[0][0:9][0][1]: <class 'torch.Tensor'>

print(wrong_list[0][0:9])

indexes_for_wrong_list_image = [x[0] for x in wrong_list[0][0:9]]

print(str(indexes_for_wrong_list_image)) # ex. [17, 23, 40, 42, 46, 49, 68, 74, 98]

wrong_images_list = []

for i, v in enumerate(images):

if i in indexes_for_wrong_list_image:

# print(i)

# 検証用画像のサイズ(28 × 28)

# v[0].size(): torch.Size([28, 28])

# print(v[0].size())

# Adding a dimension to a tensor in PyTorch.

# http://blog.outcome.io/adding-a-dimension-to-a-tensor-in-pytorch/

# uv: torch.Size([28, 28]) -> torch.Size([1, 28, 28])

uv = v[0][None, :, :]

wrong_images_list.append(uv)

# How to turn a list of tensor to tensor?

# https://discuss.pytorch.org/t/how-to-turn-a-list-of-tensor-to-tensor/8868/4

# -> convert list to torch.Tensor by torch.stack.

wrong_images_list = torch.stack(wrong_images_list)

print(wrong_images_list.size()) # torch.Size([9, 1, 28, 28])

wrong_images = torchvision.utils.make_grid(wrong_images_list, nrow=3, padding=1)

plt.subplot(121)

plt.title('wrong')

imshow(wrong_images)

print('--- display 9 correct answers ----------------------------------------')

print(correct_list[0][0:9])

indexes_for_correct_list_image = [x[0] for x in correct_list[0][0:9]]

print(str(indexes_for_correct_list_image)) # ex. [0, 1, 2, 3, 4, 5, 6, 7, 8]

correct_images_list = []

for i, v in enumerate(images):

if i in indexes_for_correct_list_image:

uv = v[0][None, :, :]

correct_images_list.append(uv)

correct_images_list = torch.stack(correct_images_list)

# print(correct_images_list.size())

correct_images = torchvision.utils.make_grid(correct_images_list, nrow=3, padding=1)

plt.subplot(122)

plt.title('correct')

imshow(correct_images)

print('--------------------------------------------------')

print('Elapsed Time: ' + str(end - start) + "[sec]")

■実行結果(epoch = 1).

100%|██████████| 469/469 [00:10<00:00, 46.54it/s]
0 0.46340912513625926 0.8374666666666667 0.8877999782562256
--- display 9 wrong answers ------------------------------------------
[[12, tensor(7, device='cuda:0'), tensor(5, device='cuda:0')], [17, tensor(4, device='cuda:0'), tensor(2, device='cuda:0')], [23, tensor(9, device='cuda:0'), tensor(5, device='cuda:0')], [25, tensor(4, device='cuda:0'), tensor(6, device='cuda:0')], [42, tensor(3, device='cuda:0'), tensor(6, device='cuda:0')], [46, tensor(2, device='cuda:0'), tensor(6, device='cuda:0')], [49, tensor(2, device='cuda:0'), tensor(6, device='cuda:0')], [57, tensor(4, device='cuda:0'), tensor(6, device='cuda:0')], [66, tensor(2, device='cuda:0'), tensor(6, device='cuda:0')]]
[12, 17, 23, 25, 42, 46, 49, 57, 66]
torch.Size([9, 1, 28, 28])
--- display 9 correct answers ----------------------------------------
[[0, tensor(9, device='cuda:0'), tensor(9, device='cuda:0')], [1, tensor(2, device='cuda:0'), tensor(2, device='cuda:0')], [2, tensor(1, device='cuda:0'), tensor(1, device='cuda:0')], [3, tensor(1, device='cuda:0'), tensor(1, device='cuda:0')], [4, tensor(6, device='cuda:0'), tensor(6, device='cuda:0')], [5, tensor(1, device='cuda:0'), tensor(1, device='cuda:0')], [6, tensor(4, device='cuda:0'), tensor(4, device='cuda:0')], [7, tensor(6, device='cuda:0'), tensor(6, device='cuda:0')], [8, tensor(5, device='cuda:0'), tensor(5, device='cuda:0')]]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
--------------------------------------------------
Elapsed Time: 12.64216923713684[sec]

100%|██████████| 469/469 [00:10<00:00, 46.54it/s]

0 0.46340912513625926 0.8374666666666667 0.8877999782562256

--- display 9 wrong answers ------------------------------------------

[[12, tensor(7, device='cuda:0'), tensor(5, device='cuda:0')], [17, tensor(4, device='cuda:0'), tensor(2, device='cuda:0')], [23, tensor(9, device='cuda:0'), tensor(5, device='cuda:0')], [25, tensor(4, device='cuda:0'), tensor(6, device='cuda:0')], [42, tensor(3, device='cuda:0'), tensor(6, device='cuda:0')], [46, tensor(2, device='cuda:0'), tensor(6, device='cuda:0')], [49, tensor(2, device='cuda:0'), tensor(6, device='cuda:0')], [57, tensor(4, device='cuda:0'), tensor(6, device='cuda:0')], [66, tensor(2, device='cuda:0'), tensor(6, device='cuda:0')]]

[12, 17, 23, 25, 42, 46, 49, 57, 66]

torch.Size([9, 1, 28, 28])

--- display 9 correct answers ----------------------------------------

[[0, tensor(9, device='cuda:0'), tensor(9, device='cuda:0')], [1, tensor(2, device='cuda:0'), tensor(2, device='cuda:0')], [2, tensor(1, device='cuda:0'), tensor(1, device='cuda:0')], [3, tensor(1, device='cuda:0'), tensor(1, device='cuda:0')], [4, tensor(6, device='cuda:0'), tensor(6, device='cuda:0')], [5, tensor(1, device='cuda:0'), tensor(1, device='cuda:0')], [6, tensor(4, device='cuda:0'), tensor(4, device='cuda:0')], [7, tensor(6, device='cuda:0'), tensor(6, device='cuda:0')], [8, tensor(5, device='cuda:0'), tensor(5, device='cuda:0')]]

[0, 1, 2, 3, 4, 5, 6, 7, 8]

--------------------------------------------------

Elapsed Time: 12.64216923713684[sec]

■実行結果(epoch = 3).

100%|██████████| 469/469 [00:10<00:00, 44.76it/s]
0 0.4758336953500397 0.83515 0.8811999559402466
100%|██████████| 469/469 [00:09<00:00, 48.26it/s]
1 0.31819574741853607 0.8837833333333334 0.8960999846458435
100%|██████████| 469/469 [00:09<00:00, 48.05it/s]
2 0.2854099352326658 0.8958166666666667 0.899899959564209
--- display 9 wrong answers ------------------------------------------
[[17, tensor(4, device='cuda:0'), tensor(6, device='cuda:0')], [23, tensor(9, device='cuda:0'), tensor(5, device='cuda:0')], [25, tensor(4, device='cuda:0'), tensor(6, device='cuda:0')], [42, tensor(3, device='cuda:0'), tensor(6, device='cuda:0')], [43, tensor(7, device='cuda:0'), tensor(9, device='cuda:0')], [49, tensor(2, device='cuda:0'), tensor(6, device='cuda:0')], [66, tensor(2, device='cuda:0'), tensor(3, device='cuda:0')], [67, tensor(3, device='cuda:0'), tensor(4, device='cuda:0')], [68, tensor(9, device='cuda:0'), tensor(7, device='cuda:0')]]
[17, 23, 25, 42, 43, 49, 66, 67, 68]
torch.Size([9, 1, 28, 28])
--- display 9 correct answers ----------------------------------------
[[0, tensor(9, device='cuda:0'), tensor(9, device='cuda:0')], [1, tensor(2, device='cuda:0'), tensor(2, device='cuda:0')], [2, tensor(1, device='cuda:0'), tensor(1, device='cuda:0')], [3, tensor(1, device='cuda:0'), tensor(1, device='cuda:0')], [4, tensor(6, device='cuda:0'), tensor(6, device='cuda:0')], [5, tensor(1, device='cuda:0'), tensor(1, device='cuda:0')], [6, tensor(4, device='cuda:0'), tensor(4, device='cuda:0')], [7, tensor(6, device='cuda:0'), tensor(6, device='cuda:0')], [8, tensor(5, device='cuda:0'), tensor(5, device='cuda:0')]]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
--------------------------------------------------
Elapsed Time: 37.92949438095093[sec]

100%|██████████| 469/469 [00:10<00:00, 44.76it/s]

0 0.4758336953500397 0.83515 0.8811999559402466

100%|██████████| 469/469 [00:09<00:00, 48.26it/s]

1 0.31819574741853607 0.8837833333333334 0.8960999846458435

100%|██████████| 469/469 [00:09<00:00, 48.05it/s]

2 0.2854099352326658 0.8958166666666667 0.899899959564209

--- display 9 wrong answers ------------------------------------------

[[17, tensor(4, device='cuda:0'), tensor(6, device='cuda:0')], [23, tensor(9, device='cuda:0'), tensor(5, device='cuda:0')], [25, tensor(4, device='cuda:0'), tensor(6, device='cuda:0')], [42, tensor(3, device='cuda:0'), tensor(6, device='cuda:0')], [43, tensor(7, device='cuda:0'), tensor(9, device='cuda:0')], [49, tensor(2, device='cuda:0'), tensor(6, device='cuda:0')], [66, tensor(2, device='cuda:0'), tensor(3, device='cuda:0')], [67, tensor(3, device='cuda:0'), tensor(4, device='cuda:0')], [68, tensor(9, device='cuda:0'), tensor(7, device='cuda:0')]]

[17, 23, 25, 42, 43, 49, 66, 67, 68]

torch.Size([9, 1, 28, 28])

--- display 9 correct answers ----------------------------------------

[0, 1, 2, 3, 4, 5, 6, 7, 8]

--------------------------------------------------

Elapsed Time: 37.92949438095093[sec]

■以上の実行結果から, 以下のことが分かった.
① 例えば, epoch = 1 の場合, Fashion-MNIST のテスト画像の (index的に)12番目について,
“Sandal” と予想(tensor(5, device=’cuda:0′)) したが, “Sneaker” が正解(tensor(7, device=’cuda:0′)) との情報が得られた.

② また, 例えば, epoch = 3 の場合, Fashion-MNIST のテスト画像の (index的に)25番目について,
“Shirt” と予想(tensor(6, device=’cuda:0′)) したが, “Coat” が正解(tensor(4, device=’cuda:0′)) との情報が得られた.

③ なお, epoch = 1, 3 のいずれも, (index的に)0～8番目について, 予想と正解が一致しているとの情報が得られた.

■参照サイト
Adding a dimension to a tensor in PyTorch.
How to turn a list of tensor to tensor?
Fashion-MNIST

■参考書籍
現場で使える! PyTorch開発入門深層学習モデルの作成とアプリケーションへの実装 (AI & TECHNOLOGY)

2018年10月7日2018年10月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 112 の問題C（Pyramid), 問題D（Partition) を解いてみた.

■感想.
1. 問題D は, 時間内で, テストケース C030_scrambled を除いて, 通過したが, ロジック修正を, 自力で出来なかったため, コンテスト終了後, 解説を見て, ロジック修正した.
2. 問題C は, 時間内で, 外枠だけコーディングしたが, 問題の意図を理解できなかったので, コンテスト終了後, 再度解き直した.
3. 問題C は, テストケース in04.txt, in06.txt, in20.txt の Wrong Answer を, 解説見ても, 自力で修正できなかったので, 正解者のコーディングを参照したところ, N個のピラミッド情報で, ピラミッド高度に関する降順 sort が, 必要なことが分かった(※初回取得で, 高度 0 を取得させないようにするため)ので, ロジック修正した.
4. 個人的には, ここ最近, ABCコンテストの難易度が, かなり上昇気味に感じた, 復習がかなり大変となっている模様(汗).

本家のサイトABC 112 解説をご覧下さい.

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

// 解き直し.
// ABC 112 解説.
// https://img.atcoder.jp/abc112/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)

struct pyramid {
    int x;    // ピラミッドのx座標.
    int y;    // ピラミッドのy座標.
    LL  h;    // ピラミッドの高度.
};

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    vector<pyramid> v;
    FOR(i, 0, N) {
        pyramid p;
        cin >> p.x >> p.y >> p.h;
        v.push_back(p);
    }
    
    // 2. ピラミッドの高度に関して, 降順sort の ロジック追加.
    // テストケース in04.txt, in06.txt, in20.txt の Wrong Answer を, 自力で修正できなかったので, 
    // 正解者 の コーディングを参照したところ, 下記 3-1. の ロジックで, 
    // ピラミッドの高度 が 0 より大きいものが取れている必要があるとの情報が得られたため.
    sort(v.begin(), v.end(), [](const pyramid& x, const pyramid& y) {return x.h > y.h;});
    
    // 3. ピラミッド中心座標を計算.
    // 中心が, (pCx, pCy) だったとして, 全部調査してみる.
    int cx = 0;
    int cy = 0;
    LL  h  = 0LL;
    FOR(pCx, 0, 101) {
        FOR(pCy, 0, 101) {
            bool isCenter = true;
            LL lh = -1LL;
            for (auto &p : v) {
                // 3-1. とりあえず, 高さを抽出.
                if(lh == -1LL) {
                    lh = p.h + abs(p.x - pCx) + abs(p.y - pCy);
                    continue;
                }
                
                // 3-2. 抽出した高さが, 条件を満たすかを確認.
                // -> ピラミッド中心座標が確定すれば, (p.x, p.y) によらず, 高さが一定になるはず.
                LL lh2 = max(lh - abs(p.x - pCx) - abs(p.y - pCy), 0LL);
                if(p.h != lh2) {
                    isCenter = false;
                    break;
                }
                
            }
            // 3-3. 確定したピラミッド中心座標, 高度を保存.
            if(isCenter) {
                cx = pCx;
                cy = pCy;
                h  = lh;
                break;
            }
        }
    }

    // 4. 出力 ～ 後処理.
    cout << cx << " " << cy << " " << h << endl;
    return 0;
    
}

// 解き直し.

// ABC 112 解説.

// https://img.atcoder.jp/abc112/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)

struct pyramid {

int x; // ピラミッドのx座標.

int y; // ピラミッドのy座標.

LL h; // ピラミッドの高度.

};

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

vector<pyramid> v;

FOR(i, 0, N) {

pyramid p;

cin >> p.x >> p.y >> p.h;

v.push_back(p);

}

// 2. ピラミッドの高度に関して, 降順sort のロジック追加.

// テストケース in04.txt, in06.txt, in20.txt の Wrong Answer を, 自力で修正できなかったので,

// 正解者のコーディングを参照したところ, 下記 3-1. のロジックで,

// ピラミッドの高度が 0 より大きいものが取れている必要があるとの情報が得られたため.

sort(v.begin(), v.end(), [](const pyramid& x, const pyramid& y) {return x.h > y.h;});

// 3. ピラミッド中心座標を計算.

// 中心が, (pCx, pCy) だったとして, 全部調査してみる.

int cx = 0;

int cy = 0;

LL h = 0LL;

FOR(pCx, 0, 101) {

FOR(pCy, 0, 101) {

bool isCenter = true;

LL lh = -1LL;

for (auto &p : v) {

// 3-1. とりあえず, 高さを抽出.

if(lh == -1LL) {

lh = p.h + abs(p.x - pCx) + abs(p.y - pCy);

continue;

}

// 3-2. 抽出した高さが, 条件を満たすかを確認.

// -> ピラミッド中心座標が確定すれば, (p.x, p.y) によらず, 高さが一定になるはず.

LL lh2 = max(lh - abs(p.x - pCx) - abs(p.y - pCy), 0LL);

if(p.h != lh2) {

isCenter = false;

break;

}

// 3-3. 確定したピラミッド中心座標, 高度を保存.

if(isCenter) {

cx = pCx;

cy = pCy;

h = lh;

break;

}

// 4. 出力～後処理.

cout << cx << " " << cy << " " << h << endl;

return 0;

}

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

// 解き直し.
// ABC 112 解説.
// https://img.atcoder.jp/abc112/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)

int main() {
    
    // 1. 入力情報取得.
    LL N, M;
    cin >> N >> M;
    // 2. 最大公約数を計算.
    LL ans = 1;
    if(M % N == 0) ans = M / N;
    if(M % N != 0) {
        LL LGCD = 1;
        // C030_scrambled が通過できなかった.
        // FOR(i, 2, 100001) {
        LL LIMIT = M / N;
        FOR(i, 2, LIMIT) {
            if(M % i == 0) LGCD = i;
            if(LGCD * N <= M) ans = max(ans, LGCD);
        }
    }
    
    // 3. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;

}

// 解き直し.

// ABC 112 解説.

// https://img.atcoder.jp/abc112/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)

int main() {

// 1. 入力情報取得.

LL N, M;

cin >> N >> M;

// 2. 最大公約数を計算.

LL ans = 1;

if(M % N == 0) ans = M / N;

if(M % N != 0) {

LL LGCD = 1;

// C030_scrambled が通過できなかった.

// FOR(i, 2, 100001) {

LL LIMIT = M / N;

FOR(i, 2, LIMIT) {

if(M % i == 0) LGCD = i;

if(LGCD * N <= M) ans = max(ans, LGCD);

}

// 3. 出力～後処理.

cout << ans << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 112

2018年10月6日2018年10月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 066 の問題C（pushpush）を解いてみた.

■感想.
1. 数列の要素を, 問題文の操作で並び順を変えると, 膨大な計算量(O(nの2乗)) が必要となるが, 規則性を見つけると, 計算量が O(n) の 3倍程度まで, 削減できる点が, 面白いと感じた.
2. 解説を読んだところ, 標準ライブラリ std::deque があるとのことで, 大変参考になったと思う.
3. 標準ライブラリ std::deque を使ってみたところ, 実装が, よりコンパクトにまとまって, びっくりした(汗).

本家のサイトABC066 / ARC077 解説をご覧下さい.

■C++版プログラム.

#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. 入力情報取得.
    int N;
    cin >> N;
    LL A[N] = {};
    FOR(i, 0, N) cin >> A[i];
    
    // 2. 問題文の操作した数列を保存.
    // 例)
    // 1 -> 1
    // 1 2 -> 2 1
    // 1 2 3 -> 3 1 2
    // 1 2 3 4 -> 4 2 1 3
    // 1 2 3 4 5 -> 5 3 1 2 4
    // -> 以上のことから, 
    // A の i番目の要素 は,  
    // B の (N / 2) + sign * ((i + 1)/ 2)番目 に, 対応することが分かった.
    // 但し, 符合 sign の 初期値 は, N の 偶奇 で 分岐.
    LL B[N] = {};
    int sign = ((N % 2 == 0) ? (-1) : 1);
    FOR(i, 0, N) {
        sign *= (-1);
        int index = (N / 2);
        index += (sign * ((i + 1) / 2));
        // cout << index << endl;
        B[index] = A[i];
    }
    
    // 3. 出力 ～ 後処理.
    FOR(i, 0, N) cout << B[i] << " ";
    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. 入力情報取得.

int N;

cin >> N;

LL A[N] = {};

FOR(i, 0, N) cin >> A[i];

// 2. 問題文の操作した数列を保存.

// 例)

// 1 -> 1

// 1 2 -> 2 1

// 1 2 3 -> 3 1 2

// 1 2 3 4 -> 4 2 1 3

// 1 2 3 4 5 -> 5 3 1 2 4

// -> 以上のことから,

// A の i番目の要素は,

// B の (N / 2) + sign * ((i + 1)/ 2)番目に, 対応することが分かった.

// 但し, 符合 sign の初期値は, N の偶奇で分岐.

LL B[N] = {};

int sign = ((N % 2 == 0) ? (-1) : 1);

FOR(i, 0, N) {

sign *= (-1);

int index = (N / 2);

index += (sign * ((i + 1) / 2));

// cout << index << endl;

B[index] = A[i];

}

// 3. 出力～後処理.

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

return 0;

}

■C++版プログラム(std::dequeを使った場合).

// 解き直し.
// std::deque を 使って, 実装した版.
// ABC066 / ARC077 解説.
// https://atcoder.jp/img/arc077/editorial.pdf
#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. 入力情報取得.
    int N;
    cin >> N;
    LL A[N] = {};
    FOR(i, 0, N) cin >> A[i];
    
    // 2. 問題文の操作した数列を保存.
    // 例)
    // 1 -> 1
    // 1 2 -> 2 1
    // 1 2 3 -> 3 1 2
    // 1 2 3 4 -> 4 2 1 3
    // 1 2 3 4 5 -> 5 3 1 2 4
    // 
    // 解説通り.
    // i(※0 ～ N - 1) と N の 偶奇 を確認して, 
    // 一致する   … 数列A の要素を, deque の 末尾 に追加.
    // 一致しない … 数列A の要素を, deque の 先頭 に追加.
    deque<LL> dq;
    FOR(i, 0, N) {
        if((N - i) % 2 == 0) dq.push_back(A[i]);
        else                 dq.push_front(A[i]);
    }
    
    // 3. 出力 ～ 後処理.
    for (auto &p : dq) cout << p << " ";
    return 0;
    
}

// 解き直し.

// std::deque を使って, 実装した版.

// ABC066 / ARC077 解説.

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

#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. 入力情報取得.

int N;

cin >> N;

LL A[N] = {};

FOR(i, 0, N) cin >> A[i];

// 2. 問題文の操作した数列を保存.

// 例)

// 1 -> 1

// 1 2 -> 2 1

// 1 2 3 -> 3 1 2

// 1 2 3 4 -> 4 2 1 3

// 1 2 3 4 5 -> 5 3 1 2 4

// 解説通り.

// i(※0 ～ N - 1) と N の偶奇を確認して,

// 一致する … 数列A の要素を, deque の末尾に追加.

// 一致しない … 数列A の要素を, deque の先頭に追加.

deque<LL> dq;

FOR(i, 0, N) {

if((N - i) % 2 == 0) dq.push_back(A[i]);

else dq.push_front(A[i]);

}

// 3. 出力～後処理.

for (auto &p : dq) cout << p << " ";

return 0;

}

■参照サイト
AtCoder Beginner Contest 066

2018年10月4日

PyTorch の動作確認をしてみた（６）

1. 環境は、Window 10 Home (64bit) 上で行った。

2. Anaconda3 (64bit) – Spyder上で、動作確認を行った。

3. python のバージョンは、python 3.6.5 である。

4. pytorch のバージョンは、pytorch 0.4.1 である。

5. GPU は, NVIDIA社の GeForce GTX 1050 である。

6. CPU は, Intel社の Core(TM) i7-7700HQ である。

今回確認した内容は、現場で使える! PyTorch開発入門深層学習モデルの作成とアプリケーションへの実装 (AI & TECHNOLOGY) の 4.2.2 CNNの構築と学習(P.067 – P.071) である。
Fashion-MNIST を使った, CNN の画像分類について書かれていたので, 少し動作確認を行った.
また, tqdm の使い方も確認できた.

※プログラムの詳細は、書籍を参考(P.067 – P.071)にして下さい。

■Fashion-MNISTの学習(GPU版).

# tqdm を 下記コマンドで, install.
# conda install -c conda-forge tqdm
# 1. library import.
from __future__ import print_function
import torch
from torchvision.datasets import FashionMNIST
from torchvision import transforms
from torch.utils.data import DataLoader
import os, time
from torch import nn, optim
from tqdm import tqdm

# 2. declare functions.
# 2-1. A layer that stretches a Tensor of the (H, C, H, W) type to (N, C * H * W).
# required to pass the output of convolution layer to MLP.
class FlattenLayer(nn.Module):
    def forward(self, x):
        sizes = x.size()
        return x.view(sizes[0], - 1)

～(略)～
        n, n_acc = 0, 0
        for i ,(xx, yy) in tqdm(enumerate(train_loader), total=len(train_loader)):
            xx, yy = xx.to(device), yy.to(device)
～(略)～

# 5. execute training.
net.to("cuda:0")
train_net(net, train_loader, test_loader, n_iter=20, device="cuda:0")

# 6. display processing time.
end = time.time()
print('--------------------------------------------------')
print('Elapsed Time: ' + str(end - start) + "[sec]")

# tqdm を下記コマンドで, install.

# conda install -c conda-forge tqdm

# 1. library import.

from __future__ import print_function

import torch

from torchvision.datasets import FashionMNIST

from torchvision import transforms

from torch.utils.data import DataLoader

import os, time

from torch import nn, optim

from tqdm import tqdm

# 2. declare functions.

# 2-1. A layer that stretches a Tensor of the (H, C, H, W) type to (N, C * H * W).

# required to pass the output of convolution layer to MLP.

class FlattenLayer(nn.Module):

def forward(self, x):

sizes = x.size()

return x.view(sizes[0], - 1)

～(略)～

n, n_acc = 0, 0

for i ,(xx, yy) in tqdm(enumerate(train_loader), total=len(train_loader)):

xx, yy = xx.to(device), yy.to(device)

～(略)～

# 5. execute training.

net.to("cuda:0")

train_net(net, train_loader, test_loader, n_iter=20, device="cuda:0")

# 6. display processing time.

end = time.time()

print('--------------------------------------------------')

print('Elapsed Time: ' + str(end - start) + "[sec]")

■実行結果(GPU版).

■Fashion-MNISTの学習(CPU版).

# -*- coding: utf-8 -*-
# tqdm を 下記コマンドで, install.
# conda install -c conda-forge tqdm
# 1. library import.
from __future__ import print_function
import torch
from torchvision.datasets import FashionMNIST
from torchvision import transforms
from torch.utils.data import DataLoader
import os, time
from torch import nn, optim
from tqdm import tqdm

# 2. declare functions.
# 2-1. A layer that stretches a Tensor of the (H, C, H, W) type to (N, C * H * W).
# required to pass the output of convolution layer to MLP.
class FlattenLayer(nn.Module):
    def forward(self, x):
        sizes = x.size()
        return x.view(sizes[0], - 1)

～(略)～
        n, n_acc = 0, 0
        for i ,(xx, yy) in tqdm(enumerate(train_loader), total=len(train_loader)):
            xx, yy = xx.to(device), yy.to(device)
～(略)～

# 5. execute training.
train_net(net, train_loader, test_loader, n_iter=20)

# 6. display processing time.
end = time.time()
print('--------------------------------------------------')
print('Elapsed Time: ' + str(end - start) + "[sec]")

# -*- coding: utf-8 -*-

# tqdm を下記コマンドで, install.

# conda install -c conda-forge tqdm

# 1. library import.

from __future__ import print_function

import torch

from torchvision.datasets import FashionMNIST

from torchvision import transforms

from torch.utils.data import DataLoader

import os, time

from torch import nn, optim

from tqdm import tqdm

# 2. declare functions.

# 2-1. A layer that stretches a Tensor of the (H, C, H, W) type to (N, C * H * W).

# required to pass the output of convolution layer to MLP.

class FlattenLayer(nn.Module):

def forward(self, x):

sizes = x.size()

return x.view(sizes[0], - 1)

～(略)～

n, n_acc = 0, 0

for i ,(xx, yy) in tqdm(enumerate(train_loader), total=len(train_loader)):

xx, yy = xx.to(device), yy.to(device)

～(略)～

# 5. execute training.

train_net(net, train_loader, test_loader, n_iter=20)

# 6. display processing time.

end = time.time()

print('--------------------------------------------------')

print('Elapsed Time: ' + str(end - start) + "[sec]")

■実行結果(CPU版).

■以上の実行結果から, 以下のことが分かった.
① 処理速度.
実行結果(GPU版): Elapsed Time: 189.46908950805664[sec]
実行結果(CPU版): Elapsed Time: 1290.8199858665466[sec]
-> GPU版が CPU版に比べて, 約6.8倍早く処理できたことが分かった.

② tqdm の使い方.
著書上の tqdm.tqdm(enumerate～(略)～では, 動作しなかったので, tqdm(enumerate～(略)～で確認した.

■参考書籍
現場で使える! PyTorch開発入門深層学習モデルの作成とアプリケーションへの実装 (AI & TECHNOLOGY)

2018年9月30日

PyTorch の動作確認をしてみた（５）

1. 環境は、Window 10 Home (64bit) 上で行った。

2. Anaconda3 (64bit) – Spyder上で、動作確認を行った。

3. python のバージョンは、python 3.6.5 である。

4. pytorch のバージョンは、pytorch 0.4.1 である。

5. GPU は, NVIDIA社の GeForce GTX 1050 である。

6. CPU は, Intel社の Core(TM) i7-7700HQ である。

今回確認した内容は、現場で使える! PyTorch開発入門深層学習モデルの作成とアプリケーションへの実装 (AI & TECHNOLOGY) の 3.3.1 Dropoutによる正則化(P.052 – P.055) である。
Dropoutによる正則化について書かれていたので, 少し動作確認を行った.

※プログラムの詳細は、書籍を参考(P.052 – P.055)にして下さい。

■Dropout無し.

# -*- coding: utf-8 -*-
# 1. library import.
from __future__ import print_function
import torch
from torch import nn, optim
import matplotlib.pyplot as plt
from sklearn.datasets import load_digits
from torch.utils.data import TensorDataset, DataLoader
from sklearn.model_selection import train_test_split
import time

# 2. build a network.
start = time.time()
l = 100
net = nn.Sequential(
        nn.Linear(64, l),
        nn.ReLU(),
        nn.Linear(l, l),
        nn.ReLU(),
        nn.Linear(l, l),
        nn.ReLU(),
        nn.Linear(l, l),
        nn.ReLU(),
        nn.Linear(l, 10)
    )

～(略)～

# 9. display graph.
plt.title('not Regularization')
plt.plot(train_losses, label='train')
plt.plot(test_losses, label='test')
plt.legend(loc='upper right')

# 10. classify digits data.
end = time.time()
print('--------------------------------------------------')
print('Elapsed Time: ' + str(end - start) + "[sec]")

# -*- coding: utf-8 -*-

# 1. library import.

from __future__ import print_function

import torch

from torch import nn, optim

import matplotlib.pyplot as plt

from sklearn.datasets import load_digits

from torch.utils.data import TensorDataset, DataLoader

from sklearn.model_selection import train_test_split

import time

# 2. build a network.

start = time.time()

l = 100

net = nn.Sequential(

nn.Linear(64, l),

nn.ReLU(),

nn.Linear(l, l),

nn.ReLU(),

nn.Linear(l, l),

nn.ReLU(),

nn.Linear(l, l),

nn.ReLU(),

nn.Linear(l, 10)

)

～(略)～

# 9. display graph.

plt.title('not Regularization')

plt.plot(train_losses, label='train')

plt.plot(test_losses, label='test')

plt.legend(loc='upper right')

# 10. classify digits data.

end = time.time()

print('--------------------------------------------------')

print('Elapsed Time: ' + str(end - start) + "[sec]")

■実行結果(Dropout無し).

■Dropout有り.

# -*- coding: utf-8 -*-
# 1. library import.
from __future__ import print_function
import torch
from torch import nn, optim
import matplotlib.pyplot as plt
from sklearn.datasets import load_digits
from torch.utils.data import TensorDataset, DataLoader
from sklearn.model_selection import train_test_split
import time

# 2. build a network.
start = time.time()
l = 100
r = 0.5
net = nn.Sequential(
        nn.Linear(64, l),
        nn.ReLU(),
        nn.Dropout(r),
        nn.Linear(l, l),
        nn.ReLU(),
        nn.Dropout(r),
        nn.Linear(l, l),
        nn.ReLU(),
        nn.Dropout(r),
        nn.Linear(l, l),
        nn.ReLU(),
        nn.Dropout(r),
        nn.Linear(l, 10)
    )

～(略)～

# 9. display graph.
t = 'Regularization (r=' + str(r) + ')'
plt.title(t)
plt.plot(train_losses, label='train')
plt.plot(test_losses, label='test')
plt.legend(loc='upper right')

# 10. classify digits data.
end = time.time()
print('--------------------------------------------------')
print('Elapsed Time: ' + str(end - start) + "[sec]")

# -*- coding: utf-8 -*-

# 1. library import.

from __future__ import print_function

import torch

from torch import nn, optim

import matplotlib.pyplot as plt

from sklearn.datasets import load_digits

from torch.utils.data import TensorDataset, DataLoader

from sklearn.model_selection import train_test_split

import time

# 2. build a network.

start = time.time()

l = 100

r = 0.5

net = nn.Sequential(

nn.Linear(64, l),

nn.ReLU(),

nn.Dropout(r),

nn.Linear(l, l),

nn.ReLU(),

nn.Dropout(r),

nn.Linear(l, l),

nn.ReLU(),

nn.Dropout(r),

nn.Linear(l, l),

nn.ReLU(),

nn.Dropout(r),

nn.Linear(l, 10)

)

～(略)～

# 9. display graph.

t = 'Regularization (r=' + str(r) + ')'

plt.title(t)

plt.plot(train_losses, label='train')

plt.plot(test_losses, label='test')

plt.legend(loc='upper right')

# 10. classify digits data.

end = time.time()

print('--------------------------------------------------')

print('Elapsed Time: ' + str(end - start) + "[sec]")

■実行結果①(Dropout有り, r = 0.3).

■実行結果②(Dropout有り, r = 0.5 ※書籍と同じ).

■実行結果③(Dropout有り, r = 0.7).

■以上の実行結果から, 以下のことが分かった.
① Dropout を設定しないと, 過学習が発生していることが分かった.

② Dropout を設定すると, 過学習を抑制できる分かった.

③ Dropout に設定する r の値を変えると, 表示されるグラフも大きく変わってくることが分かった.

■参考書籍
現場で使える! PyTorch開発入門深層学習モデルの作成とアプリケーションへの実装 (AI & TECHNOLOGY)

2018年9月29日2018年9月29日

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

C++の練習を兼ねて, AtCoder Beginner Contest 068 の問題D（Decrease (Contestant ver.)）を解いてみた.

■感想.
1. 問題を読んでも, 方針が全く見えなかった.
2. 解説を読んだところ, 目から鱗で, なるほど, と感心させられ, 大変勉強になったと思う.

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

■C++版プログラム.

// 解き直し.
// AtCoder Regular Contest 079 Editorial
// https://atcoder.jp/img/arc079/editorial.pdf
#include <iostream>

using namespace std;

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

typedef long long LL;

int main() {
    
    // 1. 入力情報取得.
    LL K;
    cin >> K;
    
    // 2. 数列 0, 1, ..., N - 1 を 考え, 
    // 1, 2, ..., N, 1, 2, ..., N, の 順番で, 逆操作を行えばよいとのこと.
    // 2-1. N = 50 として, 確認することにする.
    int N = 50;
    LL sequence[N] = {};
    FOR(i, 0, N) sequence[i] = i;
    
    // 2-2. K回繰り返すには...
    
    // 試しに, N = 10 と置いて, 10回繰り返す.
    // -> 0回目 と比べて, 各要素 が 1ずつ増加している.
    // 0回目 …  0  1  2  3  4  5  6  7  8  9
    // 1回目 … 10  0  1  2  3  4  5  6  7  8
    // 2回目 …  9 10  0  1  2  3  4  5  6  7
    // ...
    // 9回目 …  2  3  4  5  6  7  8  9 10  0
    // 10回目 …  1  2  3  4  5  6  7  8  9 10 <--- 0回目 から, 全体が, 1ずつ増加している.
    // N = 10;
    // int loop = 0;
    // int index = 0;
    // while(loop < N) {
    //     FOR(i, 0, N) {
    //         if(index == i) sequence[i] += N;
    //         else           sequence[i]--;
    //     }
    //     loop++;
    //     index++;
    //     index %= N;
    // }
    // FOR(i, 0, N) cout << sequence[i] << " ";
    
    // 2-3. 数列の base を作り, 全体 を increment. 
    // K が, 非常に大きな数なので, K を N で 割ったときの商, 余りを計算してみる.
    LL quotient = K / N;
    LL remainder = K % N;
    
    // base.
    int index = 0;
    while(index < remainder) {
        FOR(i, 0, N) {
            if(index == i) sequence[i] += N;
            else           sequence[i]--;
        }
        index++;
    }
    
    // increment.
    FOR(i, 0, N) sequence[i] += quotient;

    // 3. 出力 ～ 後処理.
    cout << N << endl;
    FOR(i, 0, N) cout << sequence[i] << " ";
    return 0;
    
}

// 解き直し.

// AtCoder Regular Contest 079 Editorial

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

#include <iostream>

using namespace std;

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

typedef long long LL;

int main() {

// 1. 入力情報取得.

LL K;

cin >> K;

// 2. 数列 0, 1, ..., N - 1 を考え,

// 1, 2, ..., N, 1, 2, ..., N, の順番で, 逆操作を行えばよいとのこと.

// 2-1. N = 50 として, 確認することにする.

int N = 50;

LL sequence[N] = {};

FOR(i, 0, N) sequence[i] = i;

// 2-2. K回繰り返すには...

// 試しに, N = 10 と置いて, 10回繰り返す.

// -> 0回目と比べて, 各要素が 1ずつ増加している.

// 0回目 … 0 1 2 3 4 5 6 7 8 9

// 1回目 … 10 0 1 2 3 4 5 6 7 8

// 2回目 … 9 10 0 1 2 3 4 5 6 7

// ...

// 9回目 … 2 3 4 5 6 7 8 9 10 0

// 10回目 … 1 2 3 4 5 6 7 8 9 10 <--- 0回目から, 全体が, 1ずつ増加している.

// N = 10;

// int loop = 0;

// int index = 0;

// while(loop < N) {

// FOR(i, 0, N) {

// if(index == i) sequence[i] += N;

// else sequence[i]--;

// }

// loop++;

// index++;

// index %= N;

// }

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

// 2-3. 数列の base を作り, 全体を increment.

// K が, 非常に大きな数なので, K を N で割ったときの商, 余りを計算してみる.

LL quotient = K / N;

LL remainder = K % N;

// base.

int index = 0;

while(index < remainder) {

FOR(i, 0, N) {

if(index == i) sequence[i] += N;

else sequence[i]--;

}

index++;

}

// increment.

FOR(i, 0, N) sequence[i] += quotient;

// 3. 出力～後処理.

cout << N << endl;

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

return 0;

}

■参照サイト
AtCoder Beginner Contest 068

個人用メモ帳

投稿

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

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

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 064 の問題D（Insertion) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 028 の問題B（Removing Blocks) を解いてみた.

PyTorch の動作確認をしてみた（７）

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

C++の練習を兼ねて, AtCoder Beginner Contest 112 の問題C（Pyramid), 問題D（Partition) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 066 の問題C（pushpush）を解いてみた.

PyTorch の動作確認をしてみた（６）

PyTorch の動作確認をしてみた（５）

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

C++の練習を兼ねて, AtCoder Beginner Contest 068 の問題D（Decrease (Contestant ver.)）を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 064 の 問題D（Insertion) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 028 の 問題B（Removing Blocks) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 112 の 問題C（Pyramid), 問題D（Partition) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 066 の 問題C（pushpush）を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 068 の 問題D（Decrease (Contestant ver.)）を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 064 の問題D（Insertion) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 028 の問題B（Removing Blocks) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 112 の問題C（Pyramid), 問題D（Partition) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 066 の問題C（pushpush）を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 068 の問題D（Decrease (Contestant ver.)）を解いてみた.