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

はじめに

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

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

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

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

単語先頭英文字を大文字に（難易度：★★☆☆☆）

問題

引数で与えられた string& 型文字列の半角英字で始まる英数字列の先頭文字を大文字に、２文字目以降は小文字に置換した文字列を返す関数 string capitalize(const string& txt) を実装しなさい。
ただし、単語と単語の区切りは半角空白またはタブのみとする。

例えば、”abc XYZZZ 1zb #abc” が与えられた場合は、”Abc Xyzzz 1zb #abc” を返す。

#include <iostream>       //  標準入出力ライブラリ
#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);
}
string capitalize(const string& txt) {
    //  ToDo: ここにコードを記述し、キャピタライズした文字列を返す
    return "";
}
int main() {
    DO_TEST( capitalize("") == "" );
    DO_TEST( capitalize("abc") == "Abc" );
    DO_TEST( capitalize("ABC") == "Abc" );
    DO_TEST( capitalize("ab2c xyzzz") == "Ab2c Xyzzz" );
    DO_TEST( capitalize("ab2c\txyzzz") == "Ab2c\tXyzzz" );
    DO_TEST( capitalize("AB2C XYZZZ") == "Ab2c Xyzzz" );
    cout << "\nGood Job!\n";
    return 0;
}

ヒント

・文字が英字かどうかをチェックするには isalpha(char) を使うんだぞ。
・文字が英数字かどうかをチェックするには isalnum(char) を使うんだぞ。
・英小文字を大文字に変換するには char toupper(char) を使うんだぞ。
・英大文字を小文字に変換するには char tolower(char) を使うんだぞ。

解答例

string capitalize(const string& txt) {
    string t;       //  変換結果格納用 文字列
    for (int i = 0; i != txt.size();) {
        if( isalpha(txt[i]) ) {         //  英字の場合
            t += toupper(txt[i++]);     //  大文字変換
            while( i != txt.size() && isalnum(txt[i]) )     //  英数字の場合
                t += tolower(txt[i++]);     //  英小文字変換
        } else {    //  英字以外の場合
            do {
                t += txt[i++];
            } while ( i != txt.size() && txt[i] != ' ' && txt[i] != '\t' );     //  単語区切り文字・末尾までループ
        }
        while( i != txt.size() && (txt[i] == ' ' || txt[i] == '\t') )   //  単語区切り文字の場合
            t += txt[i++];
    }
    return t;
}

解説

結果を格納する文字列 t を用意しておく。 for 文で元の文字列から１文字ずつ取り出し、それが半角英字であれば、大文字に変換し、結果格納用文字列に追加する。それ以降変革英数字が続くあいだ小文字に変換し、結果文字列に追加する。
英字以外の場合は、末尾または単語区切り文字（半角空白・タブ）が現れるまで結果格納用文字列に追加していく。
どちらの場合でも、その後に続く単語区切り文字を結果文字列に追加する。
以上を末尾まで繰り返し、最後に結果文字列をリターンする。

配列90度回転（難易度：★★☆☆☆）

問題

8×8 の２次元画像を表す文字列があるとき、この画像を時計方向に90度回転させる関数 void rotate90(string& data) を実装しなさい。

例えば、下図左のような画像は、下図右の画像文字列に変換される。

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

なお、引数で渡された文字列長が64でない場合は、なにも処理を行わないものとする。

#include <iostream>       //  標準入出力ライブラリ
#include <string>
const int WIDTH = 8, HEIGHT = 8;  //  画面サイズ
typedef unsigned char uchar;
using namespace std;    //  std 名前空間使用
#define     WIDTH       8       //  横サイズ
#define     HEIGHT      8       //  縦サイズ
#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);
}
inline int xyToIX(int x, int y) { return x + y * WIDTH; }
void print(const string& data) {    //  画像文字列表示関数
    for(int y = 0; y != HEIGHT; ++y) {
        for(int x = 0; x != WIDTH; ++x) cout << data[xyToIX(x,y)];
        cout << "\n";
    }
    cout << "\n";
}
void rotate90(string& data) {
    //  ToDo: ここにdataを時計方向に90度回転するコードを記述
}
int main() {
    string img =    "*******."
                    "*......*"
                    "*......*"
                    "*******."
                    "*......."
                    "*......."
                    "*......."
                    "*.......";
    rotate90(img);
    print(img);
    DO_TEST( img == "********"
                    "....*..*"
                    "....*..*"
                    "....*..*"
                    "....*..*"
                    "....*..*"
                    "....*..*"
                    ".....**." );

    string img2 =   "......*."
                    ".......*"
                    "..**...*"
                    ".......*"
                    ".......*"
                    "..**...*"
                    ".......*"
                    "......*.";
    rotate90(img2);
    print(img2);
    DO_TEST( img2 == "........"
                    "........"
                    "..*..*.."
                    "..*..*.."
                    "........"
                    "........"
                    "*......*"
                    ".******." );
    cout << "\nGood Job!\n";
    return 0;
}

ヒント

・２次元座標 (x, y) を１次元配列インデックスに変換するには x + y * WIDTH を計算するといいぞ。
・回転結果を格納する string オブジェクトを用意しておき、そこに回転した結果を順に格納していくといいぞ。

解答例

void rotate90(string& data) {
    if( data.size() != WIDTH * HEIGHT ) return;     //  データ長が不正な場合
    string t(WIDTH*HEIGHT, ' ');     //  回転結果格納用 string
    for(int y = 0; y != HEIGHT; ++y) {
        for(int x = 0; x != WIDTH; ++x) {
            t[xyToIX(x, y)] = data[xyToIX(y, HEIGHT-1-x)];
        }
    }
    data = t;   //  回転結果を参照引数に代入
}

解説

最初にデータが縦*横=64だけあるかどうかをチェックする。
回転結果を格納する string 型のオブジェクト t を用意しておく。サイズは WIDTH*HEIGHT に for文で y と x を回し、90度回転した位置の文字を取り出し、t に格納していく。最後に結果文字列を仮引数の data にコピーする。