Hatena::Grouptopcoder

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

 | 

2015-01-19

Codeforces Round #286 (Div. 1) 09:28 Codeforces Round #286 (Div. 1) - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces Round #286 (Div. 1) - nodchipのTopCoder日記 Codeforces Round #286 (Div. 1) - nodchipのTopCoder日記 のブックマークコメント

A. Mr. Kitayuta, the Treasure Hunter

  • 日本人writerとは聞いていたけど、ここまで露骨なタイトルをつけてくるとは・・・
  • ・・・
  • というか一問目からDP!?
  • かんべんして欲しい。
  • 見た感じdp[前回のジャンプ距離][総距離]だけど
  • 30000^2になるからそのままではダメ
  • 多分速度は√30000回くらいしか変わらないからdp[512][30000]すればよさそう
  • Accepted
static const int OFFSET = 256;
static const int INVALID = INT_MIN;

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

	int N, D;
	cin >> N >> D;
	static int gems[32 * 1024];
	CLEAR(gems);
	REP(n, N) {
		int p;
		cin >> p;
		++gems[p];
	}

	static int dp[OFFSET * 2][32 * 1024];
	fill_n((int*)dp, sizeof(dp) / sizeof(int), INVALID);
	dp[OFFSET][D] = gems[D];
	for (int d = 0; d < 30000; ++d) {
		for (int speedDelta = -OFFSET; speedDelta < OFFSET; ++speedDelta) {
			int speedIndex = speedDelta + OFFSET;
			int speed = D + speedDelta;
			if (dp[speedIndex][d] == INVALID) {
				continue;
			}

			for (int delta = -1; delta <= 1; ++delta) {
				int nextSpeed = speed + delta;
				if (nextSpeed == 0) {
					continue;
				}
				int nextSpeedDelta = nextSpeed - D;
				int nextSpeedIndex = nextSpeedDelta + OFFSET;
				int nextD = d + nextSpeed;
				if (nextD > 30000) {
					continue;
				}

				MAX_UPDATE(dp[nextSpeedIndex][nextD], dp[speedIndex][d] + gems[nextD]);
			}
		}
	}

	int bestAnswer = 0;
	for (int d = 0; d <= 30000; ++d) {
		for (int speed = 0; speed < OFFSET * 2; ++speed) {
			MAX_UPDATE(bestAnswer, dp[speed][d]);
		}
	}

	cout << bestAnswer << endl;
}

B. Mr. Kitayuta's Technology

  • なんだこれorz
  • 強連結成分分解してDAGの最長パス求めて距離が2以上離れたエッジを削除とかそんな感じ?
  • ・・・
  • 違うっぽい
  • じゃあ最小全域有向木とか?
  • 書いてみる
  • ・・・
  • Spaghetti Sourceのライブラリが動かないorz

C. Mr. Kitayuta vs. Bamboos

  • 分かりませんでした

D. Mr. Kitayuta's Colorful Graph

  • 分かりませんでした
  • なんでこんなに解けるんだろう

E. Mr. Kitayuta's Gift

  • 分かりませんでした

結果

#Who=A 500B 1000C 1750D 1750E 2500
243Japan nodchip472 472 00:14

1906->1951 少し上がりました。レーティングに幅が出ているからなのか、このくらいの順位でもレーティングが上がるようです。

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