Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-06-27TCO2010 Round2

凡ミスで500を落とし敗退しました・・・

TCO2010 Round2 250 SnowPlow

| 20:26 | TCO2010 Round2 250 SnowPlow - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2010 Round2 250 SnowPlow - SRM diary(Sigmar) TCO2010 Round2 250 SnowPlow - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→状態を更新しながらBFS?にしては計算量が多すぎるし、随分難しいな・・・うーん・・・

→他の人の状況を確認

→240点台で出してる人がいる。実は簡単なのかな。

→1分で1レーンしか掃除できないので、最低でも全てのエッジをレーン数分往復しないといけない

→逆に、単純にツリーと考えてツリーを辿るだけで、どんな順番でも最小時間で掃除できそうだ

→ということは、ノード0から到達できないノードがある場合に-1、そうでない場合レーン数の和*2が解か

→書く→サンプル合わない

→到達できないノードがエッジを持っていなければ到達する必要がない。親切なサンプルだ。

→書き直す→サンプル通る

→これで大丈夫か・・・例外は・・・ない!提出

→500へ


チャレンジフェーズ

→特に撃墜ポイント思いつかず


システムテスト

→問題なくPassed


以下、ソースです。

BFSで連結性の判定をしたけど、Union-Findのほうが簡単だったかな。


(6.27 21:50追記)

Union-Findで書いてみました。

Union-Findのライブラリはコピーするだけなので、手で書く量が少ないUnion-Findのほうが安全な気がします。



BFS版

class SnowPlow {
public:
	int solve(vector <string> roads) {
		int res=0;
		queue <int> q;
		int qe, qt;
		int val[52];

		memset(val, -1, sizeof(val));
		qe=0;
		q.push(qe);
		val[0]=0;
		while(!q.empty()) {//BFSで連結性の判定
			qt=q.front(); q.pop();
			for(int i=0; i<(int)roads.size(); i++) {
				if(roads[qt][i]>'0' && val[i]<0) {
					qe=i;
					q.push(qe);
					val[qe]=val[qt]+1;
				}
			}
		}

		for(int i=0; i<(int)roads.size(); i++) {//到達不可能ノードにエッジがあれば-1を返す
			if(val[i]==-1) {
				for(int j=0; j<(int)roads.size(); j++) {
					if(roads[i][j]>'0') return -1;
				}
			}
		}

		for(int i=0; i<(int)roads.size(); i++) {//すべてのレーン数の和(*2)が解
			for(int j=0; j<(int)roads[0].size(); j++) {
				res+=roads[i][j]-'0';
			}
		}
		return res;
	}
};

Union-Find版

//Union-Find Treeクラス
//Union: ufind(x,y,true)
//Find:  ufind(x,y,false)(x,y間にパスがなければtrueを返す)
class UFT {
public:
	vector <int> dad;
	UFT(int size) {
		this->dad.assign(size, -1);
	}
	int ufind(int x, int y, bool dounion) {
		int t, s, i=x, j=y;
		while(this->dad[i]>=0) i=this->dad[i];
		while(this->dad[j]>=0) j=this->dad[j];
		t=x;
		while(this->dad[t]>=0) {s=t; t=this->dad[t]; this->dad[s]=i;}
		t=y;
		while(this->dad[t]>=0) {s=t; t=this->dad[t]; this->dad[s]=j;}
		if(dounion && (i!=j)) {
			if(this->dad[j]<this->dad[i]) {
				this->dad[j]+=this->dad[i]; this->dad[i]=j;
			} else {
				this->dad[i]+=this->dad[j]; this->dad[j]=i;
			}
		}
		return (i!=j);
	}
};

