htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Beginner Contest 094

B - Toll Gates

Submission #2352431 - AtCoder Beginner Contest 094

問題文読むのがなんか辛かった……。解いてる時は普通にループ回す泥臭い方法しか思いつかなかったけど、制約厳しくてもAを二分探索して終わりじゃないか。制約変えてCで出てたらハマりそうだった。

C - Many Medians

Submission #2353068 - AtCoder Beginner Contest 094

Nが偶数で、各Xiを除いた中央値を求めるということは、求めるべき中央値は元の数列の真ん中2つのどちらかになり、各XiにおいてXi >= 元の数列の真ん中上の数なら小さい方の数、違うなら大きい方。

D - Binomial Coefficients

Submission #2354005 - AtCoder Beginner Contest 094

0 <= ai <= 10**9

の制約より組み合わせの公式で計算することは不可能。n! / r!(n-r)!なのでnは最大の数字を選ぶのが最適なことは明らか。rはできるだけ真ん中っぽいほうがいいだろうなーというのはわかるけど、rn-rの差が最小であれば階乗の積も最小になるかな?証明わかんないけど投げちゃえって投げて通ったけどよく考えなくても当たり前だな……。差が大きくなれば大きい方の階乗に大きい因数が増えるので。