はまやんはまやんはまやん

hamayanhamayan's blog

Periodic Palindrome Construction [CodeChef November Challenge 2017 C]

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