Codeforces #138 Div.2

コンテストページ : Cf#138 Div.2

結果 : ox-x- 1122th 1495 -> 1409 (-86)

感想 : これは笑う. Bは配列の要素が1つ少なくてWAしてしまった(絶望)
今回のセット頑張れば上位食い込めたのに色々こけてしまって残念...

解法 :

A. 平行六面体の, 3つの面の表面積が与えられたとき, 周長を求めなさい. という問題.
2つの辺をO(n^2)で決め打ちすると, もう一つの判定をO(1)で行える.

#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
	int p, q, r;
	scanf("%d %d %d", &p, &q, &r);
	
	int ans = 0;
	for (int i = 1; i <= 10000; i++){
		for (int j = 1; j <= 10000; j++){
			if (i * j == p && q / j == r / i){
				ans = i + j + q / j;
			}
		}
	}
	
	
	printf("%d\n", ans * 4);
	
	return (0);
}

B. なんか変な尺取りする問題でした. 尺取するだけですが, バケットのサイズが1足りなくてWAしてました. (これは修正後のコードです.)

#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
	int n, k;
	int a[100000], bucket[100001];
	int head, tail;
	int num;
	
	scanf("%d %d", &n, &k);
	
	for (int i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}
	
	memset(bucket, 0, sizeof(bucket));
	head = tail = 0;
	bucket[a[head]]++;
	num = 1;
	
	while (num != k && head != n - 1){
		num += !bucket[a[head + 1]];
		bucket[a[head + 1]]++;
		head++;
	}
	if (num != k){
		printf("-1 -1\n");
		return (0);
	}
	while (bucket[a[tail]] > 1){
		bucket[a[tail++]]--;
	}
	
	printf("%d %d\n", tail + 1, head + 1);
	
	return (0);
}

E.
配列の累積和をk (<= 10^9)回取る問題でした.
各要素はk回足した後に Σ[i = k - 1, k + n - 1] iC(i - (k - 1)) * a[i - (k - 1)] になるので, これを求めてやれば良いです.

#include <cstdio>
#include <cstring>
#include <algorithm>

#define MOD (1000000007)

using namespace std;

typedef __int64 ll;

ll perm[4001];
ll bper[4001];

ll modPow(ll a, ll k)
{
	ll t = a;
	ll r = 1;
	
	while (k){
		if (k & 1){
			r *= t;
			r %= MOD;
		}
		t *= t;
		t %= MOD;
		k >>= 1;
	}
	
	return (r);
}

bool f;

int main(void)
{
	ll a[2000], s[2000];
	ll comb[2000];
	int n, k;
	
	scanf("%d %d", &n, &k);
	
	for (int i = 0; i < n; i++){
		scanf("%I64d", &a[i]);
		s[i] = 0;
	}
	
	if (k){
		
		perm[0] = 1;
		for (int i = 1; i <= 4000; i++) perm[i] = i * perm[i - 1] % MOD;
		
		comb[0] = 1;
		for (int i = 1; i < 2000; i++) comb[i] = (k + i - 1) * comb[i - 1] % MOD * modPow(i, MOD - 2) % MOD;
		
		for (int i = 0; i < n; i++){
			for (int j = i; j >= 0; j--){
				s[i] = (s[i] + comb[j] * a[i - j] % MOD) % MOD;
			}
		}
		
		for (int i = 0; i < n; i++){
			printf("%I64d%c", s[i], i == n - 1 ? '\n' : ' ');
		}
	}
	else {
		for (int i = 0; i < n; i++){
			printf("%I64d%c", a[i], i == n - 1 ? '\n' : ' ');
		}
	}
	
	return (0);
}

oo-xoくらいを目指したかったなー. 次があるし次がんばります!