2013-04-27

■ [GCJ] Google Code Jam 2013 Round1A 18:40

Round1B・1CはTCOマラソン期間中になるのでここで通過しておきたいという事情があってScalaではなくC++で

• A

オーバーフローに気をつけつつ二分探索する。

// #includeは略
using namespace std;
typedef long long ll;

ll r,t;

ll solve() {
	scanf("%lld %lld", &r, &t);
	ll left = 0;
	ll right = (ll)sqrt(t) + 1;
	while(left + 1 < right) {
		ll mid = (left + right) / 2;
		ll sum = mid * (2 * r + 2 * mid - 1);
		if (sum > t || (2 * r + 2 * mid - 1) > (ll)2e18 / mid + 1) {
			right = mid;
		} else {
			left = mid;
		}
	}
	return left;
}

int main() {
	int T;
	scanf("%d", &T);
	for (int tc = 1; tc <= T; ++tc){
		printf("Case #%d: %lld\n", tc, solve());
	}
}

• B

Greedyに使う。O(N^2)。

後の作業で今の位置のものより価値が低いのがあったら、その分のエネルギーは今の所で使っておいた方が良い。今の位置の以上の価値のものが出てきたらストップ。みたいな感じ

// #includeは略
using namespace std;
typedef long long ll;

ll E,R,N,V[10001];

ll solve() {
	scanf("%lld %lld %lld", &E, &R, &N);
	for (int i = 0; i < N; ++i) {
		scanf("%lld", V+i);
	}
	ll ans = 0;
	int e = E;
	for (int i = 0; i < N; ++i) {
		ll use = max(0LL, E - R);
		for (int j = i+1; j < N && use > 0; ++j) {
			if (V[j] >= V[i]) break;
			use = max(0LL, use - R);
			if (j == N-1) use = 0;
		}
		if (i == N-1) use = 0;
		if (use < e) {
			ans += (e - use) * V[i];
			e = use;
		}
		e = min(E, e + R);
	}
	return ans;
}

int main() {
	int T;
	scanf("%d", &T);
	for (int tc = 1; tc <= T; ++tc){
		printf("Case #%d: %lld\n", tc, solve());
	}
}

• C small

3と5の数は、それぞれ一番大きな因数の数。

2と4の数は、2の因数が奇数個のものがあったら少なくとも2は1つ含まれている…みたいな感じで適当に

// #includeは略
using namespace std;
typedef long long ll;

int R,N,M,K;

int count(int& v, int div){
	int ret = 0;
	while(v % div == 0) {
		v /= div;
		++ret;
	}
	return ret;
}

void solve() {
	scanf("%d %d %d %d", &R, &N, &M, &K);
	for (int r = 0; r < R; ++r) {
		int c2 = 0;
		int c3 = 0;
		int c5 = 0;
		bool odd2 = false;
		for (int k = 0; k < K; ++k) {
			int v;
			scanf("%d", &v);
			int count2 = count(v, 2);
			odd2 =  odd2 || count2 % 2 != 0;
			c2 = max(c2, count2);
			c3 = max(c3, count(v, 3));
			c5 = max(c5, count(v, 5));
		}
		int all = c3 + c5 + c2 / 2;
		for (int i = 0; i < c3; ++i) {
			printf("3");
		}
		for (int i = 0; i < c5; ++i) {
			printf("5");
		}
		for (int i = 0; i < c2 / 2; ++i) {
			printf("4");
		}
		if (odd2) {
			printf("2");
			++all;
		}
		for (int i = all; i < N; ++i) {
			printf("2");
		}
		printf("\n");
	}
}

int main() {
	int T;
	scanf("%d", &T);
	for (int tc = 1; tc <= T; ++tc){
		printf("Case #%d:\n", tc);
		solve();
	}
}