Chef Hates Palindromes [CodeChef November Challenge 2017 D]

https://www.codechef.com/NOV17/problems/CHEFHPAL

以下を満たす、N文字の文字列を構築する。

• A種類の文字からなる（小さい方から順に使う）
• 回分である任意の部分文字列の長さが最小

回分である任意の部分文字列の長さの最小値と共に答えよ

解法

実験によって規則性を暴く。

A=1の時
全体が回文となってしまうので、最小値はNで、"aaaa..."が答え
3≦Aの時
abcabcabc...とabcを続けていけば回文が作れないので、最小値は1で、"abcabc..."が答え
A=2の時
以下の実験コードで実験する

void test() {
    rep(n, 1, 18) {
        int mi = 101010;
        vector<string> v;
        rep(msk, 0, 1 << n) {
            string s = "";
            rep(i, 0, n) {
                if (msk & (1 << i)) s += "a";
                else s += "b";
            }
 
            int cnt = 0;
            rep(l, 0, n) rep(r, l, n) {
                int ok = 1;
                int ll = l, rr = r;
                while (ll < rr) {
                    if (s[ll] != s[rr]) ok = 0;
                    ll++; rr--;
                }
                if (ok) cnt = max(cnt, r - l + 1);
            }
            if (cnt < mi) {
                mi = cnt;
                v.clear();
            }
            if(cnt == mi) v.push_back(s);
        }
 
        sort(v.begin(), v.end());
 
        printf("[%d -> %d] ", n, mi);
        fore(s, v) printf("%s ", s.c_str());
        printf("\n");
    }
}

実験により、9≦Nは最小値が4で固定になりそうである。
そのため、少し面倒だが、8以下は実験によって得られた最適解を答えておく。
9≦Nでは頑張って探すと「aababb」をくっつけていくことによって最小値が4となるように構築できると見つかる。
それを答える。

>|cpp|
int N, A;
string magic = "aababb";
//---------------------------------------------------------------------------------------------------
void solve() {
cin >> N >> A;

int cnt = 0;
string ans = "";

if (A == 1) {
cnt = N;
rep(i, 0, N) ans += 'a';
}
else if (A == 2) {
if (N == 1) cnt = 1, ans = "a";
else if (N == 2) cnt = 1, ans = "ab";
else if (N == 3) cnt = 2, ans = "aab";
else if (N == 4) cnt = 2, ans = "aabb";
else if (N == 5) cnt = 3, ans = "aabbb";
else if (N == 6) cnt = 3, ans = "bbbaba";
else if (N == 7) cnt = 3, ans = "aaababb";
else if (N == 8) cnt = 3, ans = "aaababbb";
else {
cnt = 4;
rep(i, 0, N) ans += magic[i % 6];
}
} else {
cnt = 1;
rep(i, 0, N) ans += char('a' + (i % 3));
}

printf("%d %s\n", cnt, ans.c_str());
}
//---------------------------------------------------------------------------------------------------
void _main() {
int T; cin >> T;
rep(t, 0, T) solve();
}
|