Hatena::Grouptopcoder

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

 | 

2013-12-24

hos Xmas Contest 2013 19:24 hos Xmas Contest 2013 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - hos Xmas Contest 2013 - nodchipのTopCoder日記 hos Xmas Contest 2013 - nodchipのTopCoder日記 のブックマークコメント

Problem A: Random Trip

  • "2 乗の期待値"・・・?
  • これは誤差狙いかな?
  • 念頭に置いて問題文を読むことにする
  • 見た感じ共通祖先が高速に求められればよいだけっぽい
  • Spaghetti Sourceのオフライン最小共通先祖 (Tarjan)を使う
  • 誤差が怖いので念のためlong doubleで小さい値から順に足しあわせていく
  • 100/100
int main() {
	std::ios::sync_with_stdio(false);
	int T;
	cin >> T;
	REP(t, T) {
		int N;
		cin >> N;

		Graph g(N);

		REP(n, N - 1) {
			int a, b;
			cin >> a >> b;
			--a;
			--b;
			g[a].push_back(Edge(a, b, 0));
			g[b].push_back(Edge(b, a, 0));
		}

		static int depth[64 * 1024];
		fill_n(depth, N, -1);
		depth[0] = 0;
		deque<int> open;
		open.push_back(0);
		while (!open.empty()) {
			int from = open.front();
			open.pop_front();

			for (Edge edge : g[from]) {
				if (depth[edge.dst] != -1) {
					continue;
				}
				depth[edge.dst] = depth[from] + 1;
				open.push_back(edge.dst);
			}
		}

		// 頂点, 確率
		vector<pair<int, int> > P;
		vector<pair<int, int> > Q;
		REP(n, N) {
			int p, q;
			cin >> p >> q;
			if (p) {
				P.push_back(MP(n, p));
			}
			if (q) {
				Q.push_back(MP(n, q));
			}
		}

		vector<Query> queries;
		for (const auto& p : P) {
			for (const auto& q : Q) {
				Query query(p.first, q.first);
				query.p = p.second * q.second;
				queries.push_back(query);
			}
		}

		leastCommonAncestor(g, 0, queries);

		multiset<long double> answer;
		for (const auto& q : queries) {
			long double distance = depth[q.u] + depth[q.v] - depth[q.w] * 2;
			answer.insert(distance * distance * q.p);
		}

		while (answer.size() > 1) {
			long double first = *answer.begin();
			answer.erase(answer.begin());
			long double second = *answer.begin();
			answer.erase(answer.begin());
			answer.insert(first + second);
		}

		printf("%.4Lf\n", *answer.begin() / 10000);
	}
}

Problem B: Rotating Coin

  • 普通の幾何に見える
  • (。・ρ・)ジュル
  • 他のコインの大きさが1円玉の大きさ以上なので途中のコインをスキップすることはないっぽい
  • 接する位置は角度を二分探索して求めれば十分かな
  • 0/100
  • あれ・・・?
  • 回転の割合間違ってたっぽい。
  • こんなことが昔あったような・・・
  • 多分yuizumi先生とJAGの問題を担当した時に二人揃ってやらかしたような・・・
  • 確かymatsu先生が英語版のWikipediaを参照しながら指摘していたような・・・
  • とりあえず倍率をRi倍じゃなくてRi+1倍にしてみる
  • 100/100
typedef complex<double> P;

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

	int T;
	cin >> T;
	REP(t, T) {
		vector<double> Rs;
		vector<P> centers;

		int N;
		cin >> N;
		int x = 0;
		int lastR = 1;
		REP(n, N) {
			int r;
			cin >> r;

			Rs.push_back(r);
			x += r + lastR;
			centers.push_back(P(x));
			lastR = r;
		}

		double answer = 0;
		P current;
		for (int touching = 0; touching + 1 < N; ++touching) {
			double startAngle = arg(current - centers[touching]);

			double L = 0.0;
			double R = startAngle;
			REP(loop, 200) {
				double M = (L + R) / 2;
				P candidate = centers[touching] + polar(Rs[touching] + 1.0, M);
				if (abs(centers[touching + 1] - candidate) < Rs[touching + 1] + 1.0) {
					L = M;
				}
				else {
					R = M;
				}
			}

			double endAngle = L;
			answer += (startAngle - endAngle) * (Rs[touching] + 1.0) / PI;
			current = centers[touching] + polar(Rs[touching] + 1.0, endAngle);
		}

		double startAngle = arg(current - centers[N - 1]);
		double endAngle = 0.0;
		answer += (startAngle - endAngle) * (Rs[N - 1] + 1.0) / PI;

		//answer *= 2.0;

		printf("%.4f\n", answer);
	}
}

