8月, 2018 | 個人用メモ帳

2018年8月30日2018年9月3日

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

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

■感想.
1. 結構解ききるまでに, 結構苦労した.
2. 濃度の上限 100 × E / (100 + E) に関するバグを修正するのに, 時間かかってしまった.
3. テストケース 01.txt が, 通過しなかったので, 試行錯誤の結果, 濃度上限が, 0% のパターンと推定して,
砂糖水が, 100 × A [g] あると仮定して, 漸く全テストケースを通過した.

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

■C++版プログラム

#include <iostream>

using namespace std;

#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define max(x, y) ((x > y) ? x : y)

int main() {
    
    // 1. 入力情報取得.
    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;
    
    // 2. 濃度の最も高い砂糖水を探索.
    int sugar = 0;
    int sugarWater = 0;
    double maxConcentration = 0;
    // double limitConcentration = 100 * E / (100 + E);
    // -> 整数値(limitConcentration = 35) となるバグ(※コーディング誤り)を確認した.
    
    // 以下のように修正して, limitConcentration = (100 * 55) / (100 + 55) = 35.4839 を確認できた.
    double limitConcentration = 100.0 * E / (100.0 + E);
    //cout << "limitConcentration = " << limitConcentration << endl;
    
    // 操作1 の 最大回数.
    int aMax = F / (100 * A);
    FOR(a, 0, aMax + 1) {
        // 操作2 の 最大回数.
        int bMax = (F - (100 * A * a)) / (100 * B);
        FOR(b, 0, bMax + 1) {
            if(a == 0 && b == 0) continue;
            // 操作3 の 最大回数.
            int cMax = (F - (100 * A * a) - (100 * B * b)) / C;
            FOR(c, 0, cMax + 1) {
                // 操作4 の 最大回数.
                int dMax = (F - (100 * A * a) - (100 * B * b) - C * c) / D;
                FOR(d, 0, dMax + 1) {
                    // 濃度計算.
                    double concentration = 0.0;
                    int sg  = C * c + D * d;
                    int sgw = 100 * A * a + 100 * B * b + C * c + D * d;
                    
                    // 2-1. 砂糖の質量を加算し, 100倍.
                    concentration += sg;
                    concentration *= 100;
                    
                    // 2-2. 砂糖水の質量で除算.
                    concentration /= sgw;
                    
                    // 2-3. 過去の最高濃度と比較し, 更新.
                    // ビーカーの中に砂糖を解け残らせない … concentration <= limitConcentration
                    // 砂糖水の質量上限は, F[g] … sgw <= F
                    // 
                    // なぜか, 入力例) 17 19 22 26 55 2802 の 場合に, 
                    // a = 1, b = 0, c = 7, d = 29 で, 探索が止まる(本来は, dMax = 36 なので, d = 30 も 調査対象).
                    // -> 本件バグは, limitConcentration = (100 * 55) / (100 + 55) = 35 と計算されていたことが原因.
                    if(concentration > maxConcentration && concentration <= limitConcentration && sgw <= F) {
                        maxConcentration = concentration;
                        sugar = sg;
                        sugarWater = sgw;
                    }
                }
            }
        }
    }
    
    // 3. 出力 ～ 後処理.
    // cout << sugarWater << " " << sugar << endl;
    // テストケース 01.txt が, 通過出来なかったので, max(sugarWater, 100 * A) に置き換えた.
    cout << max(sugarWater, 100 * A) << " " << sugar << endl;
    return 0;
    
}

#include <iostream>

using namespace std;

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

#define max(x, y) ((x > y) ? x : y)

