AtCoder Beginner Contest 094

今回はABC094の参加記です。結果はA, B, C, Dの全完でした。
使用言語: C++

A - Cats and Dogs

A匹は猫なので、A≦X≦A+Bかを判定するだけ。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	int a, b, x;
	cin>>a>>b>>x;
	if(x>=a && x<=a+b) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}

B - Toll Gates

問題

左に移動し続けるか、右に移動し続けるかのどちらかの場合が最小コストになる。よってXより左側、右側のマスのコストの和のうち小さい方が答え。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	int n, m, x;
	int a[110];
	cin>>n>>m>>x;
	for(int i=0; i<m; i++) cin>>a[i];
	int cost1=0, cost2=0;
	for(int i=0; i<m; i++){
		if((a[i]-1)<x-1) cost1++;
		else const2++;
	}
	cout<<min(cost1, cost2)<<endl;
	return 0;
}

C - Many Medians

問題

$X$ をソートした数列を $Y$ とすると $X_i$ を除いたときの中央値は $Y_{\frac{N}{2}}$ または $Y_{\frac{N}{2}-1}$ である。
$Y_{\frac{N}{2}}$ が中央値となるのは $X_i$ ≦ $Y_{\frac{N}{2}-1}$ のとき。それ以外の場合、 $Y_{\frac{N}{2}-1}$ が中央値となる。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	int n;
	int x[210000];
	cin>>n;
	for(int i=0; i<n; i++) cin>>x[i];
	int y[210000];
	for(int i=0; i<n; i++) y[i]=x[i];
	sort(y, y+n);
	for(int i=0; i<n; i++){
		if(x[i]<=y[(n/2)-1]) cout<<y[n/2]<<endl;
		else cout<<y[(n/2)-1]<<endl;
	}
	return 0;
}

D - Binomial Coefficients

問題

n≦m $\Rightarrow$ comb(n, r)≦comb(m, r)なので $a_j$ を固定したとき $a_i$ は最大の $a$ である。一方、 $a_j$ は $\frac{a_i}{2}$ に最も近いものを選べば良い。コンテストでは急いでいたので変なコードを書いてしまった。
D問題にしては簡単すぎないか？と思って不安になりつつ提出したが無事AC。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	int n;
	int a[110000];
	cin>>n;
	for(int i=0; i<n; i++) cin>>a[i];
	sort(a, a+n);
	int ans1=a[n-1], ans2=0;
	for(int i=0; i<n; i++){
		if(min(ans1-ans2, ans1-(ans1-ans2))<min(ans1-a[i], ans1-(ans1-a[i]))) ans2=a[i];
	}
	cout<<ans1<<' '<<ans2<<endl;
	return 0;
}