POH6+『「え、妻が松江？」松江Ruby会議07協賛 回文作成プログラミングコンテスト』 改良編

#概要
この記事には、[POH6+](https://paiza.jp/poh/joshibato/matsue-ruby)に関するネタバレが含まれます。カンニングしたくない場合は、[前々回の記事](http://qiita.com/YSRKEN/items/11f5e1517f3bef666c29)を読んで勉強するんだ！

……今回はコードを改良する話。
**2015/09/04：重大なミスが見つかりましたので修正しました。**

#STLが足りてない！
実は[前回](http://qiita.com/YSRKEN/items/daa4ea4a814513f6f0b1)挙げたコードには問題がある。100点満点ではあるのだが、美しくない。**つまり、STLの力を生かしきれてないということ**。

手順としては、いかに「左側」一覧と「中央」を抽出するかなのだが、前回でも述べたように文字列は別に重複して構わない。その一方で、前回はゴリゴリと線形検索して、その後にソートを掛けていた。

つまりこれは、**std:map**を使うべきところなのではないか？

std::mapなら**突っ込んだデータが確実にソートされている**ので後からソートする必要はないし、同じ単語が複数あれば**findで判別してインクリメント**すればいい。検索も**二分検索**(std::unordered_mapならハッシュ法)**を使うから超速い**し、なにより(std::vectorと同じく)**メモリ解放する手間が掛からない**。

と言うことで、単語リスト読み込みにはstd::unordered_map、『leftの集合』を入れるのにはstd::mapを使用した。以下ソース。

#投稿しなおしたコード(修正前)
```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;
}
```

ちなみにコイツを魔圧縮したら**635バイト**になった。まあまあ縮んだんじゃないかな？

#投稿しなおしたコード(修正後)
```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;
}
```