これは、、、桁和を求めるタイプの問題の応用ではある
問題概要
数値を文字列に置き換える。ただしそのルールは
- 1,2,⋯,26 は、その順に a, b, ..., z
- 27,28,29,⋯,701,702 は、その順に aa, ab, ac, ..., zy, zz
- 703,704,705,⋯,18277,18278 は、その順に aaa, aab, aac, ..., zzy, zzz
- 18279,18280,18281,⋯,475253,475254 は、その順に aaaa, aaab, aaac, ..., zzzy, zzzz
- ...
という風にする。正の整数 が与えられるので、対応する文字列を答えよ。
制約
考えたこと
ひとまず 0-indexed で考えることにしよう。0 番目からスタートして、
a,b,...,z,aa,ab,...,az,ba,bb,...,bz,...,za,zb,...,zz,aaa,aab,...,aaz,aba,abb,...,abz,...,zzz,aaaa,...
という風に並んでいると考えることにする。そうすると、今回の問題は、一瞬「整数を 26 進法で表せ」という問題なのではないかと思えてくる。もしそうであるならば、例によって
while (cin >> N) { int c = N % 26; // 各桁の値 N /= 26; }
という感じの処理で、各桁の値を求めることができる。なおこの処理は、"一の位" の値から順に求めている。そして、各桁の値を対応する文字にすれば、文字列を求めることができる...はずであった。
しかしこれは、
- 0 = "a"
- 1 = "b"
- ...
- 25 = "z"
まではよいが、この次が本来なら
- 26 = "ba"
になるべきなのだ (二桁になって最小の数は "10" なので)。しかし今回は 26 = "aa" となっている。歪な 26 進法になっている。
修正
しかし今回の問題の場合も、ほんの少しの修正で対応することができる。一の位から順に決めていくのは変わらない。
まず、一の位がどうなるべきかを考えてみよう。一の位にだけ注目すると
'a', 'b', ..., 'z', 'a', 'b', ..., 'z', 'a', 'b', ..., 'z', ...
を繰り返していることがわかる。よって、一の位は、
- N % 26
によって求めることができる。次に、十の位以降について考える。まず、何番目の ('a', 'b', ..., 'z') のグループに属しているかを知るために、
- N /= 26
と処理する。改めて、十の位に注目すると、
' ', 'a', 'b', ..., 'z', 'a', 'b', ..., 'z', 'a', 'b', ..., 'z', ...
という風になる。つまり、先頭に空文字 ' ' があって、その後で 'a', 'b', ..., 'z' の繰り返す感じになる。よって、十の位の値は
- N == 0 なら、特になにもせずに break
- それ以外なら、N から 1 を引いた上で、N % 26
によって求めることができる。百の位以降もこれを繰り返せば OK。
実装
実装上は、与えられた数列の先頭に空文字列 "" を付け加えて、
"", "a", "b" ,..., "z", "aa", "ab", ... , "az", "ba", "bb" , ..., "bz", ..., "za", "zb", ..., "zz", "aaa", "aab", ..., "aaz", "aba", "abb", ..., "abz", ..., "zzz", "aaaa", ...
と考えてあげることで、一の位の処理を特別扱いせずに統一的に考えることができる。つまり、以下の繰り返しによって処理することができる。
- N = 0 ならば break
- それ以外ならば N から 1 を引いた上で、N % 26 を桁に加える
- N /= 26 とする
計算量は となる。
#include <bits/stdc++.h> using namespace std; int main() { long long N; cin >> N; string res = ""; while (N) { --N; res += (char)('a' + (N % 26)); N /= 26; } reverse(res.begin(), res.end()); cout << res << endl; }