Hatena::Grouptopcoder

hama_DU@TopCoderへの道

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

ぼちぼちと過去問を続けます。

第二問まではコンスタントに時間内で解けるようになってきました。

SRM457 div2 第一問(250点)

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

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

問題の解釈にやや時間がかかった。

実は行ごとにCの数を数えて、その数を対応する列の下から積み上げればいいと気づいたときは

既に200点を切ってました\(^o^)/


public class TheSquareDivTwo {

	public String[] solve(String[] board) {
		int N = board.length;
		int R[] = new int[N];
		int i = 0;

		// Cを数える
		for (String line : board) {
			for (int j = 0 ; j < line.length() ; j++) {
				if (line.charAt(j) == 'C') {
					R[i]++;
				}
			}
			i++;
		}

		// 下から積み上げるように文字列を生成
		String[] answer = new String[N];
		for (int j = 0 ; j < N ; j++) {
			answer[j] = "";
			for (i = 0 ; i < N ; i++) {
				if (R[i] < N) {
					answer[j] += ".";
					R[i]++;
				} else {
					answer[j] += "C";
				}
			}
		}
		return answer;
	}
}

SRM457 div2 第二問(500点)

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

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

最初場合分けして行こうと思ったが面倒になったので

愚直に4重ループを使った。分に「?」がついていたら「0」に置き換える。


public class TheTriangleBothDivs {

	public String fix(String time) {
		String hour = time.substring(0, 2);
		String minute = time.substring(3, 5);
		String gmt_flg = time.substring(9, 10);
		String gmt_num = time.substring(10, 11);


		String arr_flg[] = new String[] {"+", "-"};
		int minhour = 24;

		// GMTのプラマイ
		for (String flg : arr_flg) {
			if (!gmt_flg.equals("?") && !gmt_flg.equals(flg)) {
				continue;
			}
			// GMTの値
			for (int gmt = 0 ; gmt <= 9 ; gmt++) {
				if (!gmt_num.equals("?") && (gmt_num.charAt(0) - '0') != gmt) {
					continue;
				}

				// 説明文より、「-0」というGMTは無いのでパス
				if (flg.equals("-") && gmt == 0) {
					continue;
				}

				// 時間の10の位
				for (int h1 = 0 ; h1 <= 2 ; h1++) {
					if (hour.charAt(0) != '?' && (hour.charAt(0) - '0') != h1) {
						continue;
					}
					// 時間の1の位
					for (int h2 = 0 ; h2 <= 9 ; h2++) {
						if (hour.charAt(1) != '?' && (hour.charAt(1) - '0') != h2) {
							continue;
						}

						// 時間が24以上だったらパス
						if (h1 == 2 && h2 >= 4) {
							continue;
						}

						int hourhour = h1 * 10 + h2;
						if (flg.equals("+")) {
							hourhour -= gmt;
						} else {
							hourhour += gmt;
						}

						if (hourhour >= 24) {
							hourhour %= 24;
						} else if (hourhour < 0) {
							hourhour += 24;
						}

						if (hourhour < minhour) {
							minhour = hourhour;
						}
					}
				}
			}
		}

		// 最小値が10以下だったら、先頭に「0」をつける
		if (minhour < 10) {
			hour = "0" + minhour;
		} else {
			hour = String.valueOf(minhour);
		}

		// for minute
		if (minute.charAt(0) == '?') {
			minute = "0" + minute.charAt(1);
		}
		if (minute.charAt(1) == '?') {
			minute = minute.charAt(0) + "0";
		}

		return hour + ":" + minute;
	}
}

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;

どこがおかしいか?

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

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

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