https://www.codechef.com/NOV17/problems/PERPALIN
以下の条件を満たす長さNの文字列を構築せよ。
無理なら"impossible"
- 'a'と'b'の両方の文字から成る(どちらかはダメ)
- 全体として回文である
- i番目と(i-P)番目の文字が等しい
前提知識
- UnionFind
解法
UnionFindで同じ文字でなければいけない部分をまとめていく。
回文である必要があるので、i番目と(N-1-i)番目をまとめる。
i番目と(i-P)番目の文字が等しいので、ここもまとめる。
もし、全体が1つの成分となれば2文字使えないので、"impossible"
そうでないならば、成分毎に文字を決定していく。
2文字使う必要があるので、適当に分けてやればいい。
#define wrong "impossible" int N, P; //--------------------------------------------------------------------------------------------------- string solve() { cin >> N >> P; UnionFind uf(N); rep(i, 0, N / 2) uf(i, N - 1 - i); rep(i, 0, N) if (0 <= i - P) uf(i, i - P); map<int,char> v; rep(i, 0, N) if (uf[i] == i) v[i] = '?'; if (v.size() == 1) return wrong; string ans = ""; int c = 0; fore(p, v) p.second = char('a' + c), c = 1 - c; rep(i, 0, N) ans += v[uf[i]]; return ans; } //--------------------------------------------------------------------------------------------------- void _main() { int T; cin >> T; rep(t, 0, T) cout << solve() << endl; }