N冊の本の中からK冊本を売る。 各本には値段とジャンルが決まっていて、同じジャンルの本を多く売るとボーナスが入るので、利益の最大値を求めようという問題。 まず、任意のジャンルに関して、高いものから売ればより高くなることはすぐにわかるのでソート…

N本のつららがあり、左右に自分より長いつららがなければ伸びていく。 長さがLを越えると折れてしまうので、全部折れるまでにどれだけかかるかな？という問題。 毎秒シミュレートしては間に合わないので他の方法を取る必要がある。 まず、最初の段階で伸びる…

円上にN個のピザ屋とM個の家があり、各家からの最も近いピザ屋までの距離の総和を求める問題。 愚直にやるとO(NM)で想定解法ではなさそうなので(10^9なので今は通るかもしれない) 二分探索をして各家がどのピザ屋とどのピザ屋の間にあるか調べる。 二分探索…

N種類の得点が得られるダーツ板に4本ダーツを投げてM点以下という制約のもと最大で何点得られるかな？という問題。 投げないという選択肢が与えられていることに注意しつつ、半分全列挙を使いO(N^2)で解ける。 難易度は6程度であるように感じられた。 http:/…