整数列{Ak}(0≦k＜n)および非負整数Pが与えられるとき、 不等式|A0-X|+|A1-X|+……+|An-1-X| を満たすXの個数を求めよ。 ただし1 数え上げでは時間切れになるので少し計算が必要。 Aをソートして、akan-1の場合、X=akの場合に分けて それぞれ加算という方針で。…

商品の価格のリストが与えられ、それらを全て１つずつ買うときに必要な枚数の合計を最小にするようにコインを発行する。ただし全てのコインの額面は、それより小さいコインの整数倍になっていなければならない。 このとき全ての品物を１つずつ買うのに必要な…

一問だけ解ければいいかなくらいの感じで参加してきました。 Easy 方程式f(x)=Σa_n x^n=Xの解を求める問題。(a_k=0or1で問題文中で与えられる）二分法で実装。 Medium 期待値の線形性を使う問題ぽいのでそんな感じで実装。分数をコーディング時に逆にしてて…

新しいほうからSRM440くらいまでのDiv2のEasy,Medium問題をだらだら解いた。 英語だと問題文の見落とし等が増えるのでどうにか工夫してかないと駄目ですね。 SRMの練習ならDiv1の過去問やれよって話ですが、 Div1の問題は勉強不足によりMediumすら歯が立ちま…

http://www.topcoder.com/stat?c=problem_statement&pm=10563&rd=13909 棒の集合から、長さt以上の棒をk本切り出せるか判定するのは O(n)でできるので、二分法を使えばO(n*log(Lmax))の時間で計算可能。 なんだけど、長さt以上の棒を切り出す数を数える変数…