Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-12-31SRM528 Div1(Practice)

SRM528 Div1 250 Cut

| 21:33 | SRM528 Div1 250 Cut - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM528 Div1 250 Cut - SRM diary(Sigmar) SRM528 Div1 250 Cut - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

eelって何だと思ったらウナギらしい。最初文意からしてソバかと思った。

しかしウナギってanguilla(アンギラ)じゃなかったっけ、、と思ったらアンギラは学名だそうだ。ふーん・・


解法は単に10で割れるものから優先的に切るだけ。

10で割れるものの中でも短いものを優先的に切る。

なぜならピッタリ切れると得するのが10で割れるものだけで、なるべくピッタリを増やすほうが得だから。


あんまり難しくはないと思ったけど随分pass率が低かったみたい。なぜだろう。


class Cut {
public:
	int getMaximum(vector <int> eellen, int maxc) {
		int res=0;
		int n=eellen.size();

		vector <int> e10, eelse;
		for(int i=0; i<n; i++) {
			if(eellen[i]%10==0) e10.push_back(eellen[i]);
			else eelse.push_back(eellen[i]);
		}
		sort(e10.begin(), e10.end());
		sort(eelse.begin(), eelse.end());//10で割れないものはたぶんソートしなくていい

		for(int i=0; i<(int)e10.size(); i++) {
			if(e10[i]==10) res++;//たぶん長さ10を特別扱いしなくていい
			else {
				if(e10[i]/10-1<=maxc) {
					res+=e10[i]/10;
					maxc-=e10[i]/10-1;
				} else {
					res+=maxc;
					maxc=0;
				}
			}
		}

		for(int i=0; i<(int)eelse.size(); i++) {
			if(eelse[i]/10<=maxc) {
				res+=eelse[i]/10;
				maxc-=eelse[i]/10;
			} else {
				res+=maxc;
				maxc=0;
			}
		}
		return res;
	}
};

SRM528 Div1 500 SPartition

| 21:33 | SRM528 Div1 500 SPartition - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM528 Div1 500 SPartition - SRM diary(Sigmar) SRM528 Div1 500 SPartition - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

ナイーブにやれば、使った文字数 * Xに使った文字数 * 現在の文字パターン で40*20*2^20くらいのDPか?

更新コストが2で計算量16億と無理っぽい

実は文字パターンって入力文字列から一意に定まったりしないのかな?

・・・

無理。反例がある。

xxooxxoo で、xxoo と xoxo の2パターン取れる。

うーん

・・・

・・・

2^20っていうのがちょっと無駄な気がする。

oとxの数は決まっているのだから、入力文字列の長さをn、oの数をocntとすると、n C ocntでいいはずだ

最大20C10で、20万程度。計算量は、、3億くらい。。これでもちとオーバー気味。。

最初の文字と最後の文字は、入力の最初と最後から確定する。最初の文字だけ確定させるだけでも計算量は間に合うレベルになるはず。

19C10=10万くらいなので、総計算量1億5千万程度。ループ内部はシンプルなので大丈夫だろう。

文字パターンのループを一番外側のループにするとメモリは40*20くらいでいいので、メモリ的にも問題ない。


ところでxとoの並び替えをするのに、外側のループだからnext_permutationを使っても多分問題ないのだが、何となくnext_cmbという自前ライブラリを使ってみた。

コンビネーションの列挙で計算がシビアなときはこの関数が役に立つと思う。

でも使い方が微妙に癖があって、値が0のときを特別扱いする必要があるのでバグを生みやすい。実際にバグっていたのだがテストするまで見つけられなかったので、危険ではある。。


まあ最初の文字だけ確定とか、こんな微妙な調整をするのも綺麗じゃなくて何だなと思う。

結構スカスカなDPなので、メモ化再帰にするのが良かったかも。


このくらいの正答率(25%くらい)の問題が僕にはすぐには解けなくて練習にちょうどいいみたい。


ソースコード

unsigned long long next_cmb(unsigned long long x) {
	if(x==0) return 0;
	unsigned long long ls1b=x&~(x-1);
	unsigned long long nupper=x+ls1b;
	unsigned long long nupper_ls1b=nupper&~(nupper-1);
	unsigned long long nlower=((nupper_ls1b/ls1b)>>1)-1;
	return nupper|nlower;
}

class SPartition {
public:
	long long getCount(string s) {
		long long res=0;
		int n=s.size();
		int ocnt=0;
		for(int i=0; i<n; i++) {
			if(s[i]=='o') ocnt++;
		}

		if(ocnt%2==1) return 0;
		if(s[0]=='o') ocnt-=2;

		for(int permt=(1<<(ocnt/2))-1; permt<(1<<(n/2-1)); permt=next_cmb(permt)) {
			int perm=(permt<<1);
			if(s[0]=='o') perm++;
			ll dp[42][42];
			memset(dp, 0, sizeof(dp));
			dp[0][0]=1;
			for(int d=0; d<n; d++) {
				for(int xlen=0; xlen<=d; xlen++) {
					int ylen=d-xlen;
					if(xlen<n/2 && (((perm&(1<<xlen))>0) ^ (s[d]=='x'))) dp[d+1][xlen+1]+=dp[d][xlen];
					if(ylen<n/2 && (((perm&(1<<ylen))>0) ^ (s[d]=='x'))) dp[d+1][xlen]+=dp[d][xlen];
				}
				res+=dp[n][n/2];
			}
			if(permt==0) break;
		}
		
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111231