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


はじめに

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

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

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

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

目次

任意精度整数 加算(難易度:★★☆☆☆)

問題

「任意精度整数」とは、精度(桁数)を必要なら(メモリが許す限り)いくらでも伸ばす(増やす)ことができる整数のことだ。 本問題では、”31415926535″ のように、string 型の数字文字列で任意精度整数を表すものとする。
というわけで、string 型の任意精度整数2つを引数で受け取り、その和の任意精度整数文字列を返す関数 string add(const string& x, const string& y) を実装しなさい。

例えば、add(“123”, “1234”) は、”1357″ を、add(“99”, “1”) は、”100″ 返す。

#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 add(const string& x, const string& y) {
    //  ToDo: ここにコードを記述し、引数の和を文字列として返す
    return "";
}
int main() {
    DO_TEST(add("100", "123") == "223");
    DO_TEST(add("999", "1") == "1000");
    DO_TEST(add("31", "999") == "1030");
    DO_TEST(add("314159265358979323846", "999") == "314159265358979324845");
    cout << "3141592653589793238462643383279 + 5028841971693993751058209749445923078164 = ";
    cout << add("3141592653589793238462643383279", "5028841971693993751058209749445923078164") << "\n";
    DO_TEST(add("3141592653589793238462643383279", "5028841971693993751058209749445923078164")
                == "5028841974835586404648002987908566461443");
    cout << "\nGood Job!\n";
    return 0;
}
ヒント
解答例
解説

任意精度整数 乗算(難易度:★★☆☆☆)

問題

string 型の任意精度整数(前問参照)を2つ引数で受け取り、その積の任意精度整数文字列を返す関数 string mul(const string& x, const string& y) を実装しなさい。
また、その下請け関数として、string 型の任意精度整数と1文字を引数で受け取り、その積の任意精度整数文字列を返す関数 string mul(const string& x, char c) も実装しなさい。

例えば、mul(“123”, ‘2’) は “246” を、mul(“22”, “22”) は “464” を返す。

#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 add(const string& x, const string& y) {  //  mul() の下請けとして使用する加算関数
    auto mxl = max(x.size(), y.size());
    string ans(mxl, ' ');
    int carry = 0;
    auto ix = x.rbegin();
    auto iy = y.rbegin();
    for(auto itr = ans.rbegin(); itr != ans.rend(); ++itr) {
        char cx = ix != x.rend() ? *ix++ : '0';
        char cy = iy != y.rend() ? *iy++ : '0';
        *itr = cx + cy - '0' + carry;
        if( *itr > '9' ) {      //  桁上りの場合
            carry = 1;
            *itr -= 10;
        } else
            carry = 0;
    }
    if( carry )
        ans = '1' + ans;
    return ans;
}
string mul(const string& data, char c) {
    //  ToDo: ここにコードを記述し、引数の積を文字列として返す
    return "";
}
string mul(const string& x, const string& y) {
    //  ToDo: ここにコードを記述し、引数の積を文字列として返す
    return "";
}
int main() {
    DO_TEST( mul("123", '0') == "0" );
    DO_TEST( mul("0", '2') == "0" );
    DO_TEST( mul("123", '2') == "246" );
    DO_TEST( mul("55", '5') == "275" );
    DO_TEST( mul("999", '9') == "8991" );
    //
    DO_TEST( mul("11", "11") == "121" );
    DO_TEST( mul("999", "9") == "8991" );
    //
    const int LIMIT = 69;
    string ans = "1";
    for (int m = 2; m <= LIMIT; ++m) {
        ans = mul(ans, to_string(m));
    }
    cout << LIMIT << "! = " << ans << "\n";
    //
    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