けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 171 C - One Quadrillion and One Dalmatians (茶色, 300 点)

これは、、、桁和を求めるタイプの問題の応用ではある

問題へのリンク

問題概要

数値を文字列に置き換える。ただしそのルールは

  • 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
  • ...

という風にする。正の整数  N が与えられるので、対応する文字列を答えよ。

制約

  •  1 \le N \le 1000000000000001

考えたこと

ひとまず 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 とする

計算量は  O(\log N) となる。

#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;
}