Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-06-19SRM473 Div1

SRM473 Div1 250 SequenceOfCommands

| 15:56 | SRM473 Div1 250 SequenceOfCommands - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM473 Div1 250 SequenceOfCommands - SRM diary(Sigmar) SRM473 Div1 250 SequenceOfCommands - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→シミュレーションかな・・・面倒くさいな・・・

→実は1周終わった時点で初期状態と同じ向きを向いていたらunboundedで良いのではないか(←間違い)

→書く→サンプル通る→提出→500の問題に行く

・・・(中略)

→終了5分前に見直す

→まずい、間違っている・・・Sが1つも出てこない場合に明らかに間違った答えを返すことに気づく

→直す、submit→else文が抜けてる→直す、submit・・・できず時間切れ

→よく見たらまだ間違ってる。1周で原点に戻ってくるものは全てboundedだ。シミュレーションしないと解けない。終わった・・・


チャレンジフェーズ

→みなさん、シミュレーションで解いてますね。撃墜できません。

→撃墜されました。終わった・・・


以下、終了後ちゃんと書き直したコードです。

1周後の状態で判定してますが4周後に原点に戻るかの判定でも良いですね。

class SequenceOfCommands {
public:
	string whatHappens(vector <string> commands) {
		string res;
		int x=0, y=0;
		int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
		int dir=0;

		for(int i=0; i<(int)commands.size(); i++) {
			for(int j=0; j<(int)commands[i].size(); j++) {
				if(commands[i][j]=='S') {
					x+=dx[dir]; y+=dy[dir];
				} else if(commands[i][j]=='R') {
					dir=(dir+1)%4;
				} else if(commands[i][j]=='L') {
					dir=(dir+3)%4;
				}
			}
		}

		if(x==0 && y==0) res="bounded";
		else if(dir%4==0) res="unbounded";
		else res="bounded";

		return res;
	}
};

SRM473 Div1 500 RightTriangle

| 15:56 | SRM473 Div1 500 RightTriangle - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM473 Div1 500 RightTriangle - SRM diary(Sigmar) SRM473 Div1 500 RightTriangle - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→えーと、直角三角形の外心は斜辺の中点になるので・・・ある点と円の反対側の点がredなら、points-2を加えれば良いかな?

→えらく簡単だな・・・

→書く→サンプル通る

→一応適当にランダムなケースを入れてみようかな

→特に問題なし

→提出→1000の問題に行く


1000の問題はよく分からない。時間がなくなったので諦め。


チャレンジフェーズ

→速攻で撃墜される。

→ええええ!?何で・・・

→チャットで誰か話していたけど、ワーストケースの作り方が誤っていた

→a,b,cが全部0のときが、ワーストケース。確かに。何でこんなことに気付かなかったのか・・・


確かに500にしては簡単すぎたし、ワーストケースもあまり考えていませんでした。

でも、入力ケースを作成する部分がトラップっていうのはどうなの、という気もします。それも含めて問題だということなんだろうけど・・・


入力ケースの作成を二分探索に直したら通りました。

typedef long long ll;

class RightTriangle {
public:
	long long triangleCount(int places, int points, int a, int b, int c) {
		long long res=0;
		bool red[1000010];
		int MOD=places;
		set <int> s;

		if(places&1) return 0;
		memset(red, false, sizeof(red));
		for(int i=0; i<places; i++) s.insert(i);
		for(int i=0; i<points; i++) {
			int tmp=((ll)a*i*i%MOD+(ll)b*i%MOD+c)%MOD;
			set <int>::iterator sii=s.lower_bound(tmp);
			if(sii==s.end()) sii=s.lower_bound(0);
			red[*sii]=true;
			s.erase(sii);
		}

		for(int i=0; i<places/2; i++) {
			if(red[i] && red[i+places/2]) 
				res+=points-2;
		}

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