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;
	}

};