| 
いろいろ考えたところ、貪欲法でいけそうとなったのでやってみたらうまくいった。
満足度が高い順に、消費期限の日から遡って飲む予定をできるだけいれて行く。すでに予定が入っている日はスキップする。
(なぜなら既に入っているコーヒーの満足度は入れようとしているものより満足度が同じか高いから。)
以上をやればいいが、largeの日数は単純にループで回してたら終わらないくらい多いので、連続する予定を日数に関係ないオーダーで記録する工夫が必要となる。
具体的には、空いてる日を「開始日と長さのリスト」で管理するようにして、そこに予定をまとまて入れるようにする。
空きリストが[(1,5)]なら1日目から5日分空いてるという状態。そこに4日目から前方向に2日分予定を入れると空きリストは[(1,2),(5,1)]となる。
一般的にはリストを後ろから見ていき、置けるところに置いてリストを更新していけばいい。オーダーはリストの長さになる。
1回の予定挿入でリストの要素数は高々1個増えるだけなので、リストの要素数は最大でもコーヒーの種類数程度。なので日数が1e18とかでも現実的な時間で計算できる。
予定を入れられた分だけ満足度を加算していって、全種類入れ終わったらそれが答え。
| 
ふつうにやると large の計算が終わらないので、なんか法則性があってO(N)にならないような方法があるんだろう
→とりあえずビットが全部たってる2**n-1とそれ以外で分けたらいいんじゃね？......という予想をしつつも証明できないのでまずはsmallをふつうにやる。
smallが通ったら、N以下の最大の2**n-1と残りでわけたときの合計ビット数を求めてみて、通った答えと一致してることを確認
→でdiffしたらおなじだったのでそれでlarge提出。なんとも危なっかしいやり方だけどまあいいや(笑)
証明は「2**n-1で分けるのが最適でない場合、ビットが全部立ってるとこから残りの方に移すとビットがもっと増えるはずだがそうはならない」みたいな感じでできそう。
立ってるビットを減らして他方にもってきたときに他方で2以上増えないといけないけど、0だったとこにもってきても1になるだけで合計は変わらないし、1だったとこにもってくると0になって良くて繰り上がって1になっても変わらないし繰り上がり方によってはどんどん減る方向にしかいかないので当初の分け方が最大。みたいな感じでしょうか。
