1/31 日記
もう1月も終わるのか、はやいなあ
エキサイティングな毎日を送りたい。。。
・E - Magical Ornament (atcoder.jp)
昨日解けなかった問題。TSPであることが分かれば考察要素はほぼない（bfsを使うとCiどうしの距離がスマートに求められる）。
なんで解けなかったのか、TSPの理解が不十分だったのかも（最初に最小全域木と勘違いしてしまった後、TSPが頭の中に介入してこなかった。制約をきちんと観察することと、考察の第一手を間違えたときにどう仕切り直すかを考えたい。）
これはほぼ一緒の問題。
少し手こずった。期待値の問題。
サイコロの目の数は6*N個で、普通に再帰をするとO(N^2)で定数倍が重くてTLEする。
ここで、今出た目をNumとしたとき、どのサイコロを振るのが一番期待値が高いのかを高速に求めたいと考える（普通にやれば6*N通り試す必要がある）。各サイコロについて、次に有効になるサイコロの目はNumより大きいので、Numより大きい目の期待値の累積和を取り、それらをsetで管理するとO(logN)で次に振るべきサイコロとその期待値を求めることができる。
制約がちょっと謎だった。W=10^9は実行時間制限が4 secだからなんとか間に合う。
ただ、imos法をやろうとするとメモリが足りなくなる。よって、各石の（位置、コスト）の情報を配列に保持し、その石の位置に来た時に処理すればいい。
平均最大化の問題（蟻本にもある）。問題として解くのは初めてかも。
ある平均値xが達成可能であるとしたとき、選択したモンスターの集合をSとして
( ∑( i ∈ S) Bi ) / ( ∑ (i ∈ S ) Ai ) ≧ x が成り立ち、
∑ ( i ∈ S ) ( Bi - Ai * x ) ≧ 0 が成り立つ。
よって、Bi - Ai * x でソートし、大きい方から5個取ったときの総和が0以上ならok、0未満なら ng 、という感じに x を二分探索していけばいい。
推しは偉大。
