Hatena::Grouptopcoder

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

 | 

2011-01-26

Codeforces Beta Round #53 12:20 Codeforces Beta Round #53 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces Beta Round #53 - nodchipのTopCoder日記 Codeforces Beta Round #53 - nodchipのTopCoder日記 のブックマークコメント

#Who=ABCDE
84nodchip2374+3/-2472 00:14730 00:55972 01:28

A - Square Earth?

  • ドラクエマップ上の二地点間のマンハッタン距離・・・?
  • じゃなかった
  • 二地点はそれぞれ外枠上にあって
  • 外枠だけを通ったときの二地点間の最短距離だ
  • ・・・
  • これ場合分けヤバくね?
  • 安全策をとろう
  • A問題でまさかの幅優先探索!
  • BFS! BFS!
  • ・・・
  • orz
  • Accepted
int main() {
	int n, x1, y1, x2, y2;
	cin >> n >> x1 >> y1 >> x2 >> y2;

	static int dp[1024][1024];
	fill_n((int*)dp, sizeof(dp) / sizeof(int), INT_MAX);

	dp[x1][y1] = 0;
	deque<pair<int, int> > q;
	q.push_back(MP(x1, y1));
	while (!q.empty()) {
		const int x = q.front().first;
		const int y = q.front().second;
		q.pop_front();

		REP(dir, 4) {
			static const int dx[] = {0, 0, 1, -1};
			static const int dy[] = {1, -1, 0, 0};
			const int xx = x + dx[dir];
			const int yy = y + dy[dir];
			if (xx < 0 || n < xx || yy < 0 || n < yy) {
				continue;
			}

			if (!(xx == 0 || xx == n || yy == 0 || yy == n)) {
				continue;
			}

			if (dp[xx][yy] != INT_MAX) {
				continue;
			}

			dp[xx][yy] = dp[x][y] + 1;
			q.push_back(MP(xx, yy));
		}
	}

	cout << dp[x2][y2] << endl;
}

B - Martian Architecture

  • 問題が読みにくい!
  • ようはai~biまでci,ci+1,ci+2,...,ci+bi-ai個ずつ石を置いていく
  • でこれをM回やる
  • biに置いてある石の総和を出力する
  • って問題中複数書かれているcoordinatesが時々別のものを指していたり、複数回出てくるbiが別の物を指していたりと、いろいろ酷い
  • とりあえず普通に解いてみる
  • 解けた
  • submit
  • 撃墜ケースを考えてみようか
  • ・・・
  • あ、自分のやつTLEで落ちるorz
  • 修正した
  • Accepted
int main() {
	int N, M, K;
	scanf("%d%d%d", &N, &M, &K);
	static int as[128 * 1024];
	static int bs[128 * 1024];
	static int cs[128 * 1024];
	REP(m, M) {
		scanf("%d%d%d", &as[m], &bs[m], &cs[m]);
	}

	ll answer = 0;
	REP(k, K) {
		int q;
		cin >> q;
		REP(m, M) {
			const int a = as[m];
			const int b = bs[m];
			const int c = cs[m];
			if (a <= q && q <= b) {
				answer += c + q - a;
			}
		}
	}
	cout << answer << endl;
}

C - Array

  • 数え上げ苦手
  • とりあえず本腰入れて考えてみる
  • 非減少数列と非増加数列はそれぞれ独立に考えて良くて、それぞれA個あったとすると、重複したものは除いて2A-Nが答えになる。
  • 問題は非減少数列が何個あるか。
  • ううむ
  • これchokudai先生のアルゴリズマーの記事に合った動的計画法の例に似ている気がする
  • 最強最速アルゴリズマー養成講座:アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ http://www.itmedia.co.jp/enterprise/articles/1003/06/news002.html
  • 現在の位置の数字をカウントアップするか、次に数字を進めるかの二通り
  • 前者をN回、後者をN-1回行う。何通りの組み合わせがあるか
  • {}_{2n-1}C_{n}だ。
  • modが出てくるのでmodのライブラリを使う
  • 書けた
  • submit
  • Accepted
static const ll MODVAL = 1000000007;
struct M {
	ll x;
	M() : x(0) { }
	M(ll x) : x(x % MODVAL) { }
	M& operator += (const M& rh) {
		x += rh.x;
		x %= MODVAL;
		return *this;
	}
	M operator + (const M& rh) const {
		return M(*this) += rh;
	}
	M& operator -= (const M& rh) {
		x -= rh.x;
		x += MODVAL;
		x %= MODVAL;
		return *this;
	}
	M operator - (const M& rh) const {
		return M(*this) -= rh;
	}
	M& operator *= (const M& rh) {
		x *= rh.x;
		x %= MODVAL;
		return *this;
	}
	M operator * (const M& rh) const {
		return M(*this) *= rh;
	}
	M& operator /= (const M& rh) {
		return *this *= rh.pow(MODVAL - 2);
	}
	M operator / (const M& rh) const {
		return M(*this) /= rh;
	}
	M pow(ll e) const {
		M y(*this);
		M v(1);
		for (; e; y *= y, e >>= 1) {
			if (e & 1) {
				v *= y;
			}
		}
		return v;
	}
	M C(ll k) {
		M v = 1;
		for (ll i = 1; i <= k; ++i) {
			v *= *this - i + 1;
			v /= i;
		}
		return v;
	}
};

int main() {
	int N;
	cin >> N;
	const int N2 = 2 * N - 1;
	M answer(1);
	for (int i = 0; i < N; ++i) {
		answer *= 2 * N - 1 - i;
		answer /= i + 1;
	}
	answer *= 2;
	answer -= N;
	cout << answer.x << endl;
}
  • ところで何で自分C()使わなかったん?

D - Journey

読んでいません

E - Chess

読んでいません

Hack

  • まずはBで自分と同じTLEをしている人を探す
  • +1/-2
  • ・・・微妙
  • 時間がないからAでコーナーケースを探してみよう
  • +2

まとめ

自分のレベルではHackで大きく順位が変わるので、不用意なHackはしないべき

cyuywdxucyuywdxu 2011/02/27 20:26 Pey4Kh <a href="http://opuiexjopuug.com/">opuiexjopuug</a>, [url=http://xxwasgukoppy.com/]xxwasgukoppy[/url], [link=http://jqmdzuourpcv.com/]jqmdzuourpcv[/link], http://bryuahirhqny.com/

ゲスト



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