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


はじめに

今回から4回にわたって「競技プログラミング風 C++問題集 第5回~第8回(シーズン2)」をお届けする。

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

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

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

目次

グリコ遊び(難易度:★★☆☆☆)

問題

Aさん・Bさんの二人でじゃんけんを行い、勝者がグーを出した場合は3歩、チョキ・パーの場合は6歩進むものとする (負け・引き分けの場合は進めない)。 このとき、二人の手の出し方を文字列引数で受け取り、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;
}
ヒント
解答例
解説

【CG】データ→画像変換(難易度:★★☆☆☆)

問題

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

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

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

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

競技プログラミング風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;
}
ヒント
解答例
解説

関連記事

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

目次 0/1ナップサック問題(難易度:★★★★☆) 0/1ナップサック問題(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主 […]
コメントなし

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

目次 ポーカー:役判定(難易度:★★★☆☆) ポーカー:役判定(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi […]
コメントなし

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

目次 無向グラフ(難易度:★★★☆☆) 無向グラフ(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が […]
コメントなし

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

はじめに 今回から4回にわたって「競技プログラミング風 C++問題集 第13回~第16回(シーズン4)」をお届けする。 各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。 まず、問題を読んで […]
コメントなし

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

目次 文字列比較(難易度:★★★★☆) 文字列比較(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が […]
コメントなし

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

目次 クローズド・ナイト・ツアー(難易度:★★★★☆) クローズド・ナイト・ツアー(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研 […]
コメントなし

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

目次 オセロ:石反転(難易度:★★★☆☆) 両端キュー(難易度:★★★☆☆) オセロ:石反転(難易度:★★★☆☆) 両端キュー(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・ […]
コメントなし

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

はじめに 今回から4回にわたって「競技プログラミング風 C++問題集 第9回~第12回(シーズン3)」をお届けする。 各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。 まず、問題を読んで正 […]
コメントなし

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

目次 文字列クラス(難易度:★★★★☆) 文字列クラス(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C+ […]
コメントなし

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

目次 数独(難易度:★★★☆☆) 数独(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中 […]
コメントなし
筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。
  • このエントリーをはてなブックマークに追加

PAGE TOP