Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Regular Contest 174

B のみ 1完

各問題

A - A Multiply

(C が正数の時)非負とそれ以外のものをまとめて、絶対値の小さい負数と大きい正数もまとめて、一番大きいところに C をかけるとよい、のような方針でやったんですが、テストケース半分くらい WA。

第一感は累積和だったんですが、それをどう使えばいいのか全く見当がつかなかった...。

B - Bought Review

平均が初手で3以上なら何もする必要がないので 0 を出力して終了です。

平均が3未満の時、星3以下をいくつ足しても平均が3以上になることはないので、4 と 5 をいくつ足せばよいかだけを考えればよいです。

星 5 だけを足すとしたとき、最低いくつ必要かは算数で求められます。あとは、0 から その最低必要数の間でもっとも費用が少ないものを探せばよいです。ここで(たぶん)「最適な状態から離れるほど費用が増える」が成り立つ(と思う)ので、二分探索的なことをすれば求めることができます。

まとめ

惨敗でまた緑落ち。そういえば 3 年ほど前にも、落ちて戻ってを 3 回繰り返したことがあったな...。いやでも今回かなり落ちたので次は青パフォくらいとらないと一発では戻れなさそうなんですが。