C++ | 個人用メモ帳

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日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

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