競技プログラミング風 C++問題集【第5回】

はじめに

今回から４回にわたって「競技プログラミング風 C++問題集第5回～第8回（シーズン２）」をお届けする。

各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。
まず、問題を読んで正しく理解し、テストコード部分をIDEやテキストエディタまたはweb上のコンパイラ（ideonなど）で保存・ビルド・実行し、アウトプットに「NG」が表示されるのを確認してほしい。次に、テストコードの「ToDo:」部分のコードを完成させて、「NG」ではなく「Good Job!」が表示されるようにできれば問題クリアだ。

「ヒント」「解答例」「解説」はデフォルトでは非表示になっており、中身を読みたい場合は【show】ボタンを押せば表示される。これらをすぐに読むのではなく、ちゃんと解答を考え、使用する標準ライブラりのクラス・関数をweb検索して勉強し、コード記述・ビルド・実行してからそれらを読むのを強く推奨する。なにごとも自分で考え、いろいろ試した上で、解答などを見るようにするのが肝要だ。その方が解答が印象に残り問題解決方法が記憶に定着しやすいのだ。

問題はノンジャンルとするが、競技プログラミング問題に多いパズル的要素は少なめにし、実務的な問題よりにするようにした。
難易度的には「標準C++ライブラリ入門」よりは若干上がってるかもしれないが、極端に難しい問題はないので、どんどん問題を解いていただきたいと思っている。

グリコ遊び（難易度：★★☆☆☆）

問題

Aさん・Bさんの二人でじゃんけんを行い、勝者がグーを出した場合は３歩、チョキ・パーの場合は６歩進むものとする（負け・引き分けの場合は進めない）。このとき、二人の手の出し方を文字列引数で受け取り、Aさんの進む歩数を返す関数 int glico(const string& A, const string& B) を実装しなさい。

ただし、手の出し方文字列では、’G’ がグーを、’C’ がチョキを、’P’ がパーを表すものとする。
‘G’, ‘C’, ‘P’ 以外の文字があった場合は、相手の手に関わらず負けとする（双方ともに’G’, ‘C’, ‘P’ 以外の文字の場合は引き分けとする）。
また、手の出し方文字列長が不一致の場合は、不正な引数とみなし -1 を返すものとする。

#include <iostream>       //  標準入出力ライブラリ
#include <string>
const int WIDTH = 8, HEIGHT = 8;  //  画面サイズ
typedef unsigned char uchar;
using namespace std;    //  std 名前空間使用
#define DO_TEST(exp)    do_test(exp, __LINE__)
void do_test(bool b, int line) {
    if( b ) return;     //  OK
    cout << "\nNG at line " << line << "\n";
    exit(1);
}
int glico(const string& A, const string& B) {
    //  ToDo: ここにコードを記述し、A さんが進む歩数を返すようにしなさい
    return 0;
}
int main() {
    DO_TEST( glico("", "") == 0 );
    DO_TEST( glico("GCP", "CCC") == 3 );
    DO_TEST( glico("GCP", "PPP") == 6 );
    DO_TEST( glico("GCPGCP", "CCCPPP") == 9 );
    DO_TEST( glico("GCP", "CPG") == 15 );
    DO_TEST( glico("GCP", "...") == 15 );
    DO_TEST( glico("GCP", "....") == -1 );
    cout << "\nGood Job!\n";
    return 0;
}

ヒント

・まずは最初に二人の手の数が一致するかチェックした方がいいぞ。
・次にfor文で回して、Aさん、Bさんの手を順にチェックするんだぞ。
・Aさんがグーであれば、Bさんがチョキ、またはパーでもグーでもなければ3歩進むんだぞ。
・Aさんがチョキ・パーの場合も同様だ。
・最後に進んだ歩数の合計を返すんだぞ。

解答例

int glico(const string& A, const string& B) {
    if( A.size() != B.size() ) return -1;    //  手の数が不一致の場合
    int step = 0;       //  歩数
    for (int i = 0; i < A.size(); ++i) {
        switch (A[i]) {
        case 'G':   //  Aさんがグーの場合
            if (B[i] == 'C' || (B[i] != 'P' && B[i] != 'G'))    //  Bさんがチョキ、または不正な文字
                step += 3;      //  Aさんの勝ち
            break;
        case 'C':   //  Aさんがチョキの場合
            if (B[i] == 'P' || (B[i] != 'G' && B[i] != 'C'))    //  Bさんがパー、または不正な文字
                step += 6;      //  Aさんの勝ち
            break;
        case 'P':   //  Aさんがパーの場合
            if (B[i] == 'G' || (B[i] != 'C' && B[i] != 'P'))    //  Bさんがグー、または不正な文字
                step += 6;      //  Aさんの勝ち
            break;
        }
    }
    return step;    //  合計歩数を返す
}

解説

まず最初に二人の手の数が一致するかチェックし、不一致であれば -1 を返す。
歩いた歩数の合計を保持する変数を用意し、0 に初期化しておく。
for文で回して各文字を順にチェックする。筆者は拡張for文の方が好きなのだが、この場合は対応するBの文字と比較する必要があるので、通常のfor文で文字列インデックス i を回している。
i番目のAさんの手を元に、switch 文で分岐する。Aさんがグーであれば、Bさんがチョキ、またはパーでもグーでもなければ、 Aさんの勝ちなので3歩進む。チョキ、パーの場合も同様だ。ただし、進む歩数は6歩となる。
最後に合計歩数を返す。

