Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-02-02SRM496 Div1

SRM496 Div1 250 ColoredStrokes

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

Problem Statement

コーディングフェーズ

これは・・・縦と横でそれぞれ走査するだけなのでは・・・

簡単すぎないか?

でも合ってるようにしか思えないし、、書いてみよう

書けた

サンプル合った

提出

500を考える時間がたくさん取れて久々に嬉しい感じ


システムテスト

Passed


ソースコード

class ColoredStrokes {
public:
	int getLeast(vector <string> pict) {
		int res=0;
		int r=pict.size(), c=pict[0].size();

		for(int i=0; i<r; i++) pict[i].push_back('.');
		pict.push_back(string(c+1, '.'));

		for(int i=0; i<r; i++) {
			int p=0;
			for(int j=0; j<c+1; j++) {
				if(pict[i][j]=='R' || pict[i][j]=='G') p=1;
				if(pict[i][j]=='B' || pict[i][j]=='.') {
					if(p==1) res++;
					p=0;
				}
			}
		}
		for(int j=0; j<c; j++) {
			int p=0;
			for(int i=0; i<r+1; i++) {
				if(pict[i][j]=='B' || pict[i][j]=='G') p=1;
				if(pict[i][j]=='R' || pict[i][j]=='.') {
					if(p==1) res++;
					p=0;
				}
			}
		}
		return res;
	}
};

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

SRM496 Div1 950 YetAnotherHamiltonianPath

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

Problem Statement

後で

950だしちょっと読んでみた

意外とHardにしてはストレートフォワードな感じ

まず、コストはX^2+Y^2-LCP(X,Y)^2だが、どんな順番で訪問しても、ノードの入力時及び出力時にX^2のコストがかかるため、

LCP(X,Y)^2を最大化することだけを考えれば良い

少し制約を緩くして、始点と終点を自由に選べるとすると、再帰的にプレフィクスが一致するところをまとめればいい

例えば最初の文字がaのものをまとめ、更にその中で2文字目がbのものをまとめ・・といった感じ

これを実現するには実は単にソートして辞書順に訪れればOK

さて始点と終点が定められると、どうすれば良いのかというのが問題

色々試してみると比較的すぐに規則性が分かるが、始点と終点の共通プレフィクスをpref、全ノードの共通プレフィクスをprefallとすると、pref^2-prefall^2だけ全体のLCPが小さくなることが分かる

ということで後は計算するだけ

なんですが、プラクティスではpref^2-prefall^2の部分を勘違いして計算ミスで1WAしてしまった・・・


ソースコード

以下はプラクティスで通したコードです

class YetAnotherHamiltonianPath {
public:
	int leastCost(vector <string> label) {
		ll res=0;

		int n=label.size();

		res+=label[0].size()*label[0].size()+label[1].size()*label[1].size();
		for(int i=2; i<n; i++) {
			res+=label[i].size()*label[i].size()*2;
		}

		string pref01;
		for(int k=0; k<(int)min(label[0].size(), label[1].size()); k++) {
			if(label[0][k]==label[1][k]) pref01.push_back(label[0][k]);
			else break;
		}
		int prefall=pref01.size();
		for(int i=2; i<n; i++) {
			int tprefall=0;
			for(int k=0; k<(int)min(pref01.size(), label[i].size()); k++) {
				if(pref01[k]==label[i][k]) tprefall++;
				else break;
			}
			prefall=min(prefall, tprefall);
		}
		res+=pref01.size()*pref01.size()-prefall*prefall;

		sort(label.begin(), label.end());
		for(int i=1; i<n; i++) {
			int pref=0;
			for(int k=0; k<(int)min(label[i-1].size(), label[i].size()); k++) {
				if(label[i-1][k]==label[i][k]) pref++;
				else break;
			}
			res-=pref*pref;
		}

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