yukicoder No.254 文字列の構成 (2Q)

yukicoder で「構築」練習することにした！

• 問題へのリンク

問題概要

英小文字からなる文字列 であって、次の条件を満たすものを求めよ。

• 文字数は 以下である
• どの隣接する文字も相異なる
• の連続する部分文字列であって、回文であるものがちょうど 個存在する

制約

• 

考えたこと

基本的に

---

"abababab...aba"

---

のような文字列を、文字を変えて繋げていけばよさそうだと考えた。

まず、上の文字列において、文字 'a' が 個あるときに、回文である連続文字列が何個あるかを求めてみた。そうすると......

• 長さ のもの： 個
• 長さ のもの： 個
• 長さ のもの： 個
• ...
• 長さ のもの： 個

これらを足すと、なんと綺麗に となるのである。

よって、もとの問題は「整数 を平方数の和として表せ」という問題となったのだ。

基本的には Greedy で良いと考えた。つまり、「 以下の最大の平方数を として、 から を引く」を繰り返せばよいと。

最後に、この方針で文字列の長さが 以下になるかどうかを確かめた。 でも、文字列の長さは 63725 であったので大丈夫だった。

コード

#include <bits/stdc++.h>
using namespace std;

// a -> 1
// aba -> 4
// ababa -> 9
// abababa -> 16

const long long MAX = 100000;

int main() {
    string res = "";
    char letter = 'a';
    
    long long N;
    cin >> N;
    while (N > 0) {
        long long low = -1, high = MAX;
        while (high - low > 1) {
            long long x = (low + high) / 2;
            if (x * x <= N) low = x;
            else high = x;
        }
        res += letter;
        for (int i = 0; i < low - 1; ++i) {
            res += (char)(letter + 1);
            res += letter;
        }
        N -= low * low;
        letter += 2;
    }
    cout << res << endl;
}