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


はじめに

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

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

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

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

目次

単語先頭英文字を大文字に(難易度:★★☆☆☆)

問題

引数で与えられた string& 型文字列の半角英字で始まる英数字列の先頭文字を大文字に、2文字目以降は小文字に置換した文字列を返す関数 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;
}
ヒント
解答例
解説

配列90度回転(難易度:★★☆☆☆)

問題

8×8 の2次元画像を表す文字列があるとき、この画像を時計方向に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;
}
ヒント
解答例
解説

関連記事

競技プログラミング風 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