TopCoder SRM 648

2015-02-02 | [Competitive programming]

250

K が最大になるのは A…AB…B みたいになっているとき (A, B はほぼ同じ数) である。 最初に A をたくさん置いておいて、残りの K を減らす方針で B を適当なところに入れて文字列を構成する。

550

N, K が小さければ、「今買うときの値段が最安なものを買う」を繰り返す greedy で解ける。

商品 1 を買う個数を求めたあと、次の商品 1 を買わない範囲でどの値段のものを買うかを求める。 ここで、その範囲では同じ商品を高々 1 個しか買わないことに注意すると、値段を決めればあと何個買えるかは簡単に計算できるので、 二分探索が使える。

850

OEIS を使っていろいろ調べて試したけど解けなかった

結果

challenge できない＞＜

250, 550 両方通った

240.60 + 312.62 = 553.22 (8 位)

rating: 2990 -> 3017 target 復帰!!