SRM 528 500pt : SPartition
問題概要
長さL(<40, even)のビット列がある。長さL/2の互いに交わらない順序を保った部分列をとってきて、部分列が等しくなるような分割の仕方は何通りあるか求める問題。
解法
いろいろ解き方があるらしいけど、長さ40を見ると半分全列挙が思い浮かぶ。TLEが結構厳しいので、文字列のまま扱うのではなく整数にエンコードするなどしたら間に合うようになる。
acceptされたコード
#include <string> #include <vector> #include <algorithm> using namespace std; typedef long long int64; struct SPartition { int64 getCount(string s) { const int N = s.length(); const int HALF = N / 2; vector< vector<int64> > prevs(HALF+1), posts(HALF+1); //前半を集める { for(int bit=0; bit<(1<<HALF); bit++){ const int X = __builtin_popcount(bit), Y = HALF - X; int64 xx = 0, yy = 0; for(int i=0; i<HALF; i++){ if((bit>>i)&1){ xx = xx*2 + (s[i] == 'o' ? 1 : 0); } else{ yy = yy*2 + (s[i] == 'o' ? 1 : 0); } } if(same_prefix(xx, yy, X, Y)){ prevs[X].push_back(cut_prefix(xx, yy, X, Y)); } } for(int i=0; i<(int)prevs.size(); i++){ sort(prevs[i].begin(), prevs[i].end()); } } //後半を集める { for(int bit=0; bit<(1<<HALF); bit++){ const int X = __builtin_popcount(bit), Y = HALF - X; int64 xx = 0, yy = 0; for(int i=0; i<HALF; i++){ if((bit>>i)&1){ xx = xx*2 + (s[i+HALF] == 'o' ? 1 : 0); } else{ yy = yy*2 + (s[i+HALF] == 'o' ? 1 : 0); } } if(same_suffix(xx, yy, X, Y)){ posts[X].push_back(cut_suffix(xx, yy, X, Y)); } } for(int i=0; i<(int)posts.size(); i++){ sort(posts[i].begin(), posts[i].end()); } } //数える int64 ans = 0; { for(int i=0; i<(int)prevs.size(); i++){ const int X = i, Y = HALF - X; for(int j=0; j<(int)prevs[i].size(); j++){ const int64 diff = prevs[i][j]; pair<vector<int64>::iterator, vector<int64>::iterator > p = equal_range(posts[Y].begin(), posts[Y].end(), diff); ans += distance(p.first, p.second); } } } return ans; } bool same_prefix(int64 x, int64 y, int xl, int yl){ const int mini = min(xl, yl); for(int i=0; i<mini; i++){ if( ((x>>(xl-1-i))&1) != ((y>>(yl-1-i))&1) ){ return false; } } return true; } int64 cut_prefix(int64 x, int64 y, int xl, int yl){ const int diff = abs(yl - xl); if(xl < yl){ return y&((1LL<<diff)-1); } else if(yl < xl){ return x&((1LL<<diff)-1); } return 0; } bool same_suffix(int64 x, int64 y, int xl, int yl){ const int mini = min(xl, yl); for(int i=0; i<mini; i++){ if( ((x>>i)&1) != ((y>>i)&1) ){ return false; } } return true; } int64 cut_suffix(int64 x, int64 y, int xl, int yl){ if(xl < yl){ return y>>xl; } else if(xl > yl){ return x>>yl; } return 0; } };