【CG】データ→画像変換（難易度：★★☆☆☆）

問題

const vector<uchar>&型引数で 8個の8bitデータが引数で渡され、それを 8×8 のスクリーン文字列に変換する関数 string dataToScreen(const vector<uchar>& data) を実装しなさい（uchar はunsigned char と定義されているものとする）。

配列の各データはスクリーンの１行分の情報を保持し、最上位ビットが画面左端を、最下位ビットが画面右端を表すものとし、ビットの値が1ならば ‘*’ を、ビットの値が0ならば ‘.’ をスクリーン文字列に設定するものとする。また、配列の各データは、画面上部から下部の順に格納されているものとする。

スクリーンの文字列も、データ同様に左から右、上から下の順序とする。

例えば、{0, 1, 2, 3, 0x10, 0x20, 0xa5, 0xff} というデータが渡された場合は、以下のような文字列を返すものとする（注意：下図では見やすいように８文字ごとに文字列を分けているが、実際はひとつの文字列である）。

競技プログラミング風C＋＋問題集【第5回】_01

なお、引数で渡された配列長が8でない場合は、空文字列を返すものとする。

#include <iostream>       //  標準入出力ライブラリ
#include <string>
#include <vector>
const int WIDTH = 8, HEIGHT = 8;  //  画面サイズ
typedef unsigned char uchar;
using namespace std;    //  std 名前空間使用
#define DO_TEST(exp)    do_test(exp, __LINE__)
void do_test(bool b, int line) {
    if( b ) return;     //  OK
    cout << "\nNG at line " << line << "\n";
    exit(1);
}
void print(const string& screen) {
    if( screen.size() != WIDTH*HEIGHT) {
        cout << "invalid screen size()\n";
        return;
    }
    int ix = 0;
    for (int y = 0; y < HEIGHT; ++y) {
        for (int x = 0; x < WIDTH; ++x) {
            cout << screen[ix++];
        }
        cout << "\n";
    }
    cout << "\n";
}
string dataToScreen(const vector<uchar>& data) {
    //  ToDo: ここにdataを画面に変換した文字列を返すコードを記述
    return "";
}
int main() {
    auto sc1 = dataToScreen(vector<uchar>{0, 0, 0, 0, 0, 0, 0, 0});
    print(sc1);
    DO_TEST( sc1 ==
                "........"
                "........"
                "........"
                "........"
                "........"
                "........"
                "........"
                "........" );
    auto sc2 = dataToScreen(vector<uchar>{0xff, 0x81, 0x81, 0x81, 0x81, 0x81, 0x81, 0xff});
    print(sc2);
    DO_TEST( sc2 ==
                "********"
                "*......*"
                "*......*"
                "*......*"
                "*......*"
                "*......*"
                "*......*"
                "********" );
    auto sc3 = dataToScreen(vector<uchar>{0xff, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0xff});
    print(sc3);
    DO_TEST( sc3 ==
                "********"
                "......*."
                ".....*.."
                "....*..."
                "...*...."
                "..*....."
                ".*......"
                "********" );
    auto sc4 = dataToScreen(vector<uchar>{0xfe, 0x81, 0x81, 0xfe, 0x80, 0x80, 0x80, 0x80});
    print(sc4);
    DO_TEST( sc4 ==
                "*******."
                "*......*"
                "*......*"
                "*******."
                "*......."
                "*......."
                "*......."
                "*......." );
    cout << "\nGood Job!\n";
    return 0;
}

ヒント

・最初にデータが画面高さ分だけあるかチェックするんだぞ。
・次に、for文で回して各データを順に調べていくぞ。
・各ビットの値を調べるには mask を用意し、これを 0x80 から 0x01 まで変化させ、mask & data[i] が0かどうかをチェックするといいぞ。

解答例

string dataToScreen(const vector<uchar>& data) {
    string scr;     //  スクリーン文字列
    if (data.size() == HEIGHT) {    //  データが画面高さ分あるか？
        for (auto ch : data) {      //  それぞれのデータについて
            for (int mask = 0x80; mask != 0; mask >>= 1) {      //  マクスを 0x80 → 0x01 までループ
                scr.push_back((ch & mask) != 0 ? '*' : '.');    //  マスク位置が1であれば '*' 設定
            }
        }
    }
    return scr;
}

解説

最初にデータが画面高さ分だけあるかどうかをチェックする。
正しければ、拡張for文により、全てのデータを順に取り出す。
次にビットマスク（mask）を 0x80 から 0x01 まで変化させ、ch & mask でマスク位置のビットを調べる。ビットが1であれば ‘*’ を、0 であれば ‘.’ を src に追加する。
このように、マスクをシフトしながら、データと論理積を取るという処理はビット演算では使用頻度が高く便利なので、知らなかった人はちゃんとマスターしておいた方がよいぞ。
最後に src を関数の値として返す。