はじめに
競技プログラミングで時々必要になる基数変換の汎用的なテンプレートを作成しました。
テンプレートの機能
-
n進数 → 10進数:
to_decimal() -
10進数 → m進数:
from_decimal() -
n進数 → m進数:
convert_base() -
対応範囲: 2進数から最大36進数まで（数字
0-9と英小文字a-zを使用）
基数変換テンプレ
ヘッダー（#include <string>）とusing宣言（using ll = long long;,using namespace std）を追加すれば、そのままコピペで使えます。
//ヘッダー
#include <string>
//using宣言
using namespace std;
using ll = long long;
//n進数(string)から10進数(long long)へ
ll to_decimal(const string& str, int n){
ll decimal_value = 0;
for(char c : str){
ll digit;
if('0' <= c && c <= '9') digit = c - '0';
else digit = c - 'a' + 10;
decimal_value = decimal_value * n + digit;
}
return decimal_value;
}
//10進数(long long)からm進数(string)へ
string from_decimal(ll decimal_value, int m){
if(decimal_value == 0) return "0";
const string chars = "0123456789abcdefghijklmnopqrstuvwxyz";
string res = "";
while(decimal_value > 0){
res = chars[decimal_value % m] + res;
decimal_value /= m;
}
return res;
}
//n進数(string)からm進数(string)へ
string convert_base(const string& str, int n, int m){
return from_decimal(to_decimal(str, n), m);
}
サンプルコード
#include <iostream>
#include <string>
// using宣言
using namespace std;
using ll = long long;
//基数変換テンプレ
ll to_decimal(const string& str, int n){/*...*/}
string from_decimal(ll decimal_value, int m){/*...*/}
string convert_base(const string& str, int n, int m){/*...*/}
int main() {
// 例: 16進数 "ff" を 2進数に変換して出力する
string result = convert_base("ff", 16, 2);
cout << result << endl; // 出力: 11111111
return 0;
}
練習問題
ここで紹介したテンプレートを使って解ける練習問題です。今後、執筆者がこのテンプレを使用して問題を解き次第、順次追加していく予定です。
-
競プロ典型 90 問 - 067 - Base 8 to 9（★2）
- 問題概要: 8進数の数値を9進数に変換する、という操作をK回繰り返します。9進数で'8'が登場したら'5'に置き換えるという操作もあります。
まとめ
本記事では、競技プログラミングで汎用的に使える基数変換のC++テンプレートを紹介しました。
n進数 → 10進数 → m進数 の2ステップで変換するのが基本方針です。
ぜひ、このテンプレートを使用して問題を解いてもらえればと思います。