Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-02-02SRM496 Div1

SRM496 Div1 500 OneDimensionalBalls

| 23:53 | SRM496 Div1 500 OneDimensionalBalls - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM496 Div1 500 OneDimensionalBalls - SRM diary(Sigmar) SRM496 Div1 500 OneDimensionalBalls - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

うーん・・・

距離をイテレートするのはすぐ分かるが

その後が簡単そうでいて意外と分からない・・・

DPか?

いや、2^50とかになるし。。

色々考える

DPでは無理な気がする

何か数え上げ系じゃないのか

うーん・・/\/\/\/\こんなふうになる場合の数え方が分からない

(何となくたくさんあるように勘違いしていた)

なんか上側と下側のノードをビット化してビット演算で色々こねくり回すとか・・

だめぽい

やはりDPか?実は状態数すごく少ないとかじゃないのか

実際/\/\/\/\これの場合何通りくらいになるのか考えてみるか

あれ・・実は下側のノードの数しか組み合わせがない???

やっぱそうか。しまった。なんで気付かなかったんだ。

あとはじゃあ独立なものをかけ合わせるだけか

書く

合わない

色々書き間違えてる

10分くらいデバッグ

やっと直った・・・

提出

コード汚すぎてちょっと怖い・・・


チャレンジフェーズ

あれ

これ、2^50のDPしてる。絶対無理だろう

適当にランダムケース作って・・・

ってランダムじゃだめか。あれ、、しまった、意外とどういうのがTLEするのか考えてなかった

/\ /\ /\ こんなやつを25個で2^25=3000万くらいか・・

更新のコストもあるから落ちるかなぁ・・うーん・・

(しばし悩んで)よし、投げよう

あれ、誰かに先越された。。。うう・・・

今度からしっかりチャレンジを考えるようにしておかないと・・・


システムテスト

Passed


ソースコード

汚すぎる・・・

class OneDimensionalBalls {
public:
	long long countValidGuesses(vector <int> firstp, vector <int> secondp) {
		long long res=0;
		int n=firstp.size(), m=secondp.size();

		sort(firstp.begin(), firstp.end());
		set <int> diff;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				diff.insert(abs(firstp[i]-secondp[j]));
			}
		}
		diff.erase(0);
		vector <int> diffv(diff.begin(), diff.end());

		map <int, int> revf, revs;
		for(int i=0; i<n; i++) {
			revf[firstp[i]]=i;
		}
		for(int i=0; i<m; i++) {
			revs[secondp[i]]=i;
		}

		for(int i=0; i<(int)diffv.size(); i++) {
			int usedf[50], useds[50];
			memset(usedf, 0, sizeof(usedf));
			memset(useds, 0, sizeof(useds));
			int tdiff=diffv[i];
			ll tres=1;
			for(int j=0; j<n; j++) {
				int mulf=0;
				if(usedf[j]) continue;
				if(revs.count(firstp[j]-tdiff)) {
					mulf=1;
					useds[revs[firstp[j]-tdiff]]=1;
				}
				int nj=j;
				bool ok=true;
				int cnt=2;
				while(1) {
					usedf[nj]=1;
					if(!revs.count(firstp[nj]+tdiff)) {
						if(mulf==0) {
							ok=false;
							break;
						} else {
							mulf=0;
							break;
						}
					}
					nj=revs[firstp[nj]+tdiff];
					useds[nj]=1;
					if(!revf.count(secondp[nj]+tdiff)) {
						if(mulf==0) {
							break;
						} else {
							tres*=cnt;
							break;
						}
					}
					nj=revf[secondp[nj]+tdiff];
					cnt++;
				}
				if(!ok) {
					tres=0;
					break;
				}
			}
			res+=tres;
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110202