Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-09-16SRM482 Div1

SRM482 Div1 250 LockersDivOne

| 00:10 | SRM482 Div1 250 LockersDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM482 Div1 250 LockersDivOne - SRM diary(Sigmar) SRM482 Div1 250 LockersDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→最初に開いてないロッカーを見つけ、そこからn+1個ごとにロッカーを見ていって開いてないロッカーを開けていくと理解した

→良く分からんがロッカーの状態を配列で持てば良いんじゃ・・?これだとTLEする?

→とりあえず書く→サンプル合う

→200万(最大値)でもTLEしない。これでいいのか・・・

→念のため1と2の場合もチェック・・2が合わない・・ループ回数に少し余裕を持たないとだめなようだ

→直す→提出→500へ


チャレンジフェーズ

→他の人はリストとか使ってるみたい?

→コードが理解出来ない・・何やってるんだこの人たち・・

→あれ?落とされた?訳分からん(>_<)


終了後

→問題でも読み間違えたかなあ

→何度も読み直す・・だめだ・・・間違いが分からない・・・・・・・・

→・・・

→・・・

→もしかして"open every (n+1)th unopened locker"というのは、全ロッカーを(n+1)個おきに見ていって開いてるのを探すのではなくて、開いてないロッカーだけを(n+1)個おきに見ていくとか?

→あ・・そういう意味か・・

→"open every (n+1)th locker if it is unopened"みたいな雰囲気で解釈していた

→思い込みって怖いですね。。。

→でもこれを解釈間違えてもサンプル合うってどうなんだ。英語読み解きテストじゃなくてアルゴリズムとかコーディングで競争したいんですが・・・・


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

setを使おうかと思ったけど、setの挿入削除は対数時間、listは定数時間なのでlistを使うことにする

実はlistを使うのは初めてかもしれない・・

時間はこれで1.9sとぎりぎりみたい。

class LockersDivOne {
public:
	int lastOpened(int N) {
		int res=0;

		list <int> lc;
		for(int i=1; i<=N; i++) lc.insert(lc.end(), i);
		for(int i=2; lc.size()>0; i++) {
			for(list <int>::iterator li=lc.begin(); li!=lc.end();) {
				res=*li;
				list <int>::iterator li2=li;
				li++;
				lc.erase(li2);
				for(int j=0; j<i-1; j++) if(li!=lc.end()) li++;
			}
		}

		return res;
	}
};

SRM482 Div1 500 HanoiGoodAndBad

| 00:10 | SRM482 Div1 500 HanoiGoodAndBad - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM482 Div1 500 HanoiGoodAndBad - SRM diary(Sigmar) SRM482 Div1 500 HanoiGoodAndBad - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→ハノイですか

→Daveのほうはいいとして、Earlは何だこれ、何がしたいのか意味が分からない

→よく読むと、Earlのやり方で全部の置き方ができるということらしい。なるほど・・・

→Sampleの0を読んでみる

→なぜEarlがこういう動きになるのか全然分からない。何だこれは

→(15分後)→やっと分かった。1枚目からわざわざこんな無駄な動きをするようなやり方なのか。

→合理的に効率的な動かし方をしようとする人間の自然な考え方と反するやり方だから意味が飲み込めなかった・・ということにしておこう・・

→ともかく、Sample0は分かったが、全体的にどのような動きをするのか

→Daveのほうは2^Nなので簡単にシミュレーションできる。問題はEarlのほうかな。

→色々図を書いてみる→(10分後)→良く分からん・・図で描くシミュレーションは限界があるな

→よく考えると、Earl手法は全部のパターンを必ず1つずつ通ることができるわけだから・・

→一番大きいディスクから目的の位置に移動するまでシミュレーションし、さらに再帰的に次に大きいディスクの移動をシミュレーションし、とやれば良いのでは

→しかもN枚のディスクの移動は3^N-1回でできるとはっきり書いてあるから、実はやるだけの問題だな・・

→もう時間がない・・・早く書こう

→ハノイの状態の表し方に悩みつつ書く

→だめだ答えが合わない→デバッグ→合わない→時間切れ・・・


チャレンジフェーズ

→250が撃墜された時点で、1つ2つ程度落としてもほとんど順位が変わらないので諦め

→自分の間違ってたところでも探すか

→・・・

→上からn枚移動するのを下からn枚移動させてる・・またしょぼいミスしてた・・・


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

ハノイの状態をsetで表そうとしたんだけどeraseを含むイテレータの操作でかなり苦労してしまった・・勉強不足です。

それにしても、250は認識誤りから抜け出すきっかけすらなかったのである意味どうしようもないけど、500は反省すべき出来だった

問題を理解するのに時間がかかりすぎだ。集中ができていない・・・

ハノイの状態を表す手法についてはどんなのが良いのか、また勉強が必要かな・・・

set <int> st[3];//ハノイの状態
int pos[20];//Daveの最終状態
int cnt;
int res;

class HanoiGoodAndBad {
public:
	void rec1(int s, int t, int sp, int N) {//Daveのシミュレーション
		if(cnt==0) return;
		if(N<=0) return;

		rec1(s, sp, t, N-1);
		if(cnt==0) return;
		st[t].insert(*st[s].begin());
		st[s].erase(st[s].begin());
		cnt--;
		if(cnt==0) return;
		rec1(sp, t, s, N-1);
		return;
	}
	
	void rec2(int s, int t, int sp, int N) {//Earlのシミュレーション
		if(N<=0) return;

		if(st[pos[N]].count(N)) {
			rec2(s, t, sp, N-1);
			return;
		}
		res+=(int)pow(3., N-1.)-1;
		set <int>::iterator sti=st[s].begin();
		for(int i=1; i<N; i++) sti++;//これをsti=st[s].end(); for(略) sti--;にしてました
		st[t].insert(st[s].begin(), sti);//この辺を、insert(sti, st[s].end())とかにしてました
		st[s].erase(st[s].begin(), sti);
		sti=st[s].begin();
		st[sp].insert(*sti);
		st[s].erase(sti);
		res++;

		if(st[pos[N]].count(N)) {
			rec2(t, s, sp, N-1);
			return;
		}
		res+=(int)pow(3., N-1.)-1;
		sti=st[t].begin();
		for(int i=1; i<N; i++) sti++;
		st[s].insert(st[t].begin(), sti);
		st[t].erase(st[t].begin(), sti);
		sti=st[sp].begin();
		st[t].insert(*sti);
		st[sp].erase(sti);
		res++;

		rec2(s, t, sp, N-1);
	}

	int moves(int N, int Dave) {
		res=0;

		cnt=Dave;
		for(int i=0; i<3; i++) st[i].clear();
		for(int i=1; i<=N; i++) st[0].insert(i);
		memset(pos, 0, sizeof(pos));
		rec1(0, 1, 2, N);

		//Daveのシミュレーション結果を配列に格納し直し
		for(int i=0; i<3; i++) {
			for(set <int>::iterator sti=st[i].begin(); sti!=st[i].end(); sti++) {
				pos[*sti]=i;
			}
		}
		for(int i=0; i<3; i++) st[i].clear();
		for(int i=1; i<=N; i++) st[0].insert(i);

		rec2(0, 1, 2, N);

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