POH6+『「え、妻が松江？」松江Ruby会議07協賛 回文作成プログラミングコンテスト』 解説編
概要
この記事には、POH6+に関するネタバレが含まれます。カンニングしたくない場合は、前回の記事を読んで勉強するんだ！
2015/09/04：重大なミスが見つかりましたので修正しました。
ここで問題文をおさらい(と言う名の行数稼ぎ)
問題
N個の単語のリストw_1～w_Nが与えられる。
単語は英小文字のみからなる文字列である。
この際、リストから作られる最長の回文で辞書順最小のものを一行に出力せよ。
最後は改行し、余計な文字、空行を含んではならない。
ただし、1 ≦ N ≦ 1000・1 ≦ |w_i| ≦ 10であり、すべての単語は同じ長さである。
結局どういったコードを書いたのか
問題
N個の単語のリストw_1～w_Nが与えられる。
単語は英小文字のみからなる文字列である。
この際、リストから作られる最長の回文で辞書順最小のものを一行に出力せよ。
最後は改行し、余計な文字、空行を含んではならない。
ただし、1 ≦ N ≦ 1000・1 ≦ |w_i| ≦ 10であり、すべての単語は同じ長さである。
要するに、「それ自身で対称な文字列」(以下「center」と呼称)と、「左右ペアになっている文字列」(以下「right」「left」と呼称)をリストから選り分けて、その後に『leftの集合』→『center』→『rightの集合』と出力すればいい。
その際、leftとrightは対になっている必要があるので、leftだけ記憶しておいてrightを後から生成してもいいだろう。
leftとrightのペアを探す方法や、centerであるかを判定する方法については省略する(考えれば分かることだし、言語のライブラリに必要な機能が付いている場合も多い)。
leftとrightについてどちらがleftでどちらがrightかなんてのは問題文を読めば自明であるが、centerの扱いはまたややこしい。なにせcenterな文字列は前述のように重複している可能性がある上、centerな文字列は複数個繋げてもまたcenterな文字列なのだ。
要するに、centerな文字列の中で一番数が多い種類を抜き出して並べるという作業が必要になる。前回のテストケースにもそういった問題は入れているので参考にしてほしい。
2015/09/04修正：
上記のような処理だと最長にならないので、「centerな文字列のうち半数(切り捨て)をleft、半数をrightに入れて、残りのうち最も昇順で上なもの1つを『center』とする」ようにしなければならない。『left』は昇順前提なので、centerの半数を入れた後にソートすることになる。
『leftの集合』について、leftな文字列同士でどう並べるかも自明だろう。leftの数は問題文から最大500個しかないことが分かるが、向こうが用意するテストケースでは$O(N^2)$程度のソートだと遅い、とだけ書いておく。
最終的に投稿したコード(当時。後述するようにバグあり)
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];
}
}
#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];
}
}
2015/09/04追記：このコードには実はバグがあるが、問題自体は100点満点で通過してしまう。これはテストケースに不備があるということなので、paizaさんにバグレポートを送っておく。
あとがき(当時)
今回は結構大変だったが面白かった。前回の記事のテストケースだが、実は試行錯誤で得られたものだったりする。それすら通らない段階で、paiza運営に対し「ランタイムエラーで途中で止まるんですが……」と陳情したのが恥ずかしく感じる(POHでテストケースがランタイムエラー＝ぬるぽなどの実行時エラーだと思いねぇ)。
ただ、工夫すれば自分が書いたコードよりずっと短くなるそうで、Rubyで227バイトとか、それ以下で書けるといった報告もあった。これは言語仕様というよりは書き方の問題らしいので、自分のC++コードも更に最適化できるということなのか？
Author And Source
この問題について(POH6+『「え、妻が松江？」松江Ruby会議07協賛 回文作成プログラミングコンテスト』 解説編), 我々は、より多くの情報をここで見つけました https://qiita.com/YSRKEN/items/daa4ea4a814513f6f0b1著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .