Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2009-06-14

Single Round Match 442 @ TopCoder 09:52 Single Round Match 442 @ TopCoder - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 442 @ TopCoder - nodchipのTopCoder日記 Single Round Match 442 @ TopCoder - nodchipのTopCoder日記 のブックマークコメント

Single Round Match 442 @ TopCoderの参加記録です。

Easy 250 Underprimes

AからBまでの自然数の中で、素因数の数が素数となっているものの数を求めよ。

やるだけ問題です。エラトステネスのふるいを書いてごにょごびょして終わりです。

エラトステネスのふるいを書き間違えたのはここだけの秘密です。

class Underprimes {
public:
	bool isUnderprime(int i, const vector<int>& primes)
	{
		if (!flag[i]){
			return false;
		}
		int counter = 0;
		int primeIndex = 0;
		while (i != 1){
			if (i % primes[primeIndex] == 0){
				++counter;
				i /= primes[primeIndex];
			} else {
				++primeIndex;
			}
		}
		return !flag[counter];
	}
	int howMany(int A, int B) {
		memset(flag, 0, sizeof(flag));
		for (int i = 2; i <= 200000; ++i){
			if (flag[i]){
				continue;
			}
			for (int j = i + i; j <= 200000; j += i){
				flag[j] = true;
			}
		}
		vector<int> primes;
		for (int i = 2; i <= 200000; ++i){
			if (!flag[i]){
				primes.push_back(i);
			}
		}

		int result = 0;
		for (int i = A; i <= B; ++i){
			if (isUnderprime(i, primes)){
				++result;
			}
		}
		return result;
	}
}

Midium 550 BedroomFloor

http://www.topcoder.com/contest/problem/BedroomFloor/floortiles.png

こんな感じのフロアの(x1,y1)-(x2,y2)を対角線とする矩形について、この部分を構成するためには1x5のサイズのパネルが最低何枚必要か求めよ。

見た瞬間に超重量級の実装問題だと思いました。解けるはずありませんが950が解けたためしがないので迷わず解き始めました。

5x5に収まる場合、5xYに縦に伸びる場合、Xx5に横に伸びる場合、それ以上の大きさの場合に分けて実装しました。

最終的には三項演算子の優先順位を間違えるという大失敗と、一番最後の部分の変数の書き間違いにより撃墜されてしまいました。

以下はPracticeを通したソースです。もっと短くできるはずです。

