問題はこちら
問題概要
的に個の数字が書いてあり, 矢を
つまで投げることができる. 矢が当たった数字の和を
以下での最大値を求めよ.
思考の流れ
個数制限なしナップサック問題っぽいがであるので間に合わない.
つ投げるっていうのが怪しい. 矢の当たった数字を順に
とおくと,
になればよい.
が成り立つので2つ投げた時にあり得る得点の集合
を求める. 同じ数字をえらんでもいいので
と
が取りうる値の集合はどちらも
.
の数字を昇順に並べると,
のある要素
に対して
となる最大の
の要素
は二分探索で見つけることができる.
のすべての要素
に対してこのような
を見つけたときの
の最大値が答えとなる.
提出プログラム
https://atcoder.jp/contests/joi2008ho/submissions/12016002
感想
解法を思い付くのに時間がかかった.
