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


はじめに

今回から4回にわたって「競技プログラミング風 C++問題集」をお届けする。

出題形式は以前の「競技プログラミング風 標準C++ライブラリ入門」と同じだ。 各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。
まず、問題を読んで正しく理解し、テストコード部分をIDEやテキストエディタまたはweb上のコンパイラ (ideonなど)で保存・ビルド・実行し、 NGが出ないようにテストコードの「ToDo:」部分のコードを完成させてほしい。

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

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

目次

円・正方形サイズ比較(難易度:★★☆☆☆)

問題

円の直径 R と正方形の辺の長さ L を引数で受け取り、円のなかに正方形がすっぽり入る場合は 1 を、 逆に正方形のなかに円がすっぽり入る場合は -1 を、どちらでもない場合は 0 を返す関数 int cmpCircleSquare(int R, int L) を実装しなさい。

cmpCircleSquare(int R, int L) は、R:20, L:10 の場合は 1 を、R:10, L:20 の場合は -1 を、R:12, L:10 の場合は 0 を返す。

ただし、0 < R < 10000, 0 < L < 10000 とし、どちらかが範囲外の場合は -9999 を返すものとする。

#include <iostream>       //  標準入出力ライブラリ
#include <math.h>
#include <string>
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 cmpCircleSquare(int R, int L) {
    //  ToDo: ここに直径Rの円と辺長Lの正方形のサイズを比較するコードを記述
    return 0;
}
int main() {
    DO_TEST( cmpCircleSquare(20, 10) == 1 );
    DO_TEST( cmpCircleSquare(10, 20) == -1 );
    DO_TEST( cmpCircleSquare(10, 10) == -1 );
    DO_TEST( cmpCircleSquare(12, 10) == 0 );
    DO_TEST( cmpCircleSquare(20, 0) == -9999 );
    DO_TEST( cmpCircleSquare(0, 20) == -9999 );
    DO_TEST( cmpCircleSquare(0, 0) == -9999 );
    DO_TEST( cmpCircleSquare(20, -10) == -9999 );
    DO_TEST( cmpCircleSquare(-10, 20) == -9999 );
    DO_TEST( cmpCircleSquare(-10, -10) == -9999 );
    cout << "\nGood Job!\n";
    return 0;
}
ヒント
解答例
解説

【CG】点描画(難易度:★★☆☆☆)

問題

横幅・高さが 20×10 のスクリーン対して、(x, y) に点を描画する関数 void plot(char screen[], int x, int y) を定義しなさい。
ただし、スクリーンは左上が原点(0,0) 、右下が (19, 9) とし、 範囲外の座標が指定された場合は無視する(これをクリッピングと呼ぶ)ようにしなさい。
データ構造としては char 型の1次元配列を用い、screen[0] が (0, 0)、screen[1] が (1, 0)、screen[2] が (1, 0), … screen[20] が (0, 1) を表すものとする。 また、空白は ‘.’ で、描画された点は ‘*’ で表すものとする。

#include <iostream>       //  標準入出力ライブラリ
const int WIDTH = 20, HEIGHT = 10;  //  画面サイズ
const int SCREEN_SIZE = WIDTH * HEIGHT; //  スクリーン配列サイズ
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 char screen[]) {
    int ix = 0;
    for (int y = 0; y < HEIGHT; ++y) {
        for (int x = 0; x < WIDTH; ++x) {
            cout << screen[ix++];
        }
        cout << "\n";
    }
    cout << "\n";
}
void plot(char screen[], int x, int y) {        //  (x, y) に点をプロット
    //  ToDo: ここに (x, y) に点をプロットするコードを記述
}
int main() {
    char screen[SCREEN_SIZE];
    for(auto& x: screen) x = '.';   //  スクリーンクリア
    plot(screen, 0, 0);
    print(screen);
    DO_TEST( string(screen, screen+SCREEN_SIZE) ==
                "*..................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................." );
    plot(screen, 1, 1);
    print(screen);
    DO_TEST( string(screen, screen+SCREEN_SIZE) ==
                "*..................."
                ".*.................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................." );
    plot(screen, 1, 11);    //  スクリーン外をプロットした場合は無視(クリッピング)
    print(screen);
    DO_TEST( string(screen, screen+SCREEN_SIZE) ==
                "*..................."
                ".*.................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................." );
    plot(screen, 19, 0);
    print(screen);
    DO_TEST( string(screen, screen+SCREEN_SIZE) ==
                "*..................*"
                ".*.................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................." );
    plot(screen, 0, 9);
    print(screen);
    DO_TEST( string(screen, screen+SCREEN_SIZE) ==
                "*..................*"
                ".*.................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................."
                "...................."
                "*..................." );
    cout << "\nGood Job!\n";
    return 0;
}
ヒント
解答例
解説

関連記事

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

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

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

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

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

目次 ‘1’~’3’を’a’~’c’に置換(難易度:★★☆☆☆) 逆ポーランド記法(難易度:★★★☆☆) ‘1& […]
コメントなし

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

はじめに 今回から4回にわたって「競技プログラミング風 C++問題集」をお届けする。 出題形式は以前の「競技プログラミング風 標準C++ライブラリ入門」と同じだ。 各問題は、「問題文」「テストコード」「ヒント」「解答例」 […]
コメントなし
筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。
  • このエントリーをはてなブックマークに追加

PAGE TOP