ARC #004 - Particle

A.
全点間で距離を求めて、それらの最大値を出力する。
ans を 0 で初期化するのを忘れていて2WAしました。

int n,x[100],y[100];

int main(){
	double ans=0;
	cin>>n;
	for(int i = 0; i < n; i++)cin>>x[i]>>y[i];
	
	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n; j++){
			int dx = x[i]-x[j],dy = y[i]-y[j];
			ans = max(ans,sqrt((double)(dx*dx+dy*dy)));
		}
	}
	
	printf("%0.6f\n",ans);
	
	return 0;
}

B.
最大値:全部足す。
最小値:max(0,(一番長い辺の長さ)-(その他の辺の長さの合計)) を計算する。

(一番長い辺の長さ)<=(その他の辺の長さの合計)になるときは、折り曲げて距離を0にできる。
(一番長い辺の長さ)>(その他の辺の長さの合計)になるときは、一番長い辺の両端から、全て内側に向ければ、距離が最小になる。

int n,sum,d[500];

int main(){
	cin>>n;
	for(int i = 0; i < n; i++)cin>>d[i];
	
	for(int i = 0; i < n; i++)sum += d[i];
	
	sort(d,d+n);
	int M = d[n-1];
	
	for(int i = 0; i < n-1; i++)M -= d[i];
	M = max(0,M);
	
	cout<<sum<<'\n'<<M<<endl;
	return 0;
}

C.
N = kのとき、
(k+1)/2 - 1 <= X/Y <= (k+1)/2 - 1/k
⇒ k-1 <= 2 * X/Y <= k
⇔ 2 * X/Y <= k <= 2 * X/Y + 1

で、Nの値を求めて、N(N+1)/2-N(X/Y) = M として計算する。(この時、オーバーフローしないように注意する)
1<=M<=N で無ければ、不適なので、飛ばす。

typedef long long ll;

ll X,Y;

ll gcd(ll A,ll B){
	if(B==0)return A;
	return gcd(B,A%B);
}

int main(){
	char c;
	bool f = false;
	scanf("%lld%c%lld",&X,&c,&Y);
	ll g = gcd(X,Y);
	X /= g;
	Y /= g;
	ll N = ceil(X*2/Y);
	
	for(int i = 0; i < 2; i++){
		N += i;
		if((N%Y)||N<=0)continue;//NがYで割り切れなくなるような整数Mは存在しない
		ll S = N*(N+1)/2;
		ll A = N/Y*X;
		ll M = S-A;
		if(1<=M<=N){
			f = true;
			cout<<N<<" "<<M<<endl;
		}
	}
	if(!f)cout<<"Impossible"<<endl;
	return 0;
}

D.
Nを正に直し忘れてたのと、Combinationの計算でdp[100100][100100]にしてMLEしていたので、本番では解けませんでした。。。

素因数分解して、重複組み合わせを計算して、途中が負であるものを考える。
数字がM個あるので、最初の(M-1)個の数字の積の正負はどちらでも良いので、2^(M-1)を最後に掛ける。

typedef long long ll;

int N,M,dp[100100][40];
vector<int> D;

const int MOD = 1000000007;

int main(){
	//Combinationの計算
	dp[0][0] = 1;
	for(int i = 0; i < 100100; i++)dp[i][0]=1;
	for(int i = 0; i < 40; i++)dp[0][i]=1;
	for(int i = 1; i < 100100; i++){
		for(int j = 1; j < 40; j++){
			dp[i][j] = (dp[i-1][j]+dp[i][j-1])%MOD;
		}
	}
	
	ll ans = 1;
	cin>>N>>M;
	//素因数分解しやすくするために、予め正に直しておく
	if(N<0)N*=-1;
	
	{
		//素因数分解して、素因数の個数をそれぞれ求める。
		int N2 = N;
		for(int i = 2; i*i<= N; i++){
			if(!(N2%i)){
				D.push_back(0);
				while(!(N2%i)){
					N2 /= i;
					++D.back();
				}
			}
		}
		if(N2!=1)D.push_back(1);
	}
	
	//各々の素因数に対して、重複組み合わせの計算をする
	for(int i = 0,l = D.size(); i < l; i++){
		int n = D[i];
		int t = dp[M-1][n];//(M)_H_(n) = (M+n-1)_C_(n) = dp[M-1][n]
		ans = (ans*t) % MOD;
	}
	
	//(M-1)個の数字の正負を考える
	for(int i = 0; i < M-1; i++){
		ans = 2*ans%MOD;
	}
	
	cout<<ans<<endl;
	return 0;
}

35thでした