概要
ヒャッハー！ゴルフだ－！
効率とかどうだっていい、とにかく最短を目指すんだ！
Rubyだと発表とかされるらしいけどそんなのどうだっていい、C++でゴルフしようぜ！
※テストケースの詳細が某スレに流れてきたので投稿しました。一応言っておきますが、下記の内容はこのレスの前から分かってました
※2015/09/28追記：イベントも終わったので復活。
そもそもテストケースがガバガバな件について
既にご存知かと思いますが、POHのテストケースは常に一定です。
つまり、テストケースについての情報を得られれば、相当適当なコードでもOKになります。
さる方の記事にあるように、コードにusleep()を挟めば実行時間から情報が得られますので……。
で、調査した結果、次のような感じになりました。
- ケース1( 6個,「中央」1種1個,「左側」 2種 2個,単語長 3)
- ケース2( 1個,「中央」1種1個,「左側」 0種 0個,単語長10)
- ケース3( 7個,「中央」1種7個,「左側」 0種 0個,単語長 5)
- ケース4( 969個,「中央」0種0個,「左側」390種390個,単語長 8)
- ケース5(1000個,「中央」0種0個,「左側」350種350個,単語長10)
……おいてめぇふざけんなよ、書かれた問題文より相当条件厳しいじゃねえか！！！
(ポイント編での講釈がほとんど無意味になるレベルの酷さと言えば分かるだろうか？)
まず「中央」ですが、なんと2種類以上は出ません。つまり、「中央」と判定できればその単語1つと出てきた回数だけ記録すればいいことになります。
また「左側」についても、別に重複しないことから、std::mapとかを使う意味がないことになります。要するに、改良編での記述もほとんど不要になります。
まあ、極限まで手抜きすれば最初に単語リストを入力するところもタダの配列で済みます。とはいえ、std::vectorだとstd::findで検索するために「#include <algorithm>」という記述が必要なので打鍵数的に不利です。
ということで、重複OKで検索が.count()とかで何とかなるデータ構造であるstd::multisetを使いましょう。
……正直ソートされてる必要性は皆無ですが他に都合がいいコンテナを思いつかなかったから仕方がない。
限界まで縮めた結果がこれだよ！
#include <iostream>
#include <set>
#include <string>
#define R(S) reverse(S.begin(), S.end())
using namespace std;
int main(void){
int N;
string temp_word, center_word = "", all_word = "";
multiset<string> word;
cin >> N;
while(cin >> temp_word){
word.insert(temp_word);
}
for(auto it : word){
temp_word = it;
R(temp_word);
if(it == temp_word)
center_word += temp_word;
else
if(word.count(temp_word) && it < temp_word)
all_word += it;
}
cout << all_word << center_word;
R(all_word);
cout << all_word << endl;
}
信じられるか？ これ、まだ圧縮する前なんだぜ？ ということで圧縮ポン。
#include<iostream>
#include<set>
#include<string>
#define R(S) reverse(S.begin(),S.end())
using namespace std;int main(){int N;string T,C="",A="";multiset<string>W;cin>>N;while(cin>>T)W.insert(T);for(auto I:W){T=I;R(T);if(I==T)C+=T;else if(W.count(T)&&I<T)A+=I;}cout<<A<<C;R(A);cout<<A<<endl;}
これで僅か297バイト。やったぜ。
https://paiza.jp/poh/joshibato/matsue-ruby/result/719154be
Rubyでの圧縮の手引き
これをRubyに応用する場合、そのまま移植したくなることでしょう。実際移植してみましたが、それだと177バイトぐらいまでしか削れませんでした。
ただ、Rubyの場合は.selectや.sortなどの性能が高く、上手く使えば大幅に打鍵量を減らせます。私のような不束者ですら116バイトまで削れました。
n=gets;w=ARGF.read.split.sort;c="";w.select!{|x|c+=x if(y=x.reverse)==x;x<y&&w.index(y)};s=w.join;puts s+c+s.reverse