読者です 読者をやめる 読者になる 読者になる

sataniC++

C++、競プロ、数学などについて色々考えたりします。

yukicoder No.327 アルファベット列

問題

問題のURLはこちらです。
No.327 アルファベット列 - yukicoder

考えたこと

出力する文字列をSとおきます。

Nの値とそれに対応する文字列Sは次の通り。

N 0 1 2 ... 25 26 27 ... 51 52 53 ...
S A B C ... Z AA AB ... AZ BA BB ...

この表の関係を見ると、ちょうどN26のときにSの文字数が1増えていますね。
よって、「SN26進数で表したものの文字列」と考えました。


進数変換については、こちらの記事を参照してください。
satanic0258.hatenablog.com

なお、Sについて、右から数えて1文字目はN26で割った余り0,1,...,24,25がA,B,...,Y,Zに対応しているのに対し、右から数えて2文字目以降は1,2,...,25,26がA,B,...,Y,Zに対応していることに注意する必要があります。

コード

#85429 No.327 アルファベット列 - yukicoder

#include <iostream>
#include <vector>

using ll = long long int;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    ll n;
    std::vector<char> str;
    std::cin >> n;

    do{
        str.push_back(n%26+'A');
        n/=26;
        --n;
    }while(n!=-1);

    for(auto rit=str.rbegin(); rit!=str.rend(); ++rit){
        std::cout << *rit;
    }
    std::cout << "\n";

    return 0;
}

コードの説明など

do{
    str.push_back(n%26+'A');
    n/=26;
    --n;
}while(n!=-1);

C++では'A'も整数として扱われているため、'A'にAからの差分であるN26で割った余りを加えることで、全てのアルファベットを表現することが出来ます。

また、右から数えて2文字目以降は1文字目に対して1大きい値となっているため、ループの最後でNから1を引いています。

for(auto rit=str.rbegin(); rit!=str.rend(); ++rit){
    std::cout << *rit;
}

ループの部分で、1桁目から順に「str.push_back」しているため、strの中身は表示したい文字列とは逆順に文字が格納されています。
そのため、strの中身をreverse_iteratorを使って後ろから順に出力するようにしています。

備考

10進数の非負整数N26進数で表す操作をしているため、計算量はO(\lfloor \log_{26}N \rfloor)となります。(計算量についてまだ正確に理解していない部分もあるので、間違っているかもしれません。。)

感想など

進数変換をする問題としては結構基本的な問題だと思います。
右から2文字目以降のずれや、入力が32bit整数に収まらないことなどに注意すれば大丈夫ですね。