Palindrome [ACPC2017 Day2 C]

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day2&pid=C

解説

http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2538219&cid=ACPC2017Day2

文字列をカウントしておく(cnt配列)。
ペアを見つけるように文字列を辞書順で小さい方から考えていく。
辞書順で考えていき、相手がいるなら答えに追加していく。
貪欲にペアを見つけていき、もし自分自身が回文のやつが1つ残ったら、そのうち辞書順最小のものを中心に置いて答え。

int N, L; string S[1010];
//--------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> L;
    rep(i, 0, N) cin >> S[i];
 
    map<string, int> cnt;
    rep(i, 0, N) cnt[S[i]]++;
 
    vector<pair<string, string>> v;
    vector<string> pan;
    fore(p, cnt) {
        // 回文判定
        int ispand = 1;
        rep(i, 0, L / 2 + 1) if (p.first[i] != p.first[L - 1 - i]) ispand = 0;
 
        if (ispand) { // それ自身が回文
            while (2 <= p.second) {
                v.push_back({ p.first, p.first });
                p.second -= 2;
            }
            if (p.second) pan.push_back(p.first);
        } else { // 相手の回文を探す
            string rev = p.first;
            reverse(rev.begin(), rev.end());
 
            if (p.first > rev) continue; // 相手が辞書順で小さいならスキップ
            int n = min(p.second, cnt[rev]);
            rep(i, 0, n) v.push_back({ p.first, rev });
        }
    }
 
    string ans = "";
    int n = v.size();
    rep(i, 0, n) ans += v[i].first;
    if (0 < pan.size()) ans += pan.front();
    rrep(i, n - 1, 0) ans += v[i].second;
    cout << ans << endl;
}