c問題、D問題共に解けたhttps://atcoder.jp/contests/abc094/tasks
C問題
方針
はじめは、与えられて数列をlistなどにコピーし、i番目の要素を削除しソートして、(l+1)/2番目の要素を取り出そうとしたが、ソートの計算量がnlognのため、要素すべてについて一つ一つ要素を決してソートしてをすると計算量が(配列の長さ*ソート)=(n*nlogn)となってしまい間に合わない。ここで、中央値についてよく考えると、中央値は2通りくらいにしか動かないことがわかる。これは、中央値より大きい値が削除された時は中央値が一個小さい要素に代わるということ以外に中央値は動かないからである。よって削除される値と元々の中央値を比較することで中央値がそのままか動くのか判断すれば定数で中央値を求められるので、結局計算量はO(N)で答えを求められる。
D問題
方針
comb(l,r)と考えると、combの性質から明らかに、lが大きい方がcomb(l,r)は大きくなるのがわかる。また、rはl/2に近い方がcomb(l.r)が大きくなるのがわかる。よって、a[i]の中から最大の値をlとし、二分探索で、l/2に近い値を見つけ、rとすれば良い。