Problem C: Really Long Sequences

  • 全く思いつかない
  • とりあえず部分点を狙う
  • 30/100
int main() {
	std::ios::sync_with_stdio(false);

	int T;
	cin >> T;
	REP(t, T) {
		int M, K, P, R, N, L, Q, S;
		cin >> M >> K >> P >> R >> N >> L >> Q >> S;

		static int a[3 * 1024 * 1024];
		static int b[3 * 1024 * 1024];

		a[0] = P;
		for (int i = 1; i <= M + 2 * K; ++i) {
			a[i] = (103 * a[i - 1] + R) % 1000003;
		}
		for (int j = 1; j <= K; ++j) {
			int i1 = 1 + a[M + 2 * j - 1] % M;
			int i2 = 1 + a[M + 2 * j] % M;
			swap(a[i1], a[i2]);
		}

		b[0] = Q;
		for (int i = 1; i <= N + 2 * L; ++i) {
			b[i] = (103 * b[i - 1] + S) % 1000003;
		}
		for (int j = 1; j <= L; ++j) {
			int i1 = 1 + b[N + 2 * j - 1] % N;
			int i2 = 1 + b[N + 2 * j] % N;
			swap(b[i1], b[i2]);
		}

		vector<int> aa(a + 1, a + 1 + M);
		vector<int> bb(b + 1, b + 1 + N);

		vector<int> c = lcs_hs(aa, bb);
		cout << c.size() << endl;
	}
}

Problem D: Rabbit Pairs

  • DP無理

終了後

  • これはもしかして平面グラフにおける完全マッチングの個数を求める問題だったりする・・・?

Problem E: Range Composition

  • これは・・・スキップリスト書くだけ?
  • 変換テーブル書くの結構だるい・・・
  • 100/100
ll S[7] = { 1, 10, 100, 1000, 10000, 100000, 1000000 };

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

	int table[128][4];
	for (int ch = 'A'; ch <= 'Z'; ++ch) {
		int remain = ch - 'A';
		for (int j = 1; j <= 3; ++j) {
			table[ch][j] = remain % 3 + 1;
			remain /= 3;
		}
	}

	int T;
	cin >> T;
	REP(t, T) {
		ll N, Q, J, K, L, M;
		cin >> N >> Q >> J >> K >> L >> M;
		string F;
		cin >> F;

		// [(1<<i)個先][何個目から][x]
		static int skip_list[21][1 << 21][4];
		CLEAR(skip_list);
		for (int i = 1; i <= F.size(); ++i) {
			for (int x = 1; x <= 3; ++x) {
				skip_list[0][i][x] = table[F[i - 1]][x];
			}
		}

		for (int skip = 1; skip <= 20; ++skip) {
			for (int from = 1; from + (1 << skip) <= N + 1; ++from) {
				for (int x = 1; x <= 3; ++x) {
					int xx = skip_list[skip - 1][from][x];
					assert(xx);
					int xxx = skip_list[skip - 1][from + (1 << (skip - 1))][xx];
					assert(xxx);
					skip_list[skip][from][x] = xxx;
				}
			}
		}

		ll r = J;
		for (int i = 1; i <= (1 << Q); ++i) {
			r = (K * r + L) % M;
			int x = 1 + (r % 3);
			r = (K * r + L) % M;
			int a = 1 + (r % N);
			r = (K * r + L) % M;
			ll s = S[r % 7];
			r = (K * r + L) % M;
			int b = 1 + ((a + s + (r % s)) % N);
			if (a > b) {
				swap(a, b);
			}

			int y = x;
			for (int skip = 20; skip >= 0; --skip) {
				if (a + (1 << skip) > b + 1) {
					continue;
				}
				y = skip_list[skip][a][y];
				assert(y);
				a += (1 << skip);
			}

			if (countPop(i) == 1) {
				cout << y;
			}

			r = (K * r + L + i + y) % M;
		}

		cout << endl;
	}
}

Problem F: Replacing Batteries

  • 読んでいません

Problem G: Rumor with Primes

  • これはパターン書くだけ?
  • 違うっぽい
  • オンライン整数列大辞典を読んでみる
  • ・・・
  • 意外と面倒くさい
  • 時間ないorz

Problem H: Read the Input

  • 思いついた単語でひたすら検索・・・
  • 100/100
