個人用メモ帳

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

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

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

■感想.
① 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月10日2018年9月3日

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

C++の練習を兼ねて, AtCoder Beginner Contest 090 の問題C（Flip,Flip, and Flip……）を解いてみた.

最初, if文で, 1行×1列の場合, 2行×M列の場合, N行×2列の場合, … などと試行錯誤していたが, 絶対値を使ってみると,
全ての条件が, 一つの式で表せることが確認できたので, 見た目が, だいぶスリムになったと思う.
かなり感動したので, 投稿することになってしまった(汗).

本家のサイトABC 090/ARC 091 解説をご覧下さい。

■C++版プログラム

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

using namespace std;

#define abs(x) ((x > 0) ? x : (-(x)))
typedef long long LL;

int main() {
    
    // 1. 入力情報取得.
    LL N, M;
    cin >> N >> M;
    
    // 2. カードの状態を把握.
    // 例えば,
    // (1, 1)成分 … (1, 1) -> (1, 2) -> (2, 1) -> (2, 2) の 4回操作されるので"表"のはず.
    // (1, 2)成分 … (1, 1) -> (1, 2) -> (1, 3) -> (2, 1) -> (2, 2) -> (2, 3) の6回操作されるので"表"のはず
    // -> 結局, カードの最終状態は, 自カードを含む周囲のカード枚数により, 偶数 … 表, 奇数 … 裏 と分類されることになる
    LL reversedCard = abs((N - 2) * (M - 2)); // いろんなパターンが, この数式に集約される.
    
    // 3. 出力 ～ 後処理.
    cout << reversedCard << endl;
    return 0;
    
}

// 解き直し.

// ABC 090 解説.

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

#include <iostream>

using namespace std;

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

typedef long long LL;