class SnowPlow {
public:
	int solve(vector <string> roads) {
		int res=0;
		UFT eq(roads.size());

		//Union-Find Treeの作成
		for(int i=0; i<(int)roads.size(); i++) {
			for(int j=0; j<(int)roads.size(); j++) {
				if(roads[i][j]>'0') eq.ufind(i, j, true);
			}
		}

		//連結性の判定
		for(int i=0; i<(int)roads.size(); i++) {
			if(!eq.ufind(0, i, false)) continue;
			for(int j=0; j<(int)roads.size(); j++) {
				if(roads[i][j]>'0') return -1;
			}
		}

		for(int i=0; i<(int)roads.size(); i++) {
			for(int j=0; j<(int)roads[0].size(); j++) {
				res+=roads[i][j]-'0';
			}
		}
		return res;
	}
};

TCO2010 Round2 500 RepresentableNumbers

| 20:26 | TCO2010 Round2 500 RepresentableNumbers - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2010 Round2 500 RepresentableNumbers - SRM diary(Sigmar) TCO2010 Round2 500 RepresentableNumbers - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→少なくとも100000000は解の条件を満たす(representable numberとなる)ので、最大100000000までXから順番に解となるか判定して、解でなければXを1増やす。解の条件を満たす数字はかなり多そうなので、多分計算量は問題ないだろう。これで、あるXが解の条件を満たすかを判定する問題になる。

→判定は1桁ずつGreedyっぽくできそうではあるが・・・例外が多そう。。やりたくないですね。。

→うーん・・・とはいえ、他の方法も思いつかない・・十分に気をつけながら実装するしかないかな。

→まず、奇数同士の和は偶数になるので、最下位が奇数だとNG

→最下位以外は・・前の桁からの桁上がり(キャリー)があれば奇数、なければ偶数となる

→キャリーが発生する条件は・・・前の桁が2以上ならキャリーを発生させるもさせないも可能、0か1だとキャリーが必ず発生する。

→では、ある桁が0か1のときに、次の桁が偶数ならNG、それ以外のパターンはOKかな

→書く→サンプル合わない

→1000の場合、実際はOKだが今の判定方法だとNGですな・・これはリーディングゼロが含まれていてもtotally oddとなることを考慮しなかったのが原因みたい

→では、上記判定方法でNGとなったとき、残った数字がtotally oddとなる場合はOKとする。

→書き直す→サンプル通る

→こういう例外処理が多い問題は非常に不安だ・・・他の例外は・・うーん・・どう考えてもこれで全部だな

→提出

→1000はどうせ解けないだろうからもう一度500を確認しておこう

→・・・やっぱりどの場合でも問題ない。大丈夫だ。


チャレンジフェーズ

→お、これ間違ってる気がする。突撃!

→失敗。。なぜだ・・・。あ、、ちゃんと例外処理してる。。見落としてた・・・

→あ、この人間違ってそう・・・

→確認してる間に撃墜される

→1失敗で-25ポイント。結構みんな落ちてたなあ。。


システムテスト

→Failed

→ええーーなんで・・・

→あ・・・キャリー発生フラグを0,1以外のときOFFに戻す文が抜けてる

→酷い・・・アルゴリズムの検証にのみ注力して、プログラムの検証が疎かになっていた・・

→今度から、しっかり見直さないと・・それにしても、1文抜けるだけで天と地の差ですね。


以下、修正したソースです。

class RepresentableNumbers {
public:
	bool isto(int X) {//totally odd判定関数
		while(X) {
			if(!(X&1)) return false;
			X/=10;
		}
		return true;
	}

	int getNext(int X) {
		while(1) {
			int x=X;
			if(x&1) {//最下位桁が奇数ならNG
				X++;
				continue;
			}
			bool c=false, ok=true;
			while(x) {
				if(c && !(x&1)) {//キャリーが発生しており、かつ、偶数の場合
					x--;
					if(isto(x)) return X;
					ok=false;
					break;
				}
				if(x&1) x--;
				if(x%10==0) c=true;
				else c=false;//このelse文が抜けていた
				x/=10;
			}
			if(ok) return X;
			X++;
		}
		return 0;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100627