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();
}
|