Close Menu Navigation
Open Categories Menu ソニーのソフトウェアスペシャリスト認定コンテスト『暗号検索の高速化』(2)
- 8 2月, 2012 -
- プログラミング, 就職活動 -
- Tags :
- 0 Comments
2/8追記：ライセンスについて
※回答はオープンソースソフトウェアとして公開してください。
その際、そのソフトウェアをOSDに準拠したライセンス(GPLライセンスやBSDライセンスなど)であることを明示して公開してください。
とあるので、ここのコードは修正BSDライセンスとして扱って下さい。普段は常識的な範囲でご自由にライセンスにしておくのだけど、OSSの世界ではそれは困るらしい。
ソニーのソフトウェアスペシャリスト認定コンテスト『暗号検索の高速化』(2)
前回のエントリで勘違いした実装をしてやり直し。一部分だけ直したけど、これは方針が悪いのでとても遅い。
前回のDFSを使い回しているのだけど、30万文字あって等確率に出るとすると1文字あたり1万回以上は出てくる。その全ての文字に対して2文字目は総当たりで探索しているので、10000 x 10000 = 1億くらいの初期ノードでやっていて正気の沙汰とは言えない。小さいのを求めるのが目標だからこれ以上いいスコアが出る見込みがない場合には探索を打ち切ることにしているけど、それでも手元のPCで20秒くらいかかるため、要改善。
#include < stdio.h>
#include < iostream>
#include < string>
#include < set>
#include < map>
#include < algorithm>
#include < stack>
#include < vector>
using namespace std;
struct node
{
int address;
int depth;
int skip;
};
int main( int c, char *v[] )
{
if( c != 2 )
{
fprintf( stderr, "%s keywordn",v[0] );
return EXIT_FAILURE;
}
string keyword = v[1];
string reverse = keyword;
std::reverse( reverse.begin(), reverse.end() );
set<char> k;
for( int i = 0; i < keyword.length(); i++ )
k.insert(keyword[i]);
// アドレス、文字
map<int, char> m;
int loc = 0;
while(!feof(stdin))
{
char ch = fgetc(stdin);
if( k.count(ch) != 0 )
m.insert(make_pair<int, char>( loc, ch ));
loc++;
}
stack<node> s;
for( map<int, char>::iterator it = m.begin(); it != m.end(); it++ )
{
node n;
if( it->second == reverse[0] )
{
n.address = it->first;
n.depth = 1;
n.skip = 0;
s.push(n);
}
}
int min = loc;
vector< pair<int, int> > result;
while( !s.empty() )
{
node n;
n = s.top();
s.pop();
// 脱出条件をここに書く
if( reverse.length() == n.depth )
{
map<int, char>::iterator it = m.find( n.address );
if( m.end() != it )
{
min = std::min( min, abs(n.skip) );
result.push_back(make_pair<int, int>(abs(n.skip), n.address));
}
continue;
}
// ここでノードの枝を全部辿るループを書く
if( n.depth == 1 || n.skip == 0 )
{
// 初回は全部見ておく
for( map<int, char>::iterator it = m.begin(); it != m.end(); it++ )
{
if( it->second == reverse[n.depth] )
{
node next;
next.address = it->first;
next.depth = n.depth + 1;
next.skip = next.address - n.address;
s.push(next);
}
}
}
else
{
// 枝狩り、最良になる見込みのないのは要らない
if( abs(n.skip) > min )
continue;
// 二回目以降はskipだけ離れたところしか見ない
map<int, char>::iterator it = m.find( n.address + n.skip );
if( m.end() != it && it->second == reverse[n.depth] )
{
node next;
next.address = it->first;
next.depth = n.depth + 1;
next.skip = next.address - n.address;
s.push(next);
}
}
}
sort( result.begin(), result.end() );
for( int i = 0; i < result.size(); i++ )
fprintf( stdout, "%d, %dn", result[i].first, result[i].second );
return 0;
}
実行結果
こっちは枝狩りをしている方。
1, 118590 2, 149499 2, 234392 2, 286130 3, 289966 3, 298337 213, 298248 1928, 293465 4356, 286390 14960, 254591 27030, 218446
枝狩りをしないとなんと65,000行以上の出力になる。というか解がこんなに多いとは予想以上である。
恥さらしなコードを晒したので後で改善したいと思う。けど、2/10に帰国を控えて忙しいのでどうなるかわからない。
- 著者／訳者：ティモシー フェリス
- 出版社：青志社( 2007-09-21 )
- 単行本：255 ページ
- ISBN-10 : 490385311X
- ISBN-13 : 9784903853116
- 定価：￥ 1,470
- 著者／訳者：ティモシー・フェリス
- 出版社：青志社( 2011-02-03 )
- 単行本：640 ページ
- ISBN-10 : 4905042097
- ISBN-13 : 9784905042099
- 定価：￥ 1,995
- 著者／訳者：篠山 半太
- 出版社：PHP研究所( 2012-06-16 )
- 文庫：340 ページ
- ISBN-10 : 4569678467
- ISBN-13 : 9784569678467
- 定価：￥ 720
