この問題を解きました。苦労したので振り返っておこうと思います。
ネタバレをふんだんに含むのでご注意ください。
コンテストには参加していなくて過去問として挑戦しました。 この記事を書いている2019年12月7日時点での僕のAtCoderのスコアは804(緑色の下のほう)です。
解説を見てACしましたが、それでも一週間近く掛かりました。他の人の提出コードは見ないようにしました。
考え方は解説にある通りですが、「宝石を左側または右側から取り出して、最後に全部いらないものをキューに戻す」という発想に至るのは難しくなくて、ここまでは解説を見ずに到達できました。が難しかったのはそのあとでした。
いらない宝石を捨てる場合は手数を一個消費することになるので、手数をT、捨てる数をSとすると T-S個の宝石をキューから取り出すと考えることができます。
宝石の数Nよりも手数Kのほうが多いケースがあるので、宝石を取り出す最大の数は min(N, K)になります。 min(N, K)をHとすると
for(int i=0; i<H; i++){
// i個の宝石を捨てることができる、つまりN-i個の宝石を取り出す
}
のようにイテレートして、1個捨てる場合の最大の価値はA, 2個捨てる場合の最大の価値はB...のようにしていくと最終的に答えが出せそうです。
次にforの中で以下のように左から取り出す数と右から取り出す数をひとつずつ決めながら全パターン試します。
for(int i=0; i<H; i++){
H-i個の宝石を取り出す
for(int j=0; j<=取り出す数; j++){
右からj個、左から取り出す数-j個
}
}
左からN-0個、右から0個、
左からN-1個、右から1個、
...
左からN-N個、右からN個
という感じです。
ここも一回のイテレートで済むので、ここまででO(N2)です。
書き忘れていましたが 1 <= N <= 100です。
つぎに捨てる宝石の決め方ですが、0以上のものについては捨てる必要がないので、負の価値を持つ宝石を、絶対値が大きい順に捨てていくのが最適だと言えます。
「絶対値が大きい順に捨てていく」というワードでピンと来るかもしれませんが、優先度付きキューが使えそうです。
ヒープを使ってデータを管理することで、値が大きい順または小さい順に値を取り出すことができます。 データを取り出す（かつ削除する）場合、データを格納する場合、ともにO(log N)です。
for(int i=0; i<H; i++){
H-i個の宝石を取り出す
for(int j=0; j<=取り出す数; j++){
右からj個の要素を一個ずつ見て、負の数ならpriority queueに突っ込む
左から取り出す数-j個の要素を一個ずつ見て、負の数ならpriority queueに突っ込む
while(残手数が残っているまたはpriority queueが空でない){
priority queueから取り出して、現在持っている価値から引く
}
}
}
のようにすることで答えを求めることができます。
こうやって書くとあんまり難しそうに見えないんですが確かに難しかったんですよね。うーん...?
