Hatena::Grouptopcoder

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

 | 

2012-11-27

NPCA Programming Contest Alpha #1 (Div.1) 21:45 NPCA Programming Contest Alpha #1 (Div.1) - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - NPCA Programming Contest Alpha #1 (Div.1) - nodchipのTopCoder日記 NPCA Programming Contest Alpha #1 (Div.1) - nodchipのTopCoder日記 のブックマークコメント

#10: 黒い板

  • 1問目にしては難しいような・・・
  • 最後の教室を塗って直帰するのが一番距離が短くなりそう
  • 後ろから順に貪欲かな?
  • Wrong Answer
  • 違うっぽいorz

#11: 宿題

  • 全く分かりませんでした

#12: プール掃除

  • これは答えの値で二分探索をすれば良いのでは・・・?
  • NPCA最後の良心的問題
  • Accepted
int countGroup(vector<ll>& ws, ll maxMin) {
	int numberOfGroups = 1;
	int numberOfBackets = 1;
	ll minWeight = ws[0];
	ll sumOfWeights = ws[0];
	for (int i = 1; i < ws.size(); ++i) {
		MIN_UPDATE(minWeight, ws[i]);
		sumOfWeights += ws[i];
		++numberOfBackets;
		if (sumOfWeights - minWeight * numberOfBackets > maxMin) {
			++numberOfGroups;
			numberOfBackets = 1;
			minWeight = ws[i];
			sumOfWeights = ws[i];
		}
	}
	return numberOfGroups;
}

int main() {
	std::ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	vector<ll> ws;
	REP(n, N) {
		ll w;
		cin >> w;
		ws.push_back(w);
	}

	// 整数用二分探索
	ll L = 0;
	ll R = 1LL << 62;
	while (L + 1 < R){
		ll mid = (L + R) / 2;
		if (countGroup(ws, mid) > M){
			L = mid;
		} else {
			R = mid;
		}
	}

	for (ll answer = MAX(0LL, L - 10); ; ++answer) {
		if (countGroup(ws, answer) > M) {
			continue;
		}

		cout << answer << endl;
		break;
	}
}

#13: 世界史ネットワーキングサービス

  • 区間クエリ・・・?
  • WikipediaにはO(N log N + k)って書いてあるんだけどどうするんだろう?
  • ・・・
  • クエリについて既に生まれている人の数から死んだ人の数を引けば良い?
  • 既に生まれた人は予め偉人を生まれた順にソートすればO(logN)で求まる
  • 死んだ人はFenwick木で管理すればO(logN)で求められそう・・・
  • Accepted
struct Hero {
	int left, right, index;
};

bool compairByBegin(const Hero& lh, const Hero& rh) {
	return lh.left != rh.left ? lh.left < rh.left :
		lh.right != rh.right ? lh.right < rh.right :
		lh.index < rh.index;
}

bool compairByEnd(const Hero& lh, const Hero& rh) {
	return lh.right != rh.right ? lh.right < rh.right :
		lh.left != rh.left ? lh.left < rh.left :
		lh.index < rh.index;
}

template <class T>
struct fenwick_tree {
  vector<T> x;
  fenwick_tree(int n) : x(n, 0) { }
  T sum(int i, int j) {
    if (i == 0) {
      T S = 0;
      for (j; j >= 0; j = (j & (j + 1)) - 1) S += x[j];
      return S;
    } else return sum(0, j) - sum(0, i-1);
  }
  void add(int k, T a) {
    for (; k < x.size(); k |= k+1) x[k] += a;
  }
};

int main() {
	std::ios::sync_with_stdio(false);

	vector<Hero> herosByBegin;
	int N;
	cin >> N;
	REP(n, N) {
		int a, b;
		cin >> a >> b;
		Hero hero = {a, b, n};
		herosByBegin.push_back(hero);
	}

	vector<Hero> herosByEnd = herosByBegin;
	sort(ALL(herosByBegin), compairByBegin);
	sort(ALL(herosByEnd), compairByEnd);

	vector<int> heroBegins(N);
	REP(n, N) {
		heroBegins[n] = herosByBegin[n].left;
	}

	// 元の偉人index -> 誕生順
	vector<int> heroToByBegin(N);
	REP(n, N) {
		heroToByBegin[herosByBegin[n].index] = n;
	}

	// indexは誕生順
	fenwick_tree<int> tree(N);

	int deadIndex = 0;
	vector<int> answers(N);
	REP(n, N) {
		const Hero& hero = herosByBegin[n];
		while (deadIndex < N && herosByEnd[deadIndex].right < hero.left) {
			tree.add(heroToByBegin[herosByEnd[deadIndex++].index], 1);
		}

		int bornTillRight = distance(heroBegins.begin(), upper_bound(ALL(heroBegins), hero.right));
		int alreadyDead = tree.sum(0, bornTillRight - 1);
		answers[hero.index] = bornTillRight - alreadyDead - 1;
	}

	REP(n, N) {
		cout << answers[n] << endl;
	}
}

#14: 約数スマッシュ

  • 数論苦手・・・
  • 嘆いていてもしかたがないので何とかする
  • これは答えの時間計算量がO(N^{0.5})になるのではなかろうか?
  • "for (int i = 1; i <= n; +i) sum += n / i;" で1からnまでの約数の個数の総和が求まるっぽい
  • これをnの平方根までのループに抑えれば良いっぽい
  • 平方根超えたあたりの数字は同じ数字が連続しているはずだからまとめて求められるはず
  • あとは勘で適当にやってつじつま合わせてエイヤー!
  • Accepted
ll calc(ll a) {
	ll result = 0;
	for (ll i = 1; i <= a; ++i) {
		result += a / i;
	}
	return result;
}

ll calc2(ll a) {
	if (a <= 0) {
		return 0;
	}
	ll result = 0;
	ll i;
	for (i = 1; i * i <= a; ++i) {
		result += a / i;
		result += i * (a / i - a / (i + 1));
	}
	--i;
	if (a < i * i + i) {
		result -= a / i;
	}
	return result;
}

int main() {
	std::ios::sync_with_stdio(false);

	//for (int i = 1; i < 1000; ++i) {
	//	cout << i << " " << calc(i) << " " << calc2(i) << " " << (calc(i) == calc2(i) ? "OK" : "NG") << endl;
	//}

	ll N, M;
	cin >> N >> M;
	//cout << calc(M) - calc(N - 1) << endl;
	cout << calc2(M) - calc2(N - 1) << endl;
}

#15: リニア植物

  • 分かりませんでした

#16: あみだくじ

  • バブルソートの交換回数をゴニョゴニョするっぽいけど・・・
  • 分かりませんでした

#17: まわし読み

  • フローっぽいけどよくわからない

結果

RankUsernameSolvedPenalty#10#11#12#13#14#15#16#17
21nodchip38:18-2-11:41 (0)3:37 (0)3:00 (0)---

正直現役の人にはかないませんorz

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