int main() {
	std::ios::sync_with_stdio(false);

	int T;
	cin >> T;
	REP(t, T) {
		string S;
		cin >> S;
		int N;
		cin >> N;
		vector<int> R;
		REP(n, N) {
			int r;
			cin >> r;
			R.push_back(r);
		}

		switch (t) {
		//case 0:
		//	// outputabsolutedifferencebetweenfirstintegerandlastinteger
		//	cout << abs(R.front() - R.back()) << endl;
		//	break;
		//case 1:
		//	// whatsfirstelementplusnthelement
		//	cout << R[0] + R[N - 1] << endl;
		//	break;
		//case 2:
		//	// findsumoffirsttwonumbersinsequence
		//	cout << R[0] + R[1] << endl;
		//	break;
		//case 3:
		//	// whatslastintegermultipliedbyfirstintegerinsequence
		//	cout << R.back() * R.front() << endl;
		//	break;
		//case 4:
		//	// computeproductoffirsttwoelement
		//	cout << R[0] * R[1] << endl;
		//	break;
		//case 5:
		//	// printsumofallnumbersinsequence
		//	cout << accumulate(ALL(R), 0) << endl;
		//	break;
		//case 6:
		//	// calculatesumoflasttwointegersinsequence
		//	cout << R[N - 2] + R[N - 1] << endl;
		//	break;
		//case 7:
		//	// whatisfirstnumbersubtractedbysecondnumber
		//	cout << R[0] - R[1] << endl;
		//	break;
		//case 8:
		//	// determineproductoflasttwonumbers
		//	cout << R[N - 2] * R[N - 1] << endl;
		//	break;
		//case 9:
		//	// findfirstintegertimeslastintegerinsequence
		//	cout << R[0] * R[N - 1] << endl;
		//	break;
		case 0:
			// outputsmallestintegerinsequence
			sort(ALL(R));
			cout << R[0] << endl;
			break;
		case 1:
			// whichelementinsequenceisfourthsmallest
			sort(ALL(R));
			cout << R[3] << endl;
			break;
		case 2:
			// whatelementhasexactlyfivenumbersbiggerthanit
			// ???
			sort(ALL(R));
			reverse(ALL(R));
			cout << R[5] << endl;
			break;
		case 3:
			// whatsseventhlargestelementfromsequence
			sort(ALL(R));
			reverse(ALL(R));
			cout << R[6] << endl;
			break;
		case 4:
			// outputbiggestoneofgivennumbers
			sort(ALL(R));
			reverse(ALL(R));
			cout << R[0] << endl;
			break;
		case 5:
			// whichnumberinsequencehasexactlytwootherslessthanitself
			sort(ALL(R));
			cout << R[2] << endl;
			break;
		case 6:
			// findsixthsmallestelementinsequence
			sort(ALL(R));
			cout << R[5] << endl;
			break;
		case 7:
			// printeighthbiggestofgivennumbers
			sort(ALL(R));
			reverse(ALL(R));
			cout << R[7] << endl;
			break;
		case 8:
			// printfourthlargestelementfrominput
			sort(ALL(R));
			reverse(ALL(R));
			cout << R[3] << endl;
			break;
		case 9:
			// findsecondgreatestintegerinsequence
			sort(ALL(R));
			reverse(ALL(R));
			cout << R[1] << endl;
			break;
		case 10:
			// whichislargestelementfrominput
			sort(ALL(R));
			cout << R[N - 1] << endl;
			break;
		case 11:
			// whichintegerhasexactlythreeotherintegerssmallerthanit
			sort(ALL(R));
			cout << R[3] << endl;
			break;
		case 12:
			// insequencewhichelementhasexactlyoneothersmallernumber
			sort(ALL(R));
			cout << R[1] << endl;
			break;
		case 13:
			// printeighthsmallestelementfrominput
			sort(ALL(R));
			cout << R[7] << endl;
			break;
		case 14:
			// findsixthgreatestamonggivenintegers
			sort(ALL(R));
			reverse(ALL(R));
			cout << R[5] << endl;
			break;
		case 15:
			// whichisgreatestintegerinsequence
			sort(ALL(R));
			cout << R[N - 1] << endl;
			break;
		case 16:
			// whatisthirdbiggestofgivennumbers
			sort(ALL(R));
			reverse(ALL(R));
			cout << R[2] << endl;
			break;
		case 17:
			// sayhelloforthistestcaseinlowercase
			cout << "hello" << endl;
			break;
		case 18:
			// outputfifthlargestelementofsequence
			sort(ALL(R));
			reverse(ALL(R));
			cout << R[4] << endl;
			break;
		case 19:
			// printsmallestoneofgivennumbers
			sort(ALL(R));
			cout << R[0] << endl;
			break;
		}
	}
}

結果

RankNameABCDEFGHTotal
14nodchip10010030010000100430

実力相当の結果が出たと思います。欲を言えばGを解きたかったのですが、時間が足りずに解けませんでした。実装力が落ちています。

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