競技プログラミング風 標準C++ライブラリ入門【第4回】


競技プログラミング風 標準C++ライブラリ入門【第4回】

今回で本シリーズも最後だ。今回も競技プログラミング風問題を解いて、標準C++ライブラリにより詳しくなっていただこう。

問題を理解したら、テストコードをコンパイル・実行してほしい。そのままだと実行時に「NG」が表示されるので、 コードを完成させて、「Good Job!」を表示させていただきたい。グッドラック!

目次

配列充填(難易度:★★☆☆☆)

問題

int[] 型のar, 要素数sz, データdを受け取り、ar から sz個の要素にdを充填する関数 void my_fill(int ar[], int sz, int d) を実装しなさい。

例えば、int v[] = {0, 0, 0, 0, 0, 0, 0} のとき、my_fill(v+2, 3, 1) がコールされると、 v は {0, 0, 1, 1, 1, 0, 0} となる。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace 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 my_fill(int ar[], int sz, int d) {
    //  ToDo: 標準ライブラリの関数を使い、サイズ sz の配列 ar のすべての要素を d にする
}
int main()
{
    int ar[] = {0, 0, 0, 0, 0, 0, 0};       //  要素数:7
    const int sz = sizeof(ar)/sizeof(int);
    my_fill(ar+2, 3, 1);
    DO_TEST( vector<int>(ar, ar+sz) == vector<int>({0, 0, 1, 1, 1, 0, 0}) );
    my_fill(ar, 7, 2);
    DO_TEST( vector<int>(ar, ar+sz) == vector<int>({2, 2, 2, 2, 2, 2, 2}) );
    cout << "\nGood Job!\n";
    return 0;
}
ヒント
解答例
解説

重複除去ソート(難易度:★★★☆☆)

問題

vector<string>>参照型のlstを引数で受け取り、重複する要素を削除し、さらに小さい順にソートする関数 void uniqSort(vector<string>& lst) を実装しなさい。

例えば、{“abc”, “abb”, “abc”} が渡された場合は、”abc” が重複しているのでひとつ消され、昇順ソートされた {“abb”, “abc”} を返す。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace 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 uniqSort(vector<string>& lst) {
    //  ToDo: 標準ライブラリの関数を使い、lst の重複する要素を削除・昇順ソートする
}
int main() {
    vector<string> vs = {"abc", "xz", "ab", "ac", "abb", "xyz", "ab", "abc", "xz"};
    uniqSort(vs);
    DO_TEST(vs == vector<string>({"ab", "abb", "abc", "ac", "xyz", "xz"}));
    vector<string> vs2 = {"abc", "abc", "abc"};
    uniqSort(vs2);
    DO_TEST(vs2 == vector<string>({"abc"}));
    vector<string> vs3 = {};
    uniqSort(vs3);
    DO_TEST(vs3 == vector<string>());
    cout << "\nGood Job!\n";
    return 0;
}
ヒント
解答例
解説

順列生成(難易度:★★★☆☆)

問題

文字列を第1引数で受け取り、その文字列のすべての順列を辞書順で第2引数に格納する関数 void permutation(string str, vector<string>& lst) を実装しなさい。

例えば、”abc” が引数で渡された場合は、{“abc”, “acb”, “bac”, “bca”, “cab”, “cba”} が第2引数に格納される。

“cba” のように各文字が昇順でない場合、”aab” のように重複がある場合などにもちゃんと対応しなさい。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace 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 permutation(string str, vector<string>& lst)
{
    //  ToDo: 標準ライブラリの関数を使い、昇順に順列をすべて生成し、lst に格納する
}
int main() {
    vector<string> lst;
    permutation("abc", lst);
    DO_TEST( lst == vector<string>({"abc", "acb", "bac", "bca", "cab", "cba"}) );
    permutation("cba", lst);
    DO_TEST( lst == vector<string>({"abc", "acb", "bac", "bca", "cab", "cba"}) );
    permutation("aba", lst);
    DO_TEST( lst == vector<string>({"aab", "aba", "baa"}) );
    cout << "\nGood Job!\n";
    return 0;
}
ヒント
解答例
解説

さいごに

標準C++ライブラリ入門向けの競技プログラミング風問題を12問解いていただいた。
標準C++ライブラリを知って、使いこなせれば、いろいろなコードを楽に、かつ高品質に書けることを実感していただけたものと思っている。

本連載を機に標準C++ライブラリに興味を持っていただき、使いこなせるようになっていただけたら幸いである。

関連記事

競技プログラミング風 標準C++ライブラリ入門【第8回】

競技プログラミング風 標準C++ライブラリ入門【第8回】 今回で本シリーズも最後だ。競技プログラミング風問題を解いて、標準C++ライブラリにより詳しくなっていただこう。 問題を理解したら、テストコードをコンパイル・実行し […]
コメントなし

競技プログラミング風 標準C++ライブラリ入門【第7回】

競技プログラミング風 標準C++ライブラリ入門【第7回】 今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。 問題を理解したら、テストコードをコンパイル・実行していただきた […]
コメントなし

競技プログラミング風 標準C++ライブラリ入門【第6回】

競技プログラミング風 標準C++ライブラリ入門【第6回】 今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。 問題を理解したら、テストコードをコンパイル・実行していただきた […]
コメントなし

競技プログラミング風 標準C++ライブラリ入門【第5回】

競技プログラミング風 標準C++ライブラリ入門【第5回】 これまでに競技プログラミング風 標準C++ライブラリ入門 を4回にわたりお届けしたが、各方面に好評だったので、 おかわり(シーズン2)として【第5回】~【第8回】 […]
コメントなし

競技プログラミング風 標準C++ライブラリ入門【第4回】

競技プログラミング風 標準C++ライブラリ入門【第4回】 今回で本シリーズも最後だ。今回も競技プログラミング風問題を解いて、標準C++ライブラリにより詳しくなっていただこう。 問題を理解したら、テストコードをコンパイル・ […]
コメントなし

競技プログラミング風 標準C++ライブラリ入門【第3回】

競技プログラミング風 標準C++ライブラリ入門【第3回】 今回も、標準C++ライブラリ入門のための競技プログラミング風問題を解いて、標準C++ライブラリに親しんでいただきたい。 問題を理解したら、テストコードをコンパイル […]
コメントなし

競技プログラミング風 標準C++ライブラリ入門【第2回】

競技プログラミング風 標準C++ライブラリ入門【第2回】 今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。 問題を理解したら、テストコードをコンパイル・実行していただきた […]
コメントなし

競技プログラミング風 標準C++ライブラリ入門【第1回】

競技プログラミング風 標準C++ライブラリ入門【第1回】 標準C++ライブラリとは、C++で標準的に用意されているクラス・関数ライブラリのことだ。 ヘッダをインクルードするだけですぐに使える便利なクラス・関数が多数用意さ […]
コメントなし
筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。
  • このエントリーをはてなブックマークに追加

PAGE TOP