class BedroomFloor {
public:
	bool isHorizontal(int x, int y){
		return (x + y) % 2 == 0;
	}
	long long numberOfSticks(int x1, int y1, int x2, int y2) {
		map<int, ll> needed;

		const ll centerLeft = (x1 + 4) / 5 * 5;
		const ll centerRight = x2 / 5 * 5;
		const ll centerTop = (y1 + 4) / 5 * 5;
		const ll centerBottom = y2 / 5 * 5;

		if (centerLeft > centerRight){
			if (centerTop > centerBottom){
				//パネルの中にすっぽり
				ll indexX = x1 / 5;
				ll indexY = y1 / 5;
				if (isHorizontal(indexX, indexY)){
					needed[x2 - x1] += y2 - y1;
				} else {
					needed[x2 - x1] += y2 - y1;
				}
			} else {
				//縦長
				const ll extraTop = centerTop - y1;
				const ll extraBottom = y2 - centerBottom;
				const ll indexX = x2 / 5;
				const ll indexTop = centerTop / 5 - 1;
				const ll indexBottom = centerBottom / 5;
				if (extraTop){
					if (isHorizontal(indexX, indexTop)){
						needed[x2 - x1] += extraTop;
					} else {
						needed[extraTop] += x2 - x1;
					}
				}

				const ll indexBegin = indexTop + 1;
				const ll indexEnd = indexBottom;
				const ll horizontal = (indexEnd - indexBegin) / 2 + (((indexEnd - indexBegin) % 2 == 1 && isHorizontal(indexX, indexBegin)) ? 1 : 0);
				const ll vertical = (indexEnd - indexBegin) / 2 + (((indexEnd - indexBegin) % 2 == 1 && !isHorizontal(indexX, indexBegin)) ? 1 : 0);
				needed[x2 - x1] += 5 * horizontal;
				needed[5] += (x2 - x1) * vertical;

				if (extraBottom){
					if (isHorizontal(indexX, indexBottom)){
						needed[x2 - x1] += extraBottom;
					} else {
						needed[extraBottom] += x2 - x1;
					}
				}
			}
		} else {
			if (centerTop > centerBottom){
				//横長
				const ll extraLeft = centerLeft - x1;
				const ll extraRight = x2 - centerRight;
				const ll indexY = y2 / 5;
				const ll indexLeft = centerLeft / 5 - 1;
				const ll indexRight = centerRight / 5;

				if (extraLeft){
					if (isHorizontal(indexLeft, indexY)){
						needed[extraLeft] += y2 - y1;
					} else {
						needed[y2 - y1] += extraLeft;
					}
				}

				const ll indexBegin = indexLeft + 1;
				const ll indexEnd = indexRight;
				const ll horizontal = (indexEnd - indexBegin) / 2 + (((indexEnd - indexBegin) % 2 == 1 && isHorizontal(indexBegin, indexY)) ? 1 : 0);
				const ll vertical = (indexEnd - indexBegin) / 2 + (((indexEnd - indexBegin) % 2 == 1 && !isHorizontal(indexBegin, indexY)) ? 1 : 0);
				needed[y2 - y1] += 5 * vertical;
				needed[5] += (y2 - y1) * horizontal;

				if (extraRight){
					if (isHorizontal(indexRight, indexY)){
						needed[extraRight] += y2 - y1;
					} else {
						needed[y2 - y1] += extraRight;
					}
				}

			} else {
				//次に進む
				needed[5] += (centerRight - centerLeft) * (centerBottom - centerTop) / 5;

				const ll extraLeft = centerLeft - x1;
				const ll extraRight = x2 - centerRight;
				const ll extraTop = centerTop - y1;
				const ll extraBottom = y2 - centerBottom;

				//あまったところのパネル番号
				const ll indexLeft = centerLeft / 5 - 1;
				const ll indexRight = centerRight / 5;
				const ll indexTop = centerTop / 5 - 1;
				const ll indexBottom = centerBottom / 5;

				if (extraLeft && extraTop){
					if (isHorizontal(indexLeft, indexTop)){
						needed[extraLeft] += extraTop;
					} else {
						needed[extraTop] += extraLeft;
					}
				}
				if (extraLeft){
					const ll indexBegin = indexTop + 1;
					const ll indexEnd = indexBottom;
					const ll horizontal = (indexEnd - indexBegin) / 2 + (((indexEnd - indexBegin) % 2 == 1 && isHorizontal(indexLeft, indexBegin)) ? 1 : 0);
					const ll vertical = (indexEnd - indexBegin) / 2 + (((indexEnd - indexBegin) % 2 == 1 && !isHorizontal(indexLeft, indexBegin)) ? 1 : 0);
					needed[extraLeft] += 5 * horizontal;
					needed[5] += extraLeft * vertical;
				}
				if (extraLeft && extraBottom){
					if (isHorizontal(indexLeft, indexBottom)){
						needed[extraLeft] += extraBottom;
					} else {
						needed[extraBottom] += extraLeft;
					}
				}
				if (extraTop){
					const ll indexBegin = indexLeft + 1;
					const ll indexEnd = indexRight;
					const ll horizontal = (indexEnd - indexBegin) / 2 + (((indexEnd - indexBegin) % 2 == 1 && isHorizontal(indexTop, indexBegin)) ? 1 : 0);
					const ll vertical = (indexEnd - indexBegin) / 2 + (((indexEnd - indexBegin) % 2 == 1 && !isHorizontal(indexTop, indexBegin)) ? 1 : 0);
					needed[extraTop] += 5 * vertical;
					needed[5] += extraTop * horizontal;
				}
				if (extraBottom){
					const ll indexBegin = indexLeft + 1;
					const ll indexEnd = indexRight;
					const ll horizontal = (indexEnd - indexBegin) / 2 + (((indexEnd - indexBegin) % 2 == 1 && isHorizontal(indexBottom, indexBegin)) ? 1 : 0);
					const ll vertical = (indexEnd - indexBegin) / 2 + (((indexEnd - indexBegin) % 2 == 1 && !isHorizontal(indexBottom, indexBegin)) ? 1 : 0);
					needed[extraBottom] += 5 * vertical;
					needed[5] += extraBottom * horizontal;
				}
				if (extraRight && extraTop){
					if (isHorizontal(indexRight, indexTop)){
						needed[extraRight] += extraTop;
					} else {
						needed[extraTop] += extraRight;
					}
				}
				if (extraRight){
					const ll indexBegin = indexTop + 1;
					const ll indexEnd = indexBottom;
					const ll horizontal = (indexEnd - indexBegin) / 2 + (((indexEnd - indexBegin) % 2 == 1 && isHorizontal(indexRight, indexBegin)) ? 1 : 0);
					const ll vertical = (indexEnd - indexBegin) / 2 + (((indexEnd - indexBegin) % 2 == 1 && !isHorizontal(indexRight, indexBegin)) ? 1 : 0);
					needed[extraRight] += 5 * horizontal;
					needed[5] += extraRight * vertical;
				}
				if (extraRight && extraBottom){
					if (isHorizontal(indexRight, indexBottom)){
						needed[extraRight] += extraBottom;
					} else {
						needed[extraBottom] += extraRight;
					}
				}

			}
		}

		ll rest[5] = {0, 0, 0, 0, 0};

		long long result = needed[5];
		needed[5] = 0;

		result += needed[4];
		rest[1] += needed[4];
		needed[4] = 0;

		result += needed[3];
		rest[2] += needed[3];
		needed[3] = 0;
		
		const ll rest2 = min(needed[2], rest[2]);
		needed[2] -= rest2;
		rest[2] -= rest2;

		result += (needed[2] + 1) / 2;
		rest[1] += needed[2] / 2;
		rest[3] += needed[2] % 2;
		needed[2] = 0;

		const ll rest1 = min(rest[3] * 3 + rest[2] * 2 + rest[1], needed[1]);
		needed[1] -= rest1;
		rest[1] -= rest1;

		result += ((needed[1]) + 4) / 5;
		rest[1] = 0;

		return result;
	}
}

Hard 950 NowhereLand

ある国の中の街のいくつかのペアが友好関係にある。この国にはいくつかのガーディアン(?)があり、初期状態ではそれぞれの警備会社からいくつかの街にガード(?)が派遣されている。また各警備会社には何人かのエージェントがおり、これらもいくつかの街に派遣されている。エージェントはガードになることができる。友好関係にある街は、あるガーディアンから一方がガードを派遣されており、一夫がガードを派遣されていないとconflict状態となる。conflict状態が最も少なくなるようなガードの配置をしたときのconflict状態の数を求めよ。

ほとんど読めませんでした。後から他の方に解法を聞いたところ、友好関係にある街同士をつなぎ、ガードがいる街をsrcエージェントがいる街をsinkにつないで最大フローとの事です。細かいところが分かっていないのですが、最小カットがconflictの数と一致するとの事です。

撃墜フェイズ

予想通り550が撃墜祭りでした。{1,1,4,4}でなんとか1人だけ撃墜することができました。

結果

o x x +50 1803->1885と上がりました。

総評

550が解けなかったのが悔しいです。というか無理ゲー臭がした時点で負けだと思いました。

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20090614
 |