CSA #71 (Div. 2 only)

迷路 @pazzle1230

44位でDiv2だし爆上げ期待してますが

迷路 @pazzle1230

解説みたいけどもう出てますか

satanic@研究💪 @satanic0258

CSA A:s[i]==s[i+1]=='A'のときだけ出力しない B:{a[i][j],i,j}をpriority_queueに入れて順に試していく C:mapに累積和入れるやつ,最大と最小を更新していく D(WAだね):最大値を[max(A)-log(max(A)),max(A)]くらい調べれば十分,あとはその最大値以外を最大値の個数以下にする個数をカウントしてminとる

迷路 @pazzle1230

というか最初にDがBの位置にあったせいで1時間とかしたため（解けたからまだ良かったけど

daisyo @dsytk7

C通せた。これ解けなかったの悲しい感じだ

迷路 @pazzle1230

そういえばtouristって動的配点（？）嫌いなんじゃなかったっけ（前にWriterやってた気がするけど

satanic@研究💪 @satanic0258

えーコンテスト中WAだったやつ1ケースだけWAだったのか

迷路 @pazzle1230

Congratulations! Your rating has increased by 95 points . Keep it up!

有為 @uwitenpen

Dで途中から無限に増えていくのの判定が甘くて死んでた

迷路 @pazzle1230

三桁行ってほしかった

有為 @uwitenpen

結構でかいケースじゃないと反例出てこなくてつらかった

迷路 @pazzle1230

C、ARC−Bで出てきてもおかしくないと思ったし割と良問だと思ったけどそんな難しくないのかなぁ

satanic@研究💪 @satanic0258

Cみたいなやつ，累積和mapって個人的に呼んでいて，これまでこどふぉで3,4回見かけている

satanic@研究💪 @satanic0258

違う問題だからアレだけどこの記事(satanic0258.hatenablog.com/entry/2017/03/…)のC問題のところで累積和mapについて書いてた

satanic@研究💪 @satanic0258

もうちょっと一般的にどういう状況で使えるか整理したいね

nmnmnmnmnmnmnm @enuemuenuemuenu

TC:青。CF:青。AC:青。CSA:青。なので青以外の何者でもないなぁ。

nmnmnmnmnmnmnm @enuemuenuemuenu

CSAの問題悪くないよね。

satanic@研究💪 @satanic0258

累積和mapで全連続部分列で和がxになる個数とか今回みたいな和のmax/minとかがO(NlogN)でサッとわかるね

satanic@研究💪 @satanic0258

まぁ他にもやり方はたくさんあるだろうけど個人的にこういう問題はコレ！という定着をしています✋

satanic@研究💪 @satanic0258

D書き直したら通ったね

satanic@研究💪 @satanic0258

E，コンテスト中は自明O(N^4)を書いて終わってしまった