zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC171-C「One Quadrillion and One Dalmatians」です。
ポイント
26進数もどきを扱う問題です。まずは，一般的に$n$進数を扱う方法を知っておく必要があります。$n$進法を考えるときの基本的なアイディアは，「商とあまりに注目する」です。例えば，10進数で考えます。つまり，234という数をaからjまでの10個のアルファベットで表すことを考えます。
234を10で割った商は23，あまりは4です。続いて，先ほどの商23を10で割った商は2，あまりは3です。最後に，先ほどの商2を10で割った商は0，あまりは2です。このようにして，「234」を4→3→2の順番で10進数に直すことができました。
すると，234は「2番目のアルファベット→3番目のアルファベット→4番目のアルファベット」に変換すればOKです。注意点としては，234が1始まりのインデックスを表しているという点です。つまり，1番目はa，2番目はbというようになります。すると，234は「bcd」を表していることが分かります。
今回の問題は，これを26進数で考えます。注意点としては，先ほど同様にアルファベットのインデックスと与えられた数字のインデックスを揃えなくてはならないという点です。具体的には，$n$で割った商とあまりを考えていくときに，各位の数字から1を引けば与えられた数字を0始まりのインデックスに揃えることができます。
最後の引っ掛けとして，商とあまりを考えていくと，一番右の桁から$n$進数での表現が手に入ります。実装上，例えばそれらを1つの配列に格納していくと，求めたい$n$進数での表現が逆になって出てきてしまいます。そのため，格納していった結果を逆順に戻すという作業が必要になります。
$n$進法のアイディアは商とあまり
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
char alphabet[30];
ll N;
int main(){
rep(i, 26) alphabet[i ] = 'a' + i;
cin >> N;
vector<int> X;
// n進数での表現を調べる対象が0になるまで商とあまりを考え続ける
while (N > 0){
// n進数の各桁についてNを0始まりのインデックスに揃える
N -= 1;
// Nのあまりを格納する
X.push_back(N % 26);
// 次のNは26で割った商になる
N /= 26;
}
// 空文字列ansにアルファベットを繋げていく
string ans;
rep(i, X.size()) ans += alphabet[X[i]];
// 一番右側の文字から先に入れてしまっているため逆順に戻す
reverse(ans.begin(), ans.end());
cout << ans << endl;
}
コメント