naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Regular Contest 096

4/21(土) 21:00〜

2完でレート微減。お腹すいた。
f:id:n4_t:20180421235212p:plain

f:id:n4_t:20180421235223p:plain

C - Half and Half (300)

・A,BそれぞれをA,Bで買う
・A,Bの少ない方に合わせて(ABx2)を買って、多い方は個別に買う
・A,Bの多い方に合わせて(ABx2)を買って余らせる
の一番安いのが答え
→AC
https://beta.atcoder.jp/contests/arc096/submissions/2389683

D - Static Sushi (500) 部分点あり

・右回りに行って食い散らかして離脱
・左回りにちょっと行って食い散らかして戻ってきてから、右回りに行って食い散らかして離脱
・それらの逆
・何もせず離脱 (0)
の一番いいやつが答え、だけど

とりあえず位置でソートして
累積和を取って、そこから距離を引いたものを(右回りと左回りそれぞれ)用意。
累積和を取って、そこから距離x2を引いたものも(右回りと左回りそれぞれ)用意

離脱位置を固定して(O(N))、逆回りにちょっと行って食い散らかして戻って来る場合の最大利得を求める(O(?))。
O(NlogN)まで行ける、とか思って何も考えずにRMQ書いてた(O(NlogN))けど、単にmaxを累積していくだけ(O(N))で良かった。
→AC
https://beta.atcoder.jp/contests/arc096/submissions/2394935

E - Everything on It (900) 部分点あり

k種類の組み合わせからk+1種類を導き出す式が立てられるのかな、と思って考えたけど
3種類の場合の118通りってどうやれば出てくるのか(計算が合わない…)考えてるうちに終了

F - Sweet Alchemy

開いてない

教訓

O(NlogN) で間に合うからってそれが最善とは限らない(O(N) で解ける問題をわざわざO(NlogN)で解くな)