int main() {

// 1. 入力情報取得.

LL N, M;

cin >> N >> M;

// 2. カードの状態を把握.

// 例えば,

// (1, 1)成分 … (1, 1) -> (1, 2) -> (2, 1) -> (2, 2) の 4回操作されるので"表"のはず.

// (1, 2)成分 … (1, 1) -> (1, 2) -> (1, 3) -> (2, 1) -> (2, 2) -> (2, 3) の6回操作されるので"表"のはず

// -> 結局, カードの最終状態は, 自カードを含む周囲のカード枚数により, 偶数 … 表, 奇数 … 裏と分類されることになる

LL reversedCard = abs((N - 2) * (M - 2)); // いろんなパターンが, この数式に集約される.

// 3. 出力～後処理.

cout << reversedCard << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 090

2018年8月7日2018年9月3日

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

C言語で書かれたプログラムを, C++に書き換えてみた.

題材として、AtCoder Beginner Contest 089 の問題D（Practical Skill Test）を使ってみることにした。

但し、解答方針に関する理解は、まだまだ、出来てないように思うので(汗)、
C言語 -> C++ に翻訳してみることまでは、出来そうだったので、翻訳してみた。

なお、C言語で書かれたプログラムの詳細については、
本家のサイトABC 089 解説をご覧下さい。

■C++版プログラム

// 解き直し.
// ABC 089 解説.
// https://img.atcoder.jp/abc089/editorial.pdf
// 一部, C言語 から C++ に書き換えている.
#include <iostream>

using namespace std;

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

int main() {

    // 1. 入力情報取得.
    int H, W, D, A;
    int Q, L, R;
    int px[90001], py[90001];
    int d[90001];

    cin >> H >> W >> D;
    FOR(i, 0, H) FOR(j, 0, W) cin >> A, px[A] = i, py[A] = j;

    // 2. 魔力計算し, 出力.
    FOR(i, D + 1, H * W + 1) d[i] = d[i-D] + abs(px[i] - px[i-D]) + abs(py[i] - py[i-D]);

    cin >> Q;
    while (Q--) {
        cin >> L >> R;
        cout << (d[R] - d[L]) << endl;
    }

    // 3. 後処理.
    return 0;

}

// 解き直し.

// ABC 089 解説.

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

// 一部, C言語から C++ に書き換えている.

#include <iostream>

using namespace std;

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

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

int main() {

// 1. 入力情報取得.

int H, W, D, A;

int Q, L, R;

int px[90001], py[90001];

int d[90001];

cin >> H >> W >> D;

FOR(i, 0, H) FOR(j, 0, W) cin >> A, px[A] = i, py[A] = j;

// 2. 魔力計算し, 出力.

FOR(i, D + 1, H * W + 1) d[i] = d[i-D] + abs(px[i] - px[i-D]) + abs(py[i] - py[i-D]);

cin >> Q;

while (Q--) {

cin >> L >> R;

cout << (d[R] - d[L]) << endl;

}

// 3. 後処理.

return 0;

}

■参照サイト
AtCoder Beginner Contest 089

2018年7月22日2018年9月3日

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

1. 環境は、macOS High Sierra (version: 10.13.4) 上で行った。

2. プログラム記載～実行は、Visual Studio Code で行った。

今回確認した内容は、ロベールのＣ＋＋教室の（第１部）第６９章　リンケージである。
以下の “動作確認(改善前)” で、対応できなかったのでメモした。

■動作確認(改善前)
Visual Studio Code 上で、動作確認する上で、以下のルールで行ってきた。
1. 標準入力(cin)が有る場合 … ターミナルを使った動作確認
$ g++ -o abc xxx.cpp
$ ./abc

2. 標準入力(cin)が無い場合 … 下記、3種類のキーを同時押しする動作確認
[command]key + [shift]key + [,]key

■対象プログラム

// 第６９章　リンケージ.
// http://www7b.biglobe.ne.jp/~robe/cpphtml/html01/cpp01069.html
// プログラムの実行例.
// macOS High Sierra (version: 10.13.4) を前提としている.
// 1. Terminal.
// $ g++ -o abc 1-69_2.cpp
// $ ./abc
//
// 2. Visual Studio Code.
// [command]key + [shift]key + [,]key
// 
// -> 上記を試すと, いずれも以下のようなエラーが出力された.
// 〜(略)〜
// clang: error: linker command failed with exit code 1 (use -v to see invocation)
// 〜(略)〜
//
// -> 解決方法は, 1-69_2.cpp に記載した.
#include <iostream>

using namespace std;

// 1-69_2.cpp から 呼び出されるグローバル変数の実体.
int ext = 123;

// 1-69_2.cpp から 呼び出される関数の実体.
// @param: 特に無し.
// @return: 特に無し.
void eFunction () {
    cout << "ext = " << ext << endl;
}

// 第６９章　リンケージ.

// http://www7b.biglobe.ne.jp/~robe/cpphtml/html01/cpp01069.html

// プログラムの実行例.

// macOS High Sierra (version: 10.13.4) を前提としている.

// 1. Terminal.

// $ g++ -o abc 1-69_2.cpp

// $ ./abc

// 2. Visual Studio Code.

// [command]key + [shift]key + [,]key

// -> 上記を試すと, いずれも以下のようなエラーが出力された.

// 〜(略)〜

// clang: error: linker command failed with exit code 1 (use -v to see invocation)

// 〜(略)〜

// -> 解決方法は, 1-69_2.cpp に記載した.

#include <iostream>

using namespace std;

// 1-69_2.cpp から呼び出されるグローバル変数の実体.

int ext = 123;

// 1-69_2.cpp から呼び出される関数の実体.

// @param: 特に無し.

// @return: 特に無し.

void eFunction () {

cout << "ext = " << ext << endl;

}

// 第６９章　リンケージ.
// http://www7b.biglobe.ne.jp/~robe/cpphtml/html01/cpp01069.html
//
// 1. 複数の.cppを分割コンパイル.
// http://marupeke296.com/IKDADV_PI_CPP2.html
// 
// 2. コンパイラ(gccコマンド)の使い方
// http://www.ysr.net.it-chiba.ac.jp/data/cc.html
//
// -> 上記, 1. - 2. を参考に, 以下の形でコンパイルしてみた.
// プログラムの実行例(Terminal).
// $ g++ -c 1-69_1.cpp -o 1-69_1.o
// $ g++ -c 1-69_2.cpp -o 1-69_2.o
// $ g++ -g -o abc 1-69_1.o 1-69_2.o
// $ ./abc
#include <iostream>

using namespace std;

// 1-69_1.cpp から呼び出す関数.
void eFunction ();

int main() {

    // 1-69_1.cpp から呼び出すグローバル変数.
    extern int ext;

    eFunction();
    ext = 456;
    eFunction();

    return 0;

}

// 第６９章　リンケージ.

// http://www7b.biglobe.ne.jp/~robe/cpphtml/html01/cpp01069.html

// 1. 複数の.cppを分割コンパイル.

// http://marupeke296.com/IKDADV_PI_CPP2.html

// 2. コンパイラ(gccコマンド)の使い方

// http://www.ysr.net.it-chiba.ac.jp/data/cc.html

// -> 上記, 1. - 2. を参考に, 以下の形でコンパイルしてみた.

// プログラムの実行例(Terminal).

// $ g++ -c 1-69_1.cpp -o 1-69_1.o

// $ g++ -c 1-69_2.cpp -o 1-69_2.o

// $ g++ -g -o abc 1-69_1.o 1-69_2.o

// $ ./abc

#include <iostream>

using namespace std;

// 1-69_1.cpp から呼び出す関数.

void eFunction ();

int main() {

// 1-69_1.cpp から呼び出すグローバル変数.

extern int ext;

eFunction();

ext = 456;

eFunction();

return 0;

}

■動作確認(改善前)による実行結果
前述のプログラムを実行した結果、いずれの場合でも、以下のようなエラーが出力された。

〜(略)〜
clang: error: linker command failed with exit code 1 (use -v to see invocation)
〜(略)〜

■動作確認(改善版)
分割コンパイルが必要とのネット上の情報があったので、以下の形で、ターミナル上で対応した。
$ g++ -c 1-69_1.cpp -o 1-69_1.o
$ g++ -c 1-69_2.cpp -o 1-69_2.o
$ g++ -g -o abc 1-69_1.o 1-69_2.o
$ ./abc

■動作確認(改善後)による実行結果
前述のプログラムを実行した結果、以下のように、想定した動作を確認することができた。

■参照サイト
複数の.cppを分割コンパイル

コンパイラ(gccコマンド)の使い方

ターミナルに毎回表示される長ったらしい表示を短くする

2018年5月31日2018年5月31日

平成30年春期エンベデッドシステムスペシャリスト試験（ES）午後Ⅱ（問２）を解いてみた。

引き続き、ハードウェアの知識を補いたいので、試しに解いてみました。

※1. 受験した訳でないです。
※2. 解答を記載ましたが、正解とは限りません。

■■■ 問1 ■■■

■設問1.
(1)
(a) 商品の口数 … 3
販売した口数 … 3
・図6(P.22) に、”出荷ラベル3枚の印刷指示” と記載されているので、販売した口数は、3 と推定。
・図6(P.22) の注記で、”購入メッセージに付加された口数の値は、99であった。” との記述から、表2(P.17) の購入で、全口購入キーが押されたことを示す、に該当すると判断した。よって、商品の口数は、販売した口数と同じ 3 だったと推定。

(b) 競り休止
・表2(P.17) から、台端末 → 制御装置で、”競り開始”、”競り休止”、”競り終了” のステータスが有り得る。
したがって、以下の3パターンが考えられる。
① 競り開始 → 競り開始 → 競り開始 (※そもそも、考えづらい)
② 競り開始 → 競り休止 → 競り開始 (※表2(P.17) の競り開始の “確定キー” の記述、競り休止の “休止キー” の記述に符合)
② 競り開始 → 競り終了 → 競り開始 (※”競り終了” 後は、”競り結果” が来るはずなので、”競り開始” とならないと判断)
上記から、② のパターンを答案として採用してみた。

(2) 競り価格を下げずに競りを再開する場合。(19字)
・表2(P.17) の競り開始で、”テンキーで入力された値がなければ、付加される値は 0 である。”
・[制御装置における処理の概要] の (3) ④(P.18) に、”～競り価格から競り開始メッセージに付加された値を引いた価格を新たな競り価格～”
上記、2点との記載があるので、これをもとに答案作成してみた。

(3) 29[ms]
・商品の静止画 … 図3(P.16) より、商品の静止画を表示する領域は、600×500ピクセルと分かるので、600 × 500 × 3 = 900000[byte] = 900[kilobyte]
・テキストデータ … 問題文より、4[kilobyte]
・LAN1 の実効通信速度 … 1[gigabit/s] × 25% × (1 / 8)[byte/bit] = (1 / 32)[gigabyte/s] = (1000 / 32)[kilobyte/s]
・以上から、(900 + 4)[kilobyte] ÷ (1000 / 32)[kilobyte/s] = 28.928[ms] → 小数第１位を四捨五入して、29[ms]

■設問2.
(1)
(a) スクリーンと台端末に表示する休止中及び新たな販売可能な口数に関する情報(35字)
・表3(P.20) の情報表示タスクを参考に、答案作成してみた。

(b) 競り開始要求を受けてから情報表示タスクに情報表示要求を通知するまでの間(35字)
・表3(P.20) の競り制御タスクの ② と、図6(P.22) の通信シーケンスを参考に、答案作成してみた。

(2)
(a) 購入を希望する口数、買参人番号
・表2(P.17) 購入メッセージで、”台番号キーで入力した台番号と～買参人番号が付加される。” との記述があること
・図5(P.19) 購入履歴情報を構成するレコードのフィールドを見ると、買参人番号、購入口数が含まれること
→ 上記、2点の記載から、これをもとに答案作成してみた。

(b) 買参人端末の表示部に、取引の成立又は不成立についての結果の表示を指示(34字)
・他の買参人が、取引成立となった場合もイメージして、答案作成してみた。(汗)

(3)
(a) 購入履歴情報を構成するレコードの買参人番号が、記憶した買参人番号と一致するすべてのレコードを記憶(48字)
・図5(P.19) 購入履歴情報を構成するレコードのフィールドを見ると、買参人番号が含まれること
・表3(P.20) の買参人タスクに、”該当する買参人の購入履歴を買参人端末表示メッセージで～” との記述(※購入履歴情報のレコードについて絞り込み機能があると推測される)があること
→ 上記、2点の記載から、これをもとに答案作成してみた。

(b) 前回追加したレコードのリンクの値を新たなレコードのリンクに設定し、前回追加したレコードのリンクに新たなレコードのレコード番号を設定(65字)
・図5(P.19) 購入履歴情報を構成するレコードのフィールドで、レコード番号、買参人番号、リンクに絞って考えてみた。
・以下の [変更後] の挙動をイメージして、答案作成してみたが、異常にムズイ。(汗)

[変更前]
00003 BUYER_03 -1
(※前回レコード番号: 00003 に更新)
↓
00003 BUYER_03 -1
00007 BUYER_03 00003
(※前回レコード番号: 00007 に更新)
↓
00003 BUYER_03 -1
00007 BUYER_03 00003
00011 BUYER_03 00007
(※前回レコード番号: 00011 に更新)
↓
00003 BUYER_03 -1
00007 BUYER_03 00003
00011 BUYER_03 00007
00025 BUYER_03 00011
(※前回レコード番号: 00025 に更新)
↓
以下、続く

[変更後]
00003 BUYER_03 -1
(※前回レコード番号: 00003 に更新)
↓
00003 BUYER_03 00007 ← update
00007 BUYER_03 00003 ← update
(※前回レコード番号: 00007 に更新)
↓
00003 BUYER_03 00007
00007 BUYER_03 00011 ← update
00011 BUYER_03 00003 ← update
(※前回レコード番号: 00011 に更新)
↓
00003 BUYER_03 00007
00007 BUYER_03 00011
00011 BUYER_03 00025 ← update
00025 BUYER_03 00003 ← update
(※前回レコード番号: 00025 に更新)
↓
以下、続く

・但し、問題文は、レコードの書き込みについてだけ言及されているものの、おそらく、そもそも購入履歴の表示方法も、変わってくると推測される。以下の具体例のように、1行目に表示するレコードの表示方法が異なってくると推測される。
・購入履歴の表示例
[変更前]
00003 BUYER_03 -1
00007 BUYER_03 00003
00011 BUYER_03 00007
00025 BUYER_03 00011
(※前回レコード番号: 00025 に更新)

上記の購入履歴データを、表示させる場合、
① 前回レコード番号: 00025 をもとに、レコード番号 00025 を 1行目に表示
② レコード番号 00025 のリンク 00011 から、レコード番号 00011 を 2行目に表示
③ レコード番号 00011 のリンク 00007 から、レコード番号 00007 を 3行目に表示
④ レコード番号 00007 のリンク 00003 から、レコード番号 00003 を 4行目に表示

[変更後]
00003 BUYER_03 00007
00007 BUYER_03 00011
00011 BUYER_03 00025
00025 BUYER_03 00003
(※前回レコード番号: 00025 に更新)

上記の購入履歴データを、表示させる場合、
① 前回レコード番号: 00025 をもとに、レコード番号 00025 のリンク 00003 から、レコード番号 00003 を 1行目に表示
② レコード番号 00003 のリンク 00007 から、レコード番号 00007 を 2行目に表示
③ レコード番号 00007 のリンク 00011 から、レコード番号 00011 を 3行目に表示
④ レコード番号 00011 のリンク 00025 から、レコード番号 00025 を 4行目に表示

■設問3.
(1)
e. 商品追加完了の通知
f. 商品移動指示
g. 商品追加許可
・表4(P.25) の競り制御タスクから、文言から抜粋等によって、答案作成してみた。

(2)
h. 指定された商品情報を競り待ちテーブルの末尾に追加(24字)
・表4(P.25) の “商品移動要求を受けると、指定された商品情報を競り待ちテーブルの末尾に追加する。” から抜粋して、答案作成してみた。

(3)
i. 商品追加要求
j. 商品移動指示
k. 商品移動完了
l. 商品追加完了
m. 商品追加指示の処理③で追加した商品情報が、商品移動指示の処理①で消える(35字)
・競り待ちテーブルの更新タイミングについて、商品移動指示は、”処理①”、商品追加指示は、”処理③” となっているため、これを念頭に、答案作成してみたが、異常にムズイ。(汗)

参照サイト
■平成30年度春期(1)試験問題冊子・解答例・採点講評・配点割合（PDF）
https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2018h30_1/2018h30h_es_pm2_qs.pdf

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 090 の 問題C（Flip,Flip, and Flip……）を解いてみた.

C言語で書かれたプログラムを, C++に書き換えてみた.

1. 環境は、macOS High Sierra (version: 10.13.4) 上で行った。

2. プログラム記載～実行は、Visual Studio Code で行った。

引き続き、ハードウェアの知識を補いたいので、試しに解いてみました。

■■■ 問1 ■■■

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）を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 090 の問題C（Flip,Flip, and Flip……）を解いてみた.