int main() {

// 1. 入力情報取得.

int A, B, C, D, E, F;

cin >> A >> B >> C >> D >> E >> F;

// 2. 濃度の最も高い砂糖水を探索.

int sugar = 0;

int sugarWater = 0;

double maxConcentration = 0;

// double limitConcentration = 100 * E / (100 + E);

// -> 整数値(limitConcentration = 35) となるバグ(※コーディング誤り)を確認した.

// 以下のように修正して, limitConcentration = (100 * 55) / (100 + 55) = 35.4839 を確認できた.

double limitConcentration = 100.0 * E / (100.0 + E);

//cout << "limitConcentration = " << limitConcentration << endl;

// 操作1 の最大回数.

int aMax = F / (100 * A);

FOR(a, 0, aMax + 1) {

// 操作2 の最大回数.

int bMax = (F - (100 * A * a)) / (100 * B);

FOR(b, 0, bMax + 1) {

if(a == 0 && b == 0) continue;

// 操作3 の最大回数.

int cMax = (F - (100 * A * a) - (100 * B * b)) / C;

FOR(c, 0, cMax + 1) {

// 操作4 の最大回数.

int dMax = (F - (100 * A * a) - (100 * B * b) - C * c) / D;

FOR(d, 0, dMax + 1) {

// 濃度計算.

double concentration = 0.0;

int sg = C * c + D * d;

int sgw = 100 * A * a + 100 * B * b + C * c + D * d;

// 2-1. 砂糖の質量を加算し, 100倍.

concentration += sg;

concentration *= 100;

// 2-2. 砂糖水の質量で除算.

concentration /= sgw;

// 2-3. 過去の最高濃度と比較し, 更新.

// ビーカーの中に砂糖を解け残らせない … concentration <= limitConcentration

// 砂糖水の質量上限は, F[g] … sgw <= F

// なぜか, 入力例) 17 19 22 26 55 2802 の場合に,

// a = 1, b = 0, c = 7, d = 29 で, 探索が止まる(本来は, dMax = 36 なので, d = 30 も調査対象).

// -> 本件バグは, limitConcentration = (100 * 55) / (100 + 55) = 35 と計算されていたことが原因.

if(concentration > maxConcentration && concentration <= limitConcentration && sgw <= F) {

maxConcentration = concentration;

sugar = sg;

sugarWater = sgw;

}

// 3. 出力～後処理.

// cout << sugarWater << " " << sugar << endl;

// テストケース 01.txt が, 通過出来なかったので, max(sugarWater, 100 * A) に置き換えた.

cout << max(sugarWater, 100 * A) << " " << sugar << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 074

2018年8月27日2018年9月3日

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

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

■感想.
問題のタイトル的に, 面白そうな問題だったので, 解いてみた.

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

■C++版プログラム

#include <iostream>
#include <string>

using namespace std;

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

// 指定地点(i, j) の周囲に配置されている地雷の個数(上下左右斜め方向)をカウント.
// @param i: (行方向)i番目.
// @param j: (列方向)j番目.
// @param a[]: マス目.
// @return: 地雷の個数.
int countMines(int i, int j, string a[]) {
    const char SHARP_SIGN = '#';
    int ret = 0;
    if(a[i - 1][j - 1] == SHARP_SIGN) ret++;    // 左上.
    if(a[i - 1][j]     == SHARP_SIGN) ret++;    // 上.
    if(a[i - 1][j + 1] == SHARP_SIGN) ret++;    // 右上.
    if(a[i][j - 1]     == SHARP_SIGN) ret++;    // 左.
    if(a[i][j + 1]     == SHARP_SIGN) ret++;    // 右.
    if(a[i + 1][j - 1] == SHARP_SIGN) ret++;    // 左下.
    if(a[i + 1][j]     == SHARP_SIGN) ret++;    // 下.
    if(a[i + 1][j + 1] == SHARP_SIGN) ret++;    // 右下.
    return ret;
}

int main() {
    
    // 1. 入力情報取得.
    int H, W;
    cin >> H >> W;
    // 調査対象のマス目の外側を, '$' で囲む.
    // 例)
    // [入力値]
    // .....
    // .#.#.
    // .....
    // 
    // ↓
    // 
    // ['$'で囲んだ状態]
    // $$$$$$$
    // $.....$
    // $.#.#.$
    // $.....$
    // $$$$$$$
    
    const char DOLLAR_SIGN = '$';
    const char SHARP_SIGN = '#';
    
    string a;
    FOR(i, 0, W + 2) a += DOLLAR_SIGN;
    
    string S[H + 2] = {};
    S[0] = a;
    S[H + 1] = a;
    FOR(i, 1, H + 1) {
        string s;
        cin >> s;
        S[i] = (DOLLAR_SIGN + s + DOLLAR_SIGN);
    }
    
    // 2. マス目を一つ一つ調べ, '#' の個数を数える.
    // 出力用のマス目は, シャープ記号で初期化しておく.
    string b;
    FOR(i, 0, W) b += SHARP_SIGN;
    string O[H] = {};
    FOR(i, 0, H) O[i] = b;
    
    // 3. 上下左右斜め の 八方向でカウント.
    FOR(i, 1, H + 1) FOR(j, 1, W + 1) if(S[i][j] != '#') O[i - 1][j - 1] = (countMines(i, j, S) + '0');
    
    // 4. 出力 ～ 後処理.
    FOR(i, 0, H) cout << O[i] << endl;
    return 0;
    
}

#include <iostream>

#include <string>

using namespace std;

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

// 指定地点(i, j) の周囲に配置されている地雷の個数(上下左右斜め方向)をカウント.

// @param i: (行方向)i番目.

// @param j: (列方向)j番目.

// @param a[]: マス目.

// @return: 地雷の個数.

int countMines(int i, int j, string a[]) {

const char SHARP_SIGN = '#';

int ret = 0;

if(a[i - 1][j - 1] == SHARP_SIGN) ret++; // 左上.

if(a[i - 1][j] == SHARP_SIGN) ret++; // 上.

if(a[i - 1][j + 1] == SHARP_SIGN) ret++; // 右上.

if(a[i][j - 1] == SHARP_SIGN) ret++; // 左.

if(a[i][j + 1] == SHARP_SIGN) ret++; // 右.

if(a[i + 1][j - 1] == SHARP_SIGN) ret++; // 左下.

if(a[i + 1][j] == SHARP_SIGN) ret++; // 下.

if(a[i + 1][j + 1] == SHARP_SIGN) ret++; // 右下.

return ret;

}

int main() {

// 1. 入力情報取得.

int H, W;

cin >> H >> W;

// 調査対象のマス目の外側を, '$' で囲む.

// 例)

// [入力値]

// .....

// .#.#.

// .....

// ↓

// ['$'で囲んだ状態]

// $$$$$$$

// $.....$

// $.#.#.$

// $.....$

// $$$$$$$

const char DOLLAR_SIGN = '$';

const char SHARP_SIGN = '#';

string a;

FOR(i, 0, W + 2) a += DOLLAR_SIGN;

string S[H + 2] = {};

S[0] = a;

S[H + 1] = a;

FOR(i, 1, H + 1) {

string s;

cin >> s;

S[i] = (DOLLAR_SIGN + s + DOLLAR_SIGN);

}

// 2. マス目を一つ一つ調べ, '#' の個数を数える.

// 出力用のマス目は, シャープ記号で初期化しておく.

string b;

FOR(i, 0, W) b += SHARP_SIGN;

string O[H] = {};

FOR(i, 0, H) O[i] = b;

// 3. 上下左右斜めの八方向でカウント.

FOR(i, 1, H + 1) FOR(j, 1, W + 1) if(S[i][j] != '#') O[i - 1][j - 1] = (countMines(i, j, S) + '0');

// 4. 出力～後処理.

FOR(i, 0, H) cout << O[i] << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 075

2018年8月25日2018年9月3日

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

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

■感想.
時間内に解答出来なかったので, 解説見て解き直ししたところ, “連続する K 本のろうそくに火を付けるのが最適” との記述があり,
なるほどと感心してしまった.
※そのような発想が出てこなかった(汗), とはいえ, 非常に勉強になったので良かったと思う.

本家のサイトABC #107 / ARC #101 Editorialをご覧下さい。

■C++版プログラム

// 解き直し.
// ABC #107 / ARC #101 Editorial
// https://img.atcoder.jp/arc101/editorial.pdf
#include <iostream>

using namespace std;

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

typedef long long LL;

int main() {
    
    // 1. 入力情報取得.
    int N, K;
    cin >> N >> K;
    
    LL X[N] = {};
    FOR(i, 0, N) cin >> X[i];
    
    // 2. 連続する K 本のろうそくに火を付けるのが最適(解説通り).
    LL mDistance = 10000000000000;
    FOR(l, 0, N - K + 1) {
        // 最も左の蝋燭(index) … l, 最も右の蝋燭(index) … r.
        int r = l + K - 1;
        LL distance = min(abs(X[l]) + abs(X[r] - X[l]), abs(X[r]) + abs(X[r] - X[l]));
        if(distance < mDistance) mDistance = distance;
    }
    
    // 3. 出力 ～ 後処理.
    cout << mDistance << endl;
    return 0;
    
}

// 解き直し.

// ABC #107 / ARC #101 Editorial

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

#include <iostream>

using namespace std;

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

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

#define min(x, y) ((x > y) ? y : x)

typedef long long LL;

int main() {

// 1. 入力情報取得.

int N, K;

cin >> N >> K;

LL X[N] = {};

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

// 2. 連続する K 本のろうそくに火を付けるのが最適(解説通り).

LL mDistance = 10000000000000;

FOR(l, 0, N - K + 1) {

// 最も左の蝋燭(index) … l, 最も右の蝋燭(index) … r.

int r = l + K - 1;

LL distance = min(abs(X[l]) + abs(X[r] - X[l]), abs(X[r]) + abs(X[r] - X[l]));

if(distance < mDistance) mDistance = distance;

}

// 3. 出力～後処理.

cout << mDistance << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 107

2018年8月25日2018年9月3日

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

C++の練習を兼ねて, AtCoder Beginner Contest 076 の問題C（Dubious Document 2）を解いてみた.

■感想.
ゴリゴリ書いた印象で感触悪かったものの, 解説と方針がおおよそ一致していたので, とりあえず, 及第点までは行けたかと思う.

本家のサイトAtcoder Beginner Contest 076 解説をご覧下さい。

■C++版プログラム

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

using namespace std;

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

int main() {
    
    // 1. 入力情報取得.
    string S1, T;
    cin >> S1;
    cin >> T;
    
    // 2. S1内に, T を埋め込めるか確認し, 埋め込める場合は, 
    // 文字列Sを生成(該当箇所の ? について, 文字列T に置換し, 残りの ? は, 文字'a' に置換)し, vector に保存.
    vector<string> recovery;
    int ls1 = S1.size();
    int lt  = T.size();
    FOR(i, 0, ls1 - lt + 1) {
        // 2-1. T に 置換可能か確認.
        string s = S1.substr(i, lt);    // S1 から, T と 同じ長さの文字列を抽出.
        bool ok = true;
        FOR(j, 0, lt) {
            if(s[j] != '?' && s[j] != T[j]) {
                ok = false;
                break;
            }
        }
        
        // 2-2. T に 置換可能な場合, vector に 文字列S を保存.
        if(ok) {
            string S = "";
            FOR(j, 0, ls1) {
                if(j >= i && j < i + lt) S += T[j - i];
                else if(S1[j] == '?')    S += 'a';
                else                     S += S1[j];
            }
            recovery.push_back(S);
        }
    }
    
    // 3. 出力 ～ 後処理.
    if(recovery.empty()) {
        cout << "UNRESTORABLE" << endl;
    } else {
        sort(recovery.begin(), recovery.end());
        cout << recovery[0] << endl;
    }
    
    return 0;
    
}

#include <iostream>

#include <algorithm>

#include <string>

#include <vector>

using namespace std;

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

int main() {

// 1. 入力情報取得.

string S1, T;

cin >> S1;

cin >> T;

// 2. S1内に, T を埋め込めるか確認し, 埋め込める場合は,

// 文字列Sを生成(該当箇所の ? について, 文字列T に置換し, 残りの ? は, 文字'a' に置換)し, vector に保存.

vector<string> recovery;

int ls1 = S1.size();

int lt = T.size();

FOR(i, 0, ls1 - lt + 1) {

// 2-1. T に置換可能か確認.

string s = S1.substr(i, lt); // S1 から, T と同じ長さの文字列を抽出.

bool ok = true;

FOR(j, 0, lt) {

if(s[j] != '?' && s[j] != T[j]) {

ok = false;

break;

}

// 2-2. T に置換可能な場合, vector に文字列S を保存.

if(ok) {

string S = "";

FOR(j, 0, ls1) {

if(j >= i && j < i + lt) S += T[j - i];

else if(S1[j] == '?') S += 'a';

else S += S1[j];

}

recovery.push_back(S);

}

// 3. 出力～後処理.

if(recovery.empty()) {

cout << "UNRESTORABLE" << endl;

} else {

sort(recovery.begin(), recovery.end());

cout << recovery[0] << endl;

}

return 0;

}

■参照サイト
AtCoder Beginner Contest 076

2018年8月24日2018年9月3日

■感想.
① N が最大 10の5乗と指示があったので, for文の 3重ループは, TLE になると推測し, 二分探索などを模索した.
② lower_bound, upper_bound という便利な関数が用意されていることが, ネット上の情報で判明したので, 計算量削減に使えないか, 検討してみた.
③ 最初, A を基準に試行錯誤してみたが, 条件を満たす組み合わせの数え上げが上手くいかず, 次に, B を基準に試行錯誤してみたところ, 条件を満たす組み合わせの数え上げが上手くいった.
④ 本家の解答を見たところ, おおよそ解答方針が一致していたので, 時間かかってしまったものの, とりあえず粘ってみた甲斐があったと思われる.

本家のサイトARC084/ABC077 解説をご覧下さい。

■C++版プログラム

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

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;
    
    vector<LL> A, B, C;
    FOR(i, 0, N) {
        LL a;
        cin >> a;
        A.push_back(a);
    }
    
    FOR(i, 0, N) {
        LL b;
        cin >> b;
        B.push_back(b);
    }
    
    FOR(i, 0, N) {
        LL c;
        cin >> c;
        C.push_back(c);
    }
    
    // 2. 各A ～ C を, 昇順sort.
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());
    
    // 3. B を 基準にして, B[j] (0 <= j <= N - 1) に対して,
    // lower_bound, upper_bound で, A[i] < B[j] < C[k] となるi, k の組み合わせを計算していく.
    // ※ A を 基準にすると, 上手く行かなかった.
    // lower_bound、upper_boundの基本的な使い方.
    // https://qiita.com/kontotto/items/c718ec114b1532a2d159
    LL combination = 0;
    for(auto itr = B.begin(); itr != B.end(); ++itr) {
        
        // 3-1. B[j] を 取り出す.
        LL b = *itr;
        
        // 3-2. lower_bound で, A[i] を 取得.
        auto ita = lower_bound(A.begin(), A.end(), b);
        LL a = ita - A.begin();
        
        // 3-3. upper_bound で, C[k] を 取得.
        auto itc = upper_bound(C.begin(), C.end(), b);
        LL c = C.end() - itc;
        // cout << *ita << " " << *itc << endl;
        // cout << a << " " << c << endl;
    
        // 3-4. 条件を満たす組み合わせを加算.
        combination += a * c;    // 条件を満たす A の要素数 × 条件を満たす C の要素数.
    }
    
    // 4. 出力 ～ 後処理.
    cout << combination << endl;
    return 0;
    
}

#include <iostream>

#include <algorithm>

#include <vector>

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;

vector<LL> A, B, C;

FOR(i, 0, N) {

LL a;

cin >> a;

A.push_back(a);

}

FOR(i, 0, N) {

LL b;

cin >> b;

B.push_back(b);

}

FOR(i, 0, N) {

LL c;

cin >> c;

C.push_back(c);

}

// 2. 各A ～ C を, 昇順sort.

sort(A.begin(), A.end());

sort(B.begin(), B.end());

sort(C.begin(), C.end());

// 3. B を基準にして, B[j] (0 <= j <= N - 1) に対して,

// lower_bound, upper_bound で, A[i] < B[j] < C[k] となるi, k の組み合わせを計算していく.

// ※ A を基準にすると, 上手く行かなかった.

// lower_bound、upper_boundの基本的な使い方.

// https://qiita.com/kontotto/items/c718ec114b1532a2d159

LL combination = 0;

for(auto itr = B.begin(); itr != B.end(); ++itr) {

// 3-1. B[j] を取り出す.

LL b = *itr;

// 3-2. lower_bound で, A[i] を取得.

auto ita = lower_bound(A.begin(), A.end(), b);

LL a = ita - A.begin();

// 3-3. upper_bound で, C[k] を取得.

auto itc = upper_bound(C.begin(), C.end(), b);

LL c = C.end() - itc;

// cout << *ita << " " << *itc << endl;

// cout << a << " " << c << endl;

// 3-4. 条件を満たす組み合わせを加算.

combination += a * c; // 条件を満たす A の要素数 × 条件を満たす C の要素数.

}

// 4. 出力～後処理.

cout << combination << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 077
lower_bound、upper_boundの基本的な使い方

2018年8月18日2018年9月3日

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

C++の練習を兼ねて, AtCoder Beginner Contest 106 の問題D（AtCoder Express 2）を解いてみた.

■感想.
① 時間内では, C011_scrambled ～ C016_scrambled で, TLEとなったので, ロジック見直しが必要となった.
※下記ソース: ABC_106_D_1.cpp
② 解答を確認して, 計算量の削減方法について, 大変参考になった.
※下記ソース: ABC_106_D_2.cpp

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

■C++版プログラム

// C011_scrambled ～ C016_scrambled で, TLEとなった.
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

struct city {
  int li;    // 都市Li.
  int ri;    // 都市Ri.
};

int main() {
    
    // 1. 入力情報取得.
    int N, M, Q;
    cin >> N >> M >> Q;
    
    // 2. 都市情報を保存.
    vector<city> cities;
    FOR(i, 0, M) {
        city c;
        cin >> c.li >> c.ri;
        cities.push_back(c);
    }
    
    // 3. Q個の質問に解答.
    FOR(i, 0, Q) {
        int p, q;
        cin >> p >> q;
        // 条件を満たす列車の本数を計算.
        int c = 0;
        for (vector<city>::const_iterator i = cities.begin(); i != cities.end(); i++) {
            if(p <= i->li && i->ri <= q) c++;
        }
        cout << c << endl;
    }
    
    // 4. 後処理.
    return 0;
    
}

// C011_scrambled ～ C016_scrambled で, TLEとなった.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

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

struct city {

int li; // 都市Li.

int ri; // 都市Ri.

};

int main() {

// 1. 入力情報取得.

int N, M, Q;

cin >> N >> M >> Q;

// 2. 都市情報を保存.

vector<city> cities;

FOR(i, 0, M) {

city c;

cin >> c.li >> c.ri;

cities.push_back(c);

}

// 3. Q個の質問に解答.

FOR(i, 0, Q) {

int p, q;

cin >> p >> q;

// 条件を満たす列車の本数を計算.

int c = 0;

for (vector<city>::const_iterator i = cities.begin(); i != cities.end(); i++) {

if(p <= i->li && i->ri <= q) c++;

}

cout << c << endl;

}

// 4. 後処理.

return 0;

}

// 解き直し.
// AtCoder Beginner Contest 106 解説.
// https://img.atcoder.jp/abc106/editorial.pdf
#include <iostream>

using namespace std;

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

int main() {
    
    // 1. 入力情報取得.
    int N, M, Q;
    cin >> N >> M >> Q;
    
    // 2. 都市情報を保存.
    int cities[501][501] = {};
    FOR(i, 0, M) {
        int l, r;
        cin >> l >> r;
        cities[l][r]++;
    }
    // L方向に累積和.
    FOR(r, 0, 501) FOR(l, 1, 501) cities[r][l] += cities[r][l - 1];
    
    // 3. Q個の質問に解答.
    FOR(i, 0, Q) {
        int p, q;
        cin >> p >> q;
        // 条件を満たす列車の本数を計算.
        int c = 0;
        FOR(r, p, q + 1) c += (cities[r][q] - cities[r][p - 1]);
        cout << c << endl;
    }
    
    // 4. 後処理.
    return 0;
    
}

// 解き直し.

// AtCoder Beginner Contest 106 解説.

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

#include <iostream>

using namespace std;

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

int main() {

// 1. 入力情報取得.

int N, M, Q;

cin >> N >> M >> Q;

// 2. 都市情報を保存.

int cities[501][501] = {};

FOR(i, 0, M) {

int l, r;

cin >> l >> r;

cities[l][r]++;

}

// L方向に累積和.

FOR(r, 0, 501) FOR(l, 1, 501) cities[r][l] += cities[r][l - 1];

// 3. Q個の質問に解答.

FOR(i, 0, Q) {

int p, q;

cin >> p >> q;

// 条件を満たす列車の本数を計算.

int c = 0;

FOR(r, p, q + 1) c += (cities[r][q] - cities[r][p - 1]);

cout << c << endl;

}

// 4. 後処理.

return 0;

}

■参照サイト
AtCoder Beginner Contest 106

2018年8月14日2018年9月3日

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

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

■感想.
① 解答を後で見たところ, if – else if で押し切っているので, なるほどと感心させられた.
② ＋＋＋, ＋＋－, … , －－－の8通り調べる方針は, 一致していたので, 着眼点が大きくブレてはいなかったと思われる.
③ char型 -> int型の変換方法について, 勉強になったと思われる.

本家のサイトABC 079 解説をご覧下さい。

■C++版プログラム

#include <iostream>
#include <string>

using namespace std;

#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define joisinoOperators(b) (b ? "+" : "-")

// 与えられた二整数 x, y について, 加算 or 減算 を計算して返却.
// @param x: 第一引数.
// @param y: 第二引数.
// @param o: 演算指定用(0 … 加算, 1 … 減算).
// @return: 与えられた二整数を計算し, 返却.
int joisinoCalculate(int x, int y, int o) {
    return (o ? x + y : x - y);
}

int main() {
    
    // 1. 入力情報取得.
    string N;
    cin >> N;
    
    // 2. 7 に等しくなる op1, op2, op3 のパターンを計算.
    // op1, op2, op3 を 000, 001, ... , 111 と見て, 0 … プラス, 1 … マイナス で考える方針とした.
    int op = 0;
    FOR(i, 0, 8) {
        op = i;
        int comp7 = 0;
        comp7 = joisinoCalculate(N[0] - '0',  N[1] - '0', op & 1);
        comp7 = joisinoCalculate(comp7,       N[2] - '0', op & 2);
        comp7 = joisinoCalculate(comp7,       N[3] - '0', op & 4);
        if(comp7 == 7) break;
    }
    
    // 3. 表示用文字列作成.
    string joisinoString = "";
    joisinoString += N[0];
    joisinoString += joisinoOperators(op & 1);
    joisinoString += N[1];
    joisinoString += joisinoOperators(op & 2);
    joisinoString += N[2];
    joisinoString += joisinoOperators(op & 4);
    joisinoString += N[3];
    joisinoString += "=7";
    
    // 4. 出力 ～ 後処理.
    cout << joisinoString << endl;
    return 0;
    
}

#include <iostream>

#include <string>

using namespace std;

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

#define joisinoOperators(b) (b ? "+" : "-")

// 与えられた二整数 x, y について, 加算 or 減算を計算して返却.

// @param x: 第一引数.

// @param y: 第二引数.

// @param o: 演算指定用(0 … 加算, 1 … 減算).

// @return: 与えられた二整数を計算し, 返却.

int joisinoCalculate(int x, int y, int o) {

return (o ? x + y : x - y);

}

int main() {

// 1. 入力情報取得.

string N;

cin >> N;

// 2. 7 に等しくなる op1, op2, op3 のパターンを計算.

// op1, op2, op3 を 000, 001, ... , 111 と見て, 0 … プラス, 1 … マイナスで考える方針とした.

int op = 0;

FOR(i, 0, 8) {

op = i;

int comp7 = 0;

comp7 = joisinoCalculate(N[0] - '0', N[1] - '0', op & 1);

comp7 = joisinoCalculate(comp7, N[2] - '0', op & 2);

comp7 = joisinoCalculate(comp7, N[3] - '0', op & 4);

if(comp7 == 7) break;

}

// 3. 表示用文字列作成.

string joisinoString = "";

joisinoString += N[0];

joisinoString += joisinoOperators(op & 1);

joisinoString += N[1];

joisinoString += joisinoOperators(op & 2);

joisinoString += N[2];

joisinoString += joisinoOperators(op & 4);

joisinoString += N[3];

joisinoString += "=7";

// 4. 出力～後処理.

cout << joisinoString << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 079
char型をint型に変換する方法と注意【数値化キャスト文字列変換】

2018年8月12日2018年9月3日

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

C++の練習を兼ねて, AtCoder Beginner Contest 105 の問題D（Candy Distribution）を解いてみた.

■感想.
① C++ 連想配列クラス(std::map) の使い方を練習出来て良かったと思う.
② 連想配列クラスから, 値を取り出してくる場合, イテレータを使うのが良いらしい.
③ 余りゼロのケースは, 初めから, カウントアップしておく点に注意が必要.
④ 最大, 48[ms] かかっているテストケースがあったので, 改善の余地が, たくさんありそう.

本家のサイトABC 105 解説をご覧下さい。

■C++版プログラム

// 解き直し.
// ABC 105 解説.
// https://img.atcoder.jp/abc105/editorial.pdf
#include <iostream>
#include <map>

using namespace std;

typedef long long LL;

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

int main() {
    
    // 1. 入力情報取得.
    LL N, M;
    cin >> N >> M;
    
    // 2. 累積和で保管(但し, mod M で考える).
    LL A[N + 1] = {};
    map<LL, LL> B{}; // 解説通り, mapを使用.
    FOR(i, 1, N + 1) {
        cin >> A[i];
        A[i] += A[i - 1];
        A[i] %= M;
        B[A[i]]++;
    }
    
    // 3. お菓子の配り方をカウントアップ.
    
    // 3-1. 余りゼロのケース(B[0])は, 常に, 加算しておく必要がある.
    LL aCount = B[0];
    
    // 3-2. B[i]個から, 2個選ぶ選び方の組み合わせを加算.
    // FOR(i, 0, M) aCount += (B[i] - 1) * B[i] / 2;
    // -> M が 大きい場合, 終了コード 9 となり, 正しく実行されないことを確認したので,
    // iterator を 使う形に書き換えた.
    for(auto itr = B.begin(); itr != B.end(); ++itr) {
        LL bi = itr->second;
        aCount += (bi - 1) * bi / 2;
    }
    
    // 4. 出力 ～ 後処理.
    cout << aCount << endl;
    return 0;
    
}

// 解き直し.

// ABC 105 解説.

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

#include <iostream>

#include <map>

using namespace std;

typedef long long LL;

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

int main() {

// 1. 入力情報取得.

LL N, M;

cin >> N >> M;

// 2. 累積和で保管(但し, mod M で考える).

LL A[N + 1] = {};

map<LL, LL> B{}; // 解説通り, mapを使用.

FOR(i, 1, N + 1) {

cin >> A[i];

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

A[i] %= M;

B[A[i]]++;

}

// 3. お菓子の配り方をカウントアップ.

// 3-1. 余りゼロのケース(B[0])は, 常に, 加算しておく必要がある.

LL aCount = B[0];

// 3-2. B[i]個から, 2個選ぶ選び方の組み合わせを加算.

// FOR(i, 0, M) aCount += (B[i] - 1) * B[i] / 2;

// -> M が大きい場合, 終了コード 9 となり, 正しく実行されないことを確認したので,

// iterator を使う形に書き換えた.

for(auto itr = B.begin(); itr != B.end(); ++itr) {

LL bi = itr->second;

aCount += (bi - 1) * bi / 2;

}

// 4. 出力～後処理.

cout << aCount << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 105
C++ 連想配列クラス std::map 入門

2018年8月12日

OpenAI Gym を使ってみた（１）

Window10上だと, 敷居が高く感じたので, macOS(High Sierra 10.13.4)上で確認してみた.

■動作環境構築(例)
下記, 参照サイトを参考に, 以下のようなコマンドを実行した.

$ pip install gym
$ pip install --upgrade pip    <- upgrade を勧めるメッセージがあったので, install.
$ brew install cmake boost boost-python sdl2 swig wget
$ pip install 'gym[all]'
$ virtualenv --system-site-packages -p python3 env
$ source env/bin/activate

$ pip install gym

$ pip install --upgrade pip <- upgrade を勧めるメッセージがあったので, install.

$ brew install cmake boost boost-python sdl2 swig wget

$ pip install 'gym[all]'

$ virtualenv --system-site-packages -p python3 env

$ source env/bin/activate

■動作確認

$ python env/hello_gym.py

1	$ python env/hello_gym.py

# -*- coding: utf-8 -*-
# 1. import library.
import gym

# 2. set an environment.
env = gym.make('MountainCar-v0')

# 3. initialize the environment.
env.reset()

# 4. repeat 1000 times.
for _ in range(1000):
    env.render()
    action = env.action_space.sample()
    env.step(action)

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

# 1. import library.

import gym

# 2. set an environment.

env = gym.make('MountainCar-v0')

# 3. initialize the environment.

env.reset()

# 4. repeat 1000 times.

for _ in range(1000):

env.render()

action = env.action_space.sample()

env.step(action)

-> ‘CartPole-v0’ の動作確認しようとしたところ, CartPole が, 即座に画面外に消えてしまったので,
‘MountainCar-v0’ で再度, 動作確認した経緯がある.

■参照サイト
OpenAI Gymで強化学習
 OpenAI Gym 入門

2018年8月12日2018年9月3日

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

C++の練習を兼ねて, AtCoder Beginner Contest 105 の問題C（C – Base -2 Number）を解いてみた.

① 制限時間内に, 解答できず終了.
② 公開されている解答を見たものの, 理解不能.
③ 結局, 試行錯誤して, ロジックを積み上げたところ, どうやらテストケースは, 全通過した模様(汗).
④ おそらく, もっと簡単なロジックがあると想定されるので, 後日, 他の方の解答を拝見しようと思う.

本家のサイトABC 105 解説をご覧下さい。

■C++版プログラム

// 解き直し.
// ABC 105 解説.
// https://img.atcoder.jp/abc105/editorial.pdf
#include <iostream>
#include <string>

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;

// 整数a の b乗 を返却.
// @param a: べき乗したい整数.
// @param b: 指数.
// @return: 整数a の b乗.
LL power(int a, int b) {
    LL ret = 1;
    FOR(i, 0, b) ret *= a;
    return ret;
}

int main() {
    
    // 1. 入力情報取得.
    LL N;
    cin >> N;
    
    // 2. 指数の最大値を, 32 と仮定.
    // -9 ÷ 2 = -5 余り 1 のような計算を繰り返す.

    // 2-1. N == 0 の場合は, 0 を出力して, 終了.
    if(N == 0) {
        cout << 0 << endl;
        return 0;
    }

    // 2-2. N != 0 の場合.
    LL nCopy = N;  // 2で割り続けるため, コピーを取得.
    LL nComp = 0;  // N と比較し, 終了条件に使用.
    string b2 = "";
    FOR(i, 0, 32) {
        LL q = abs(nCopy % 2);  // 余り.
        LL r = nCopy / -2;       // 商.
        if(nCopy == (r - 1) * -2 + q) r -= 1;  // nCopy < 0 の場合を想定.
        if(nCopy == (r + 1) * -2 + q) r += 1;  // nCopy > 0 の場合を想定.
        b2.insert(0, to_string(q));
        nCopy = r;    // N に r を 代入して, 繰り返し計算.
        nComp += q * power(-2, i);
        if(N == nComp) break;    // 元の整数と一致したら, 処理を終了.
    }
    
    // 3. 出力 ～ 後処理.
    cout << b2 << endl;
    return 0;
    
}

// 解き直し.

// ABC 105 解説.

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

#include <iostream>

#include <string>

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;

// 整数a の b乗を返却.

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

// @param b: 指数.

// @return: 整数a の b乗.

LL power(int a, int b) {

LL ret = 1;

FOR(i, 0, b) ret *= a;

return ret;

}

int main() {

// 1. 入力情報取得.

LL N;

cin >> N;

// 2. 指数の最大値を, 32 と仮定.

// -9 ÷ 2 = -5 余り 1 のような計算を繰り返す.

// 2-1. N == 0 の場合は, 0 を出力して, 終了.

if(N == 0) {

cout << 0 << endl;

return 0;

}

// 2-2. N != 0 の場合.

LL nCopy = N; // 2で割り続けるため, コピーを取得.

LL nComp = 0; // N と比較し, 終了条件に使用.

string b2 = "";

FOR(i, 0, 32) {

LL q = abs(nCopy % 2); // 余り.

LL r = nCopy / -2; // 商.

if(nCopy == (r - 1) * -2 + q) r -= 1; // nCopy < 0 の場合を想定.

if(nCopy == (r + 1) * -2 + q) r += 1; // nCopy > 0 の場合を想定.

b2.insert(0, to_string(q));

nCopy = r; // N に r を代入して, 繰り返し計算.

nComp += q * power(-2, i);

if(N == nComp) break; // 元の整数と一致したら, 処理を終了.

}

// 3. 出力～後処理.

cout << b2 << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 105

月: 2018年8月

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

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

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

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

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 076 の問題C（Dubious Document 2）を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 106 の問題D（AtCoder Express 2）を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 105 の問題D（Candy Distribution）を解いてみた.

OpenAI Gym を使ってみた（１）

Window10上だと, 敷居が高く感じたので, macOS(High Sierra 10.13.4)上で確認してみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 105 の問題C（C – Base -2 Number）を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 076 の 問題C（Dubious Document 2）を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 106 の 問題D（AtCoder Express 2）を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 105 の 問題D（Candy Distribution）を解いてみた.

Window10上だと, 敷居が高く感じたので, macOS(High Sierra 10.13.4)上で確認してみた.

C++の練習を兼ねて, AtCoder Beginner Contest 105 の 問題C（C – Base -2 Number）を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 076 の問題C（Dubious Document 2）を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 106 の問題D（AtCoder Express 2）を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 105 の問題D（Candy Distribution）を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 105 の問題C（C – Base -2 Number）を解いてみた.