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

はじめに

今回から４回にわたって「競技プログラミング風 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 を返すものとする。
[java] #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;
}
[/java]

ヒント

・正方形の辺の長さ >= 円の直径ならば、正方形の中に円がすっぽり入るぞ。
・円の直径 >= 正方形の辺の長さ*√2 であれば、円の中に正方形がすっぽり入るぞ。
・√2 は sqrt(2) で計算できるぞ。

解答例

[java] int cmpCircleSquare(int R, int L) {
if (R <= 0 || R >= 10000 || L <= 0 || L >= 10000 ) // R, L が制約を満たさない場合
return -9999;
if (L >= R) return -1; // 正方形の中に円がすっぽり入る
if (R * R >= L * L * 2 * 2) return 1; // 円の中に正方形がすっぽり入る
return 0; // 円・正方形が重なる場合
}
[/java]

解説

最初に R, L の範囲チェックを行い、制約を満たしていない場合は -9999 を返す。

正方形の辺の長さ >= 円の直径ならば、正方形の中に円がすっぽり入るので、-1 を返す。

円の直径 >= 正方形の辺の長さ*√2< ならば、エンの中に正方形がすっぽり入るので 1 を返す。 √2 は整数ではないので sqrt(2) とし、浮動小数点で計算してもいいのだが、回答例のように左辺・右辺を自乗し、比較してもより。

最後に、どちらもすっぽり入らない場合は 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) を表すものとする。また、空白は ‘.’ で、描画された点は ‘*’ で表すものとする。
[java] #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;
}
[/java]

ヒント

・スクリーン配列に点描画する前に座標 (x, y) が有効な範囲内かどうかをチェックする必要があるぞ。
・座標 (x, y) をスクリーンのインデックスに変換するには x + y * WIDTH と計算すればいいぞ。
・点を描画するには、座標 (x, y) に対応する位置に ‘*’ を書き込むだけだぞ。

解答例

[java] void plot(char screen[], int x, int y) { // (x, y) に点をプロット
if (x < 0 || x >= WIDTH || y < 0 || y >= HEIGHT) return; // クリッピング
screen[x + y * WIDTH] = ‘*’;
}
[/java]

解説

スクリーン配列に点描画を行う前に座標 (x, y) が有効な範囲内かどうかをチェックする必要がある。回答例のように、x, y が有効範囲外だった場合は、すぐにリターンするだけだ。これをクリッピングという。

本問題でのスクリーンは１次元配列で、座標 (x, y) は２次元なので、２次元座標を１次元のインデックスに変換する必要がある。具体的には「x + y * WIDTH」と計算すればよい。WIDTH はスクリーンの幅で、本問題のテストコードでは 20 と定義されている。

したがって、回答例のように「screen[x + y * WIDTH] = ‘*’;」と記述すれば、指定位置に点を描画できる、というわけだ。