yukicoder：No.701 ひとりしりとり

スペシャルジャッジ問題は面白いなぁ

問題概要

---

yukicoder.me

ちょうど 個の単語でしりとりをせよ。ただし次のルールを守る必要がある。

• 小文字アルファベットのみからなる ~ 文字の単語のみ使用できる。
• 単語の末尾と次の文字を同じにする必要がある。
• 最後以外の単語の末尾は n 以外、最後の単語の末尾は n である必要がある。
• はじめの単語には上記ルールに従う任意の単語を用いてよい。
• 同じ単語は用いてはならない。

制約

• 

解法

---

結論から述べると、 ~ 個目の単語として

a + (かぶらない 文字の単語) + a

を用いて 個目に an を用いて終わらせばよい。

文字の単語には aaaaa ~ zzzzz の 通りのバリエーションがあるので 通りは十分表現可能。

24 1 3 4 5

25 1 3 4 5

0 2 3 4 5

という風に配列で繰り上がりを表現して 通り作ればよい。

コード

---

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define mod 1000000007ll
#define loop(i, n) for (int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
#define putout(a) cout << a << '\n'
#define Sum(v) accumulate(all(v), 0ll)

int main()
{
    ll N;
    cin >> N;
    vector<ll> num(5);
    loop(i, N - 1)
    {
        string now;
        num[0]++;
        ll j = 0;
        while (num[j] == 26)
        {
            num[j] = 0;
            num[j + 1]++;
            j++;
        }
        loop(j, 5) now += (char)('a' + num[j]);
        cout << "a" << now << "a" << endl;
    }
    putout("an");
    return 0;
}