Codeforces Round #138 (Div. 2)

A

最初O(n^3)で書いてhackされてしまった。(O(n^3)のままですが、適当にbreakとかcontinueしてるので問題ないです)

ソース

int main(){
	int a[3];
	cin>>a[0]>>a[1]>>a[2];
	sort(a,a+3);
	for(int i = 1; i <= 10000; i++){
		if(a[0]%i||a[1]%i)continue;
		for(int j = i; j <= 10000; j++){
			if(j>a[0])break;
			if(a[0]!=i*j||a[2]%j)continue;
			for(int k = j; k <= 10000; k++){
				if(k>a[1])break;
				if(j*k==a[2]&&k*i==a[1]){
					cout<<4*(i+j+k)<<endl;
					return 0;
				}
			}
		}
	}
	return 0;
}

B

条件を満たすl,rを一つ出力すればいいらしい。最初少しバグがでて時間がかかった。

解法

適当にバグらないように尺取りする。

ソース

int a[100000],d[100001];

int main(){
	int n,k;
	cin>>n>>k;
	for(int i = 0; i < n; i++)cin>>a[i];
	int l = -1, r = -1;
	int x = 0,y = -1,s = 0;
	while(x<n){
		if(s<k&&y<n-1){
			y++;
			if(!d[a[y]])s++;
			d[a[y]]++;
		}else {
			d[a[x]]--;
			if(!d[a[x]])s--;
			x++;
		}
		if(s==k && (r==-1 || r-l>y-x)){
			l = x+1,r = y+1;
		}
		//cout<<s<<' '<<x<<' '<<y<<endl;
	}
	
	cout<<l<<' '<<r<<endl;
	return 0;
}

E

数列の和をk(<=10^9)回計算する。少しバグがでてsubmit間に合わなかった。
色々考察すると面白そうな問題だった。

解法

累積和を拡張すると、累乗の計算みたいな感じになるので、繰り返し二乗法で解ける(O(n^2 * log k)で遅いけど)。
array[] = {a,b,c,d,e}
f(n,array) = arrayに問題文の操作をn回行ったもの
とすると、
f(0,array) = {a,b,c,d,e}
f(1,array) = {a,a+b,a+b+c,a+b+c+d,a+b+c+d+e}
f(2,array) = {a,2a+b,3a+2b+c,4a+3b+2c+d,5a+4b+3c+2d+e}
f(3,array) = {a,3a+b,6a+3b+c,10a+6b+3c+d,15a+10b+6c+3d+e}
f(4,array) = {a,4a+b,10a+4b+c,20a+10b+4c+d,35a+20b+10c+4d+e}
...

無証明ですが、f(n+m,array) = f(n,f(m,array)) が成り立ちます。

全部計算する必要は無いので、必要なところだけ計算すれば良いです。(計算の仕方はソース内のmal()を見てください)
どうみても累乗の計算なので、配列の要素の個数をnとすると最初に書いたオーダーでf(k,array)を計算できます。

ソース

typedef long long ll;

ll a[2000],r[2000],t[2000];
int n;
const int mod = 1000000007;

void mal(ll* x, ll* y){
	memset(t,0,sizeof(t));
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= i; j++){
			t[i] = (t[i]+x[j]*y[i-j])%mod;
		}
	}
	for(int i = 0; i < n; i++){
		x[i] = t[i];
	}
}

int main(){
	int k;
	cin>>n>>k;
	for(int i = 0; i < n; i++)cin>>a[i];
	for(int i = 0; i < n; i++)r[i]++;
	
	for(;k;k>>=1){
		if(k&1)mal(a,r);
		mal(r,r);
	}
	cout<<a[0];
	for(int i = 1; i < n; i++){
		cout<<' '<<a[i];
	}
	cout<<endl;
	return 0;
}