Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-02-27SRM498 Div1(Practice)

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