AtCoder Beginner Contest 140 - gratan’s diary

jsc2019で久しぶりにキョウプロしました

ABを早く解くことができて割と順位はよかったです。

でもC~は手も足も出ず精進不足を感じました。気が向いたときにやっていこうと思います。

今回はサボってた時期のコンテストを解きました。

やるだけ。ひっかけかと思ったけど大丈夫でした

各料理を1回ずつ食べることに気づけばやるだけです。これもひっかけじゃなくてよかったです

逆に求めます。Ai=min(Bi-1,Bi)をやるだけです。端に気を付ければよいです

問題：N人が東西どちらかを向いて並んでいる。以下の操作をk回行い「前の人が自分と同じ方向を向いている」人を最大化せよ

操作：区間[l,r]の人の順番を入れ替え、向いている方向を逆転する。

考察：

LRLRLRと同じ方向を向いている人々をグループ化します

そうしたとき、複数グループを反転させる意味がないことがわかります。

したがって、どこかのグループを反転させることになります。

各グループ幸せでない人は1人です。またどのグループを反転させても幸せな人は2人増えます。

したがってn-(グループの数)+2*kが答えとなります

最大でもn-1人までなことに注意しましょう

問題：順列Pを考える。すべての長さ２以上の連続する部分列について、2番目に大きい数の和を取れ。

考察：

典型です。ある数字ｉについて、これが2番目に大きくなるような区間を考えます。

i<jなるｊが下のように位置し、indexをa,b,x,c,dとします

ｊ　ｊ　ｉ　ｊ　ｊ

ａ　ｂ　ｘ　ｃ　ｄ

こうすればO(1)でｉによる寄与がわかります

multisetで上からindexを追加していけばO(NlogN）で解くことができます

問題：スライムを集合Sに一致させよ

考察：上から貪欲でよいです。multisetでO(MlogM)で解けます(M=2^N)