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

はじめに

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

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

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

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

任意精度整数加算（難易度：★★☆☆☆）

問題

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

例えば、add(“123”, “1234”) は、”1357″ を、add(“99”, “1”) は、”100″ 返す。
[java] #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;
}
[/java]

ヒント

・文字列の文字はメモリ内では数字で表される。例えば、UTF-8, ASCII などでは ‘0’ は0x30 だ。
・’1′, ‘2’, … ‘9’ には連続的な数字で表されるので、文字 ch を数値に変換するには ch – ‘0’ とするとよい。
・上記を考慮して下位の桁から順番に加算していくんだぞ。

解答例

[java] #if 1
string add(const string& x, const string& y) {
auto mxl = max(x.size(), y.size());
string ans(mxl, ‘ ‘);
int carry = 0; // 桁上りの場合は 1
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; // 1X → X
} else
carry = 0; // 桁上りなし
}
if( carry ) // 桁上りが残っていた場合
ans = ‘1’ + ans;
return ans;
}
#else
string add(const string& x, const string& y) {
auto mxl = max(x.size(), y.size());
string ans(mxl, ‘ ‘);
int carry = 0; // 桁上りの場合は 1
auto px = &x[0] + x.size();
auto py = &y[0] + y.size();
for(auto ptr = &ans[0] + ans.size(); ptr != &ans[0]; ) { // 答えも下位の桁から順に計算
char cx = px != &x[0] ? *–px : ‘0’;
char cy = py != &y[0] ? *–py : ‘0’;
*–ptr = cx + cy – ‘0’ + carry;
if( *ptr > ‘9’ ) { // 桁上りの場合
carry = 1;
*ptr -= 10; // 1X → X
} else
carry = 0; // 桁上りなし
}
if( carry ) // 桁上りが残っていた場合
ans = ‘1’ + ans;
return ans;
}
#endif
[/java]

解説

結果を格納する文字列 ans を用意しておく。長さは加算する文字列の桁数の多い方の長さに設定しておく。最後に桁上りがなければそれが答えの長さとなる。
加算は下位の桁から順に計算していくので、rbegin() をにより逆イテレータを取得・使用する。
以上を先頭文字まで繰り返す。最後の桁で桁上りがあった場合は、答え文字列の先頭に ‘1’ を付加する。そして結果文字列をリターンする。

逆イテレータには慣れてなくて難しいという人もいるかもしれないので、通常のポインタを使用する版も解答例の #if でコメントアウトされた部分に示しておく。

任意精度整数乗算（難易度：★★☆☆☆）

問題

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

例えば、mul(“123”, ‘2’) は “246” を、mul(“22”, “22”) は “464” を返す。
[java] #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;
}
[/java]

ヒント

・文字列の文字はメモリ内では数字で表される。例えば、UTF-8, ASCII などでは ‘0’ は0x30 だ。
・’1′, ‘2’, … ‘9’ には連続的な数字で表されるので、文字 ch を数値に変換するには ch – ‘0’ とするとよい。
・上記を考慮して上位の桁から順番に乗算していくんだぞ。

解答例

[java] string mul(const string& m, char c) { // 任意精度整数と1文字を乗算
if( c == ‘0’ || m == "0" ) return "0"; // どちらかが0の場合
c -= ‘0’; // ‘0’～’9′ を 0～9 に変換
string ans(m.size(), ‘ ‘);
auto im = m.rbegin(); // 逆イテレータ、下位の桁から順に乗算するため
int carry = 0; // 桁上り
for(auto itr = ans.rbegin(); itr != ans.rend(); ++itr) {
int t = (*im++ – ‘0’) * c + carry; // 乗算＋桁上り
carry = t / 10; // 桁上り
*itr = (t % 10) + ‘0’; // ひとけた目の数値を文字に変換し格納
}
if( carry != 0 ) // 桁上りがあった場合
ans = (char)(carry + ‘0’) + ans;
return ans;
}
string mul(const string& x, const string& y) {
string ans = "0"; // 積和のための文字列
for(auto itr = y.begin(); itr != y.end(); ++itr) { // 上位桁から順に乗算
auto t = mul(x, *itr);
ans = add(ans + ‘0’, t); // 以前の積和を10倍し、１桁の乗算結果を加える
}
return ans;
}
[/java]

解説

まずは、任意精度整数と1文字を乗算する string mul(const string& m, char c) を実装する。
m が “0” または c が ‘0’ であれば、乗算結果は 0 なので、”0″ を返す。
c -= ‘0’ で、数字文字を数値に変え、m の下位桁から順に、桁上りを考慮しつつ乗算していく。

1文字との乗算が出来上がれば、任意精度整数同士の乗算は簡単だ。答えを入れる変数 ans を用意しておき、乗数の上位から順に被乗数に先の mul() 関数を使って乗算を行い、 ans を10倍しながら、結果を ans に足し込んでいく。全桁の乗算が終われば答えを返すだけだ。