はまやんはまやんはまやん

hamayanhamayan's blog

ひとりしりとり [yukicoder No.701]

https://yukicoder.me/problems/no/701

考察

1. 20文字の文字列は全部で26^20個あるので、使える単語はかなりたくさんある
2. 条件を満たす単語列をなるべく簡単に構築できるように考えよう
3. 「しりとりを真面目にやると大変そう」→「a???????a」でつなげればいいのでは?
4. a???????aの単語の数は、26^18個なので、十分にたくさんある
5. ??????の部分は辞書順で最小のものから使っていけばダブらず構築できる

解説

https://yukicoder.me/submissions/266342

N-1個はa?????????aで構築し、最後だけanを答えよう。
?????????の部分は辞書順で最小のものから構築していくが、進数変換の要領でやっていこう。
注意であるが、以下の実装では正確には辞書順で最小のものからの構築にはなっていない。
桁の上下が逆さまになっているが、重複はしないので放置してある。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    int idx = 0;
    rep(i, 0, N - 1) {
        printf("a");
        int x = idx;
        rep(j, 0, 18) {
            char c = 'a' + x % 26;
            x /= 26;
            printf("%c", c);
        }
        printf("a\n");
        idx++;
    }
    printf("an\n");
}