ARC095 A問題 B問題

今日久しぶりにARCに出たので解法をメモしておきます。

ARC095 A問題

C - Many Medians
与えられた数列のうち、1つ抜いたときの中央値はいくつになるか計算する問題。
与えられた数列をまず昇順にソートし、中央値候補を2つ出す。
その後、抜く数字が中央値候補の1つ目以下であれば、2つ目が答え。
それ以外であれば、1つ目が解答になる。

#include <iostream>
#include <vector>
#include <algorithm>

#define lli long long int

using namespace std;

int main(){

	lli n;
	vector<lli> x;
	vector<lli> y;

	cin>>n;

	for(int i=0;i<n;i++){
		lli tmp;
		cin>>tmp;
		x.push_back(tmp);
		y.push_back(tmp);
	}
	sort(x.begin(),x.end());

	lli a = x.at(n/2-1);
	lli b = x.at(n/2);

	for(int i=0;i<n;i++){
		lli now = y.at(i);
		if(now<=a){
			cout<<b<<endl;
		}
		else{
			cout<<a<<endl;
		}
	}

	return 0;

}

ARC095 B問題

D - Binomial Coefficients
全列挙、もしくは計算をしようとしても与えられる値がでかすぎて計算が出来ない。(10^9!なんてしたらもう大変なことに。。)
組み合わせの計算方法として、n個の中からr個を選ぶ場合、rがn/2に近ければ近いほど値が大きくなることを利用する。
また、rが固定されていたとしても、nが大きければ大きいほど、組み合わせの数も大きくなることより、
nCrのnは与えられた数列の最大値、rは与えられた数列の中で最もn/2に近い値を選択する。

#include <iostream>
#include <vector>
#include <algorithm>

#define lli long long int

lli abs2(lli a){
	if(a>=0)return a;
	else return -a;
}

using namespace std;

int main(){

	int n;
	vector<lli> a;

	cin>>n;

	for(int i=0;i<n;i++){
		lli tmp;
		cin>>tmp;
		a.push_back(tmp);
	}

	sort(a.begin(),a.end());

	lli ans=0;
	lli max = a.at(n-1);
	lli center = max/2;
	for(int i=0;i<n;i++){
		if( abs2(center-ans) >= abs2(center-a.at(i))){
			if(a.at(i) != max){
				ans = a.at(i);
			}
		}
	}

	cout<<max<<" "<<ans<<endl;

	return 0;
}