ARC095/ABC094 C, D

AtCoder Regular Contest 095, AtCoder Beginner Contest 094のC問題, D問題です。

C: Many Medians

まあまずこういうのってとりあえず数列をソートしますよね。ソートしたあとの数列とする前の数列を両方取っておきます。

まず頭に浮かぶこととして、
「１つぐらい数字を消しても、中央値の位置って大きくてもせいぜい１しかずれないよね」
ということがあります。
元の数列の長さは偶数なので、ソートした数列で真ん中の2つが中央値候補です。その候補たちの左側が消された場合は右側の候補が、逆に右側が消されたら左側の候補が答えになります。これは大小比較したらよいです。

あとは、中央値候補本人が消えた場合のことをちょっと考えてから実装してやります。
僕はここでなんか迷ってしまいました。ここでさっとクリアに見通せるようになりたい。

以下僕の汚いコードです。med1, med2が候補になってます。

▶ソースコード

int n;

std::vector<int> x;//生の数列
std::vector<int> v;//ソート後の数列

int main(){
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		int a;
		scanf("%d", &a);
		x.push_back(a);
	}
	v = x;//これがしたかったからvectorにした
	std::sort(v.begin(), v.end());
	int med1, med2;
	med1 = v[n/2-1];//こういうところで添え字に何が入るか
	med2 = v[n/2];//ってのもわりと慣れがいるところですよね
	for(int i = 0; i < n; i++){
		if(x[i] < med2){
			printf("%d\n", med2);
		}else{
			printf("%d\n", med1);
		}
	}
	return 0;
}

D: Binomial Coefficients

nCrのお話ですね。高校の数学Aでおなじみのやつ。結構時間を溶かしてしまいました。考えたことを事細かに書いていこうと思います。

はじめ、なんとなくcomb(n, r)のnは大きければ大きいほどいいんじゃないかなって考えました。実はこれは正しかったのですが、このときの僕は何を考えたのか
「いやいやcomb(12, 1)と(11, 5)なら(11, 5)のほうがでかいやんか」
とか考え始めました。今思えばこれが大失敗の元でした。
そのあとは迷走して、パスカルの三角形とか色々考えてましたが、ようやく気づきました。

「さっきcomb(12, 1)と(11, 5)で考えたけど、(11, 5)に5が使えるなら(12, 5)もつくれるやん」

そして、comb(n, r)とcomb(n+1, r)ならcomb(n+1, r)の方が大きいことを確かめました。rが同じ数ならnは大きい数の方がいいということになります。階乗で表現した式を考えれば簡単です。じゃあ、nは最大の数を使って良さそうです。

じゃあ、rは何がいいのでしょうか。ここでパスカルの三角形の出番です。

    1        
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

こういうやつです。nCrとの関係はご存知である前提で話を進めます。知らない人は調べてね。これを見ると、真ん中のほうの数字が大きいのがわかると思います。ここから、

rはn/2に近い方がよい

ことがわかります。じゃああとは簡単です。一番大きい数字を選んできて、あとはそれより小さい中でn/2に一番近いものを選んだら良いです。

実は僕はここでバグを産みました。ここで比べるべきは、rの候補とn/2との差ではなく、(rの候補)*2とnとを比べるべきだったのです。どういうことかというと、
例えばnが9で、rの候補に5と3があるとしましょう。9/2は4.5なので、このうちだと5の方が近いです。しかし、9/2は整数どうしの演算なのでコンピュータの内部では答えが4となり、実装によっては3も選ばれてしまう可能性がでてきてしまいます。
普段なら気をつけるのですが、なんだかややこしくって完全に忘れていました。恥ずかしい〜

ということで1WAでACです。

▶ソースコード

int n;
std::vector<int> a;

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		int b;
		scanf("%d", &b);
		a.push_back(b);
	}
	std::sort(a.begin(), a.end());
	int bas = a[n-1];
	int crit = 0;
	for(int i = 0; i < n-1; i++){
		if(a[i] < bas/2){
			crit = i;
		}else{
			break;
		}
	}
	if(std::abs(bas - a[crit]*2) <= std::abs(bas - a[crit+1]*2)){
		printf("%d %d\n", bas, a[crit]);
	}else{
		printf("%d %d\n", bas, a[crit+1]);
	}
	return 0;
}

感想とか

レートが下がりました！w
D問題でウジウジしてしまったのが原因ですね。E問題解けると良かったんですが、なかなかきつかったです。
まあ楽しかったので良しとします。次回はhighest出したいですね。