POH6+『「え、妻が松江？」松江Ruby会議07協賛 回文作成プログラミングコンテスト』 改良編 ref: http://qiita.com/YSRKEN/items/20aea3c3d40e901e79db

code5.cpp

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <unordered_map>
using namespace std;
int main(void){
    // 単語リストに単語を代入する
    int N;
    cin >> N;
    unordered_map<string, int> word;    //単語リスト(単語->回数)
    for(int i = 0; i < N; ++i){
        string temp;
        cin >> temp;
        // 単語リスト
        if (word.find(temp) != word.end()){
            ++word.at(temp);
        }else{
            word[temp] = 1;
        }
    }
    // 単語リストから「左側」一覧と「中央」を取得する
    map<string, int> left;  //「左側」のリスト
    string center_word; int center_count = 0;   //「中央」
    for(auto it : word){
        // 単語を反転したものを用意する
        string reverse_word = it.first;
        reverse(reverse_word.begin(), reverse_word.end());
        // 「中央」ならば、「より数が多い」か「数は同じでより若い」もののみ受け入れる
        if(it.first == reverse_word){
            if(center_count < it.second){
                center_word = reverse_word;
                center_count = it.second;
            }else if(center_count == it.second){
                if(center_word > reverse_word){
                    center_word = reverse_word;
                }
            }
        }else{
            // 「左側」ならば、「より若い」もののみ受け入れ、値は「より数が少ない」方にする
            if(word.find(reverse_word) != word.end()){
                left[min(it.first, reverse_word)] = min(it.second, word.at(reverse_word));
            }
        }
    }
    // 解を出力する
    // (左側→中央→右側。右側は左側の反転、中央は当該文字列をただ吐くだけ)
    string all_left_word = "";
    for(auto it : left){
        for(int i = 0; i < it.second; ++i){
            all_left_word += it.first;
        }
    }
    cout << all_left_word;
    for(int i = 0; i < center_count; ++i){
        cout << center_word;
    }
    reverse(all_left_word.begin(), all_left_word.end());
    cout << all_left_word << endl;
}

code5_2.cpp

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <unordered_map>
using namespace std;
int main(void){
    // 単語リストに単語を代入する
    int N;
    cin >> N;
    unordered_map<string, int> word;    //単語リスト(単語->回数)
    for(int i = 0; i < N; ++i){
        string temp;
        cin >> temp;
        // 単語リスト
        if (word.find(temp) != word.end()){
            ++word.at(temp);
        }else{
            word[temp] = 1;
        }
    }
    // 単語リストから「左側」一覧と「中央」一覧を取得する
    map<string, int> left;  //「左側」のリスト
    map<string, int> center;    //「中央」のリスト
    for(auto it : word){
        // 単語を反転したものを用意する
        string reverse_word = it.first;
        reverse(reverse_word.begin(), reverse_word.end());
        // 「中央」ならば、とりあえず全て取得する
        if(it.first == reverse_word){
            center[reverse_word] = it.second;
        }else{
            // 「左側」ならば、「より若い」もののみ受け入れ、値は「より数が少ない」方にする
            if(word.find(reverse_word) != word.end()){
                left[min(it.first, reverse_word)] = min(it.second, word.at(reverse_word));
            }
        }
    }
    // 「中央」のうち、2個以上ある単語はそのうちの半分を左側、もう半分を右側に振り分けておく
    // 例えば7個あった場合は3個を左側に入れて残り1個、8個なら4個入れて残り0個
    for(auto &it : center){
        if(it.second >= 2){
            left[it.first] = it.second / 2;
            it.second = it.second % 2;
        }
    }
    // 解を出力する
    // (左側→中央→右側。右側は左側の反転、中央は左右に過剰分を振り分けた後最若を出力)
    string all_left_word = "";
    for(auto &it : left){
        for(int i = 0; i < it.second; ++i){
            all_left_word += it.first;
        }
    }
    cout << all_left_word;
    for(auto &it : center){
        if(it.second == 1){
            cout << it.first;
            break;
        }
    }
    reverse(all_left_word.begin(), all_left_word.end());
    cout << all_left_word << endl;
}