Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-02-27SRM498 Div1(Practice)

SRM498 Div1 250 FoxSequence

| 17:20 | SRM498 Div1 250 FoxSequence - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM498 Div1 250 FoxSequence - SRM diary(Sigmar) SRM498 Div1 250 FoxSequence - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

やるだけだがスピード勝負なので書き方の工夫が求められる

以下の自分のソースはシーケンスを前から順番にイテレートして条件に合うか調べているだけだが意外とこまごまして書きづらい・・

1位の人のを見ると、シーケンスの差分が変わるところだけを抽出して条件に合うかチェックしており短く書けているので頭いいなと思った

ソースコード

class FoxSequence {
public:
	string isValid(vector <int> seq) {
		int N=seq.size();
		if(N<5) return "NO";

		int i=1;

		int diff=seq[1]-seq[0];
		if(diff<=0) return "NO";
		while(i<N && seq[i]-seq[i-1]==diff) i++;
		if(i==N) return "NO";

		diff=seq[i]-seq[i-1];
		if(diff>=0) return "NO";
		while(i<N && seq[i]-seq[i-1]==diff) i++;
		if(i==N) return "NO";

		while(i<N && seq[i]-seq[i-1]==0) i++;
		if(i==N) return "NO";

		diff=seq[i]-seq[i-1];
		if(diff<=0) return "NO";
		while(i<N && seq[i]-seq[i-1]==diff) i++;
		if(i==N) return "NO";

		diff=seq[i]-seq[i-1];
		if(diff>=0) return "NO";
		while(i<N && seq[i]-seq[i-1]==diff) i++;
		if(i!=N) return "NO";

		return "YES";
	}
};

SRM498 Div1 450 FoxStones

| 17:20 | SRM498 Div1 450 FoxStones - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM498 Div1 450 FoxStones - SRM diary(Sigmar) SRM498 Div1 450 FoxStones - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

各セルについて全マークセルとの距離を求め、全ての距離が同じセルは入れ替え可能と判断できる

あとは掛け合わせるだけ・・・って簡単すぎないか?450とはいえMediumこんなんでいいのか・・・

ソースコード

const int MOD=1000000009;

class FoxStones {
public:
	int getCount(int N, int M, vector <int> sx, vector <int> sy) {
		ll res=1;

		map <vector <int>, int> cnt;
		for(int x=1; x<=N; x++) {
			for(int y=1; y<=M; y++) {
				vector <int> vi;
				for(int i=0; i<(int)sx.size(); i++) {
					vi.push_back(max(abs(x-sx[i]), abs(y-sy[i])));
				}
				cnt[vi]++;
			}
		}
		
		for(map <vector <int>, int>::iterator mpi=cnt.begin(); mpi!=cnt.end(); mpi++) {
			int v=mpi->second;
			for(int i=v; i>=2; i--) res=res*i%MOD;
		}

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