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

code4.cpp

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(void){
// データを入力する
    int N;
    cin >> N;
    vector<string> word(N);
    for(int i = 0; i < N; ++i){
        cin >> word[i];
    }
// データの中で「左側」であるものと「中央」であるものを取り出す
    // 「中央」であるものの文字列と回数を動的配列で保存する
    vector<string> center_word;
    vector<int> center_count;
    int max_center_count = 1;
    // 「左側」であるものは動的配列で保存する
    vector<string> left_word;
    // ひと通り走査して調べる
    for(int i = 0; i < N; ++i){
        // 文字列長が0なら弾く(「左側」の処理のため)
        if(word[i] == "") continue;
        // 反転したものを用意する
        string reverse_word = word[i];
        reverse(reverse_word.begin(), reverse_word.end());
        // 反転したものと同じなら「中央」に数える
        if(reverse_word == word[i]){
            bool recent_flg = false;
            for(int j = 0; j < center_word.size(); ++j){
                if(reverse_word == center_word[j]){
                    ++center_count[j];
                    if(max_center_count < center_count[j]){
                        max_center_count = center_count[j];
                    }
                    recent_flg = true;
                    break;
                }
            }
            if(!recent_flg){
                center_word.push_back(reverse_word);
                center_count.push_back(1);
            }
            word[i] = "";
            continue;
        }
        // 反転したものが他に存在する場合は、「左側」のみ取り出す
        for(int j = i + 1; j < N; ++j){
            if(reverse_word == word[j]){
                if(word[i] < word[j]){
                    left_word.push_back(word[i]);
                }else{
                    left_word.push_back(word[j]);
                }
                word[j] = "";
                break;
            }
        }
    }
// 「左側」のデータをソートする
    sort(left_word.begin(), left_word.end());
// 最大数である「中央」のデータだけを抽出する
    vector<string> center_word2;
    for(int i = 0; i < center_word.size(); ++i){
        if(max_center_count == center_count[i]){
            center_word2.push_back(center_word[i]);
        }
    }
// 抽出した「中央」のデータのうち最上位をゲットする
    string min_center_word;
    if(center_word2.size() > 0){
        min_center_word = center_word2[0];
        for(int i = 1; i < center_word2.size(); ++i){
            if(min_center_word > center_word2[i]){
                min_center_word = center_word2[i];
            }
        }
    }
// データを出力する
    for(int i = 0; i < left_word.size(); ++i){
        cout << left_word[i];
    }
    if(center_word.size() > 0){
        for(int i = 0; i < max_center_count; ++i){
            cout << min_center_word;
        }
    }
    for(int i = left_word.size() - 1; i >= 0; --i){
        reverse(left_word[i].begin(), left_word[i].end());
        cout << left_word[i];
    }
}