Hatena::Grouptopcoder

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

 | 

2014-12-24

Xmas Contest 2014 23:26 Xmas Contest 2014 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Xmas Contest 2014 - nodchipのTopCoder日記 Xmas Contest 2014 - nodchipのTopCoder日記 のブックマークコメント

Problem A: A+B Problem

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

Problem B: Bad Sort?

  • DP[begin][end]のメモ付き探索
  • だと思ったけどWA orz

Problem C: Count Your Ways

  • 20点分は隣接行列のP乗・・・
  • のはずなのにWA orz

Problem D: Distinguished Furry Animals

  • 30点分は周期がずれる最初の値か、min(|C|,|F|)+1・・・
  • だと思ったらWA orz

Problem E: Economic Plan

  • これはmax(最小の次数-1,0)が答えなのでは・・・
  • Accepted 100点
int main() {
	std::ios::sync_with_stdio(false);

	int T;
	cin >> T;
	REP(t, T) {
		int N, M;
		cin >> N >> M;

		vector<set<int> > g(N);
		REP(m, M) {
			int A, B;
			cin >> A >> B;
			--A;
			--B;
			g[A].insert(B);
			g[B].insert(A);
		}

		int answer = INT_MAX;
		for (const auto& s : g) {
			MIN_UPDATE(answer, int(N - 1 - s.size() - 1));
		}
		if (answer <= 0) {
			answer = -1;
		}
		cout << answer << endl;
	}
}

Problem F: Fake Distribution

  • ローカルで分布をサンプリングして平均と分散を比較してみる
  • ・・・
  • ほとんど違いがないorz
  • じゃあ歪度と尖度も調べてみる
  • が少し違う・・・?
  • 2つの分布の尖度の平均値で分岐してみる。
  • Accepted 30点
  • じゃあN次モーメント調べめてみる
  • 10次モーメントが結構違っているっぽい
  • これで行こう
  • Accepted 100点
double calculateAverage(const vector<double>& xs) {
	return accumulate(ALL(xs), 0.0) / xs.size();
}

double calculateMoment(const vector<double>& xs, double average, int n) {
	double v = 0.0;
	for (double x : xs) {
		double diff = x - average;
		double vv = 1.0;
		REP(i, n) {
			vv *= diff;
		}
		v += vv;
	}
	return v / xs.size();
}

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

	int T;
	cin >> T;
	REP(t, T) {
		double sum1 = 0.0;
		double sum2 = 0.0;
		int N;
		cin >> N;
		vector<double> xs;
		REP(n, N) {
			double x;
			cin >> x;
			xs.push_back(x);
		}
		double average = calculateAverage(xs);
		if (calculateMoment(xs, average, 10) > 22.20367032235) {
			cout << "White" << endl;
		}
		else {
			cout << "Black" << endl;
		}
	}
}

Problem G: Geometry Lover

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

Problem H: Hack Me

  • とりあえず入力ファイルをバイナリエディタで開いてみる
  • なんかどこかで見たようなヘッダー・・・
  • 極窓に通してみる
  • bmpファイルだった
  • 開いてみる
  • ▽△▽△▽△・・・?
  • もう一つの方も開いてみる
  • ※□☆※○☆▽※〒◎・・・
  • 一つ一つの記号が一つの数字と対応するのか・・・
  • とりあえず10点分はProblem Dのサンプル出力と一致するので提出
  • Accepted 10点
  • ▽=2 △=3で確定した
  • 10桁で2^32未満の数字は先頭が1~4までのみ
  • 10桁の数字の先頭は☆▽△※の4種類
  • 最大値は4294967295
  • ☆☆・・・で始まる10桁の数字があるので☆は4ではない
  • よって☆=1 ※=4
  • hosさんならきわどい数字を入れてくると思うので0と4294967295は入っていそう
  • □はきっと0なんじゃないかな?
  • 仮に※▽◇※◇○〒□※§が4294967295だとすると
  • 後半が矛盾するけど・・・
  • 前半を当てはめていくとそれっぽく数字が決まる
  • これで出しちゃえ
  • Accepted 100点
  • きた!

結果

RankNameABCDEFGHTotal
16nodchip00001001000100300

前半の絶望的な状況に比べるとまぁまぁ立て直したほうなのではないかと思います。BCDの小さいサイズの問題が解けなかったのが悔しいです。

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