Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-03-16[過去問]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

http://topcoder.g.hatena.ne.jp/hama_DU/20100308/p3

解けたのでレポート。


方針

以下の3つの場合に分けて考える。

まわりの六つの升にはすべて異なる数が入るため、

重複する分もまとめてカウントし、最後に6で割る。

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

f:id:hama_DU:20100309001327p:image

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

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

はじめに用いる余りの数(図では色で表現)の組み合わせそれぞれについて、

使える数字(割った余りがcenterでもotherでもない数)で残りを埋める順列を求める。

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

f:id:hama_DU:20100309001328p:image


long ptnb = 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;
			}

			long base = map[center] * map[other] * map[another] * (map[another] - 1) * 3;
			map[other]--;
			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;
							}
							long base2 = 0;
							if (a == b && a == c) {
								base2 = map[a] * (map[a] - 1) * (map[a] - 2);
							} else if (a == b) {
								base2 = map[a] * (map[a] - 1) * map[c];
							} else if (a == c) {
								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 (base2 >= 1) {
								ptnb += base * base2;
							}
						}
					}
				}
			}
			map[other]++;
		}
	}
}

前回と異なるのは、残りをすべて同じ余りの数(同色)で埋めることも許している点と、

ひとつだけ異なる余りの数(上図の場合赤)を用いる位置が3通りあるため、baseを3でかけている点である。


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

f:id:hama_DU:20100309001329p:image

long 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;
				}
				long base = map[center] * map[other] * map[another] * map[ananother];
				map[other]--;
				map[another]--;
				map[ananother]--;
				if (base >= 1) {
					for (int a = 0 ; a < k ; a++) {
						if (a == center || a == other || a == another) {
							continue;
						}
						for (int b = 0 ; b < k ; b++) {
							if (b == center || b == other || b == ananother) {
								continue;
							}
							for (int c = 0 ; c < k ; c++) {
								if (c == center || c == another || c == ananother) {
									continue;
								}
								long base2 = 0;
								if (a == b && a == c) {
									base2 = map[a] * (map[a] - 1) * (map[a] - 2);
								} else if (a == b) {
									base2 = map[a] * (map[a] - 1) * map[c];
								} else if (a == c) {
									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 (base2 >= 1) {
									ptnc += base * base2;
								}
							}
						}
					}
				}
				map[other]++;
				map[another]++;
				map[ananother]++;
			}
		}
	}
}

はじめに3色を使う場合と同様に、残りを同色で埋めることも許している。

これでモレなく計算できた。すべて足して6で割れば答えが求まる。