Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-03-08[過去問]SRM457(DIV2)

SRM457 div2 第三問(1000点)

| SRM457 div2 第三問(1000点) - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - SRM457 div2 第三問(1000点) - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=10694

とりあえず考えたことのメモ。

1~nまでの数が使用でき、kで割った余りを使うとする。

ここで、あらかじめ、kで割った余りがi(0≦i≦k-1)であるもの(1~n)を数えてmap[i]とおく。


もちろん、数をいちいち当てはめていったら時間がたりないので、このように場合分けしてみた。

真ん中を埋め、周りの三つを同じ余りで埋める場合。

f:id:hama_DU:20100309001327p:image

こんな感じで計算できるんじゃないかと。

for (int center = 0; center < k; center++) {
	for (int other = 0; other < k; other++) {
		if (other == center) {
			continue;
		}
		int ptn = 0;
		for (int i = 1; i <= n; i++) {
			if ((i % k) != center && (i % k) != other) {
				ptn++;
			}
		}
		int base = map[center] * map[other] * (map[other] - 1) * (map[other] - 2);
		int base2 = ptn * (ptn - 1) * (ptn - 2);
		if (base >= 1 && base2 >= 1) {
			ptna += base * base2;
		}
	}
}
ptna /= 6;

周りの三つを二種類の余りを使って埋める場合。

f:id:hama_DU:20100309001328p:image

三つの余りを決めて、計算しようとしているが

回した場合同じになるケースの判定が微妙。

果たして一律に3で割っていいものかどうか・・・

ちなみに、色で塗ってない残り三つの場所には、

すべて同じ余りの数は使わないようにしています。

その場合、上のパターンと同じものができてしまうため。

for (int center = 0; center < k; center++) {
	for (int other = 0; other < k; other++) {
		if (other == center) {
			continue;
		}
		for (int another = 0; another < k; another++) {
			if (another == center || another == other) {
				continue;
			}

			int base = map[center] * map[other] * map[another] * (map[another] - 1);
			if (base >= 1) {
				for (int a = 0 ; a < k ; a++) {
					if (a == another || a == center) {
						continue;
					}
					for (int b = 0 ; b < k ; b++) {
						if (b == another || b == center || b == other) {
							continue;
						}
						for (int c = 0 ; c < k ; c++) {
							if (c == another || c == center || c == other) {
								continue;
							}
							if (a == b && a == c) {
								continue;
							}

							if (a == other) {
								map[a]--;
							}
							int base2 = 0;
							if (a == b) {
								if (a == other) {
									base2 = 0;
								} else {
									base2 = map[a] * (map[a] - 1) * map[c];
								}
							} else if (a == c) {
								if (a == other) {
									base2 = 0;
								} else {
									base2 = map[a] * (map[a] - 1) * map[b];
								}
							} else if (b == c) {
								base2 = map[b] * (map[b] - 1) * map[a];
							} else {
								base2 = map[a] * map[b] * map[c];
							}
							if (a == other) {
								map[a]++;
							}

							if (base2 >= 1) {
								ptnb += base * base2;
							}
						}
					}
				}
			}
		}
	}
}
ptnb /= 3;

真ん中を埋め、周りの三つをすべて異なる余りを使って埋める場合。

f:id:hama_DU:20100309001329p:image

色で塗ってない残り三つの場所には、すべて異なる余りの数を使うようにしている。

理由は上二つのパターンとかぶってしまうため。

int ptnc = 0;
for (int center = 0; center < k; center++) {
	for (int other = 0; other < k; other++) {
		if (other == center) {
			continue;
		}
		for (int another = 0; another < k; another++) {
			if (another == center || another == other) {
				continue;
			}
			for (int ananother = 0; ananother < k; ananother++) {
				if (ananother == center || ananother == other
						|| ananother == another) {
					continue;
				}
				int base = map[center] * map[other] * map[another] * map[ananother];
				if (base >= 1) {
					for (int a = 0 ; a < k ; a++) {
						if (a == another || a == center || a == other) {
							continue;
						}
						for (int b = 0 ; b < k ; b++) {
							if (b == another || b == center || b == other) {
								continue;
							}
							for (int c = 0 ; c < k ; c++) {
								if (c == another || c == center || c == other) {
									continue;
								}
								if (a == b || a == c || b == c) {
									continue;
								}

								int base2 = map[a] * map[b] * map[c];
								if (base2 >= 1) {
									ptnc += base * base2;
								}
							}
						}
					}
				}
			}
		}
	}
}
ptnc /= 6;

どこがおかしいか?

最後の割り算の数が怪しいような気がします。

特に形が対称でない第二のパターン。

てかそもそもこんな解き方でいいのかな?(アプローチは正しいのか?)