CSA #75

satanic@研究💪 @satanic0258

CSAおつでした

beet @beet_aizu

Modulo Queries、セグ木を1000本作ってk>1000の時はRangeCountTree上の二分探索をした（意味不明（986 ms csacademy.com/submission/148…

kmjp @kmjp_pc

Eで時間かかりすぎてFに時間を残せなかった…。

satanic@研究💪 @satanic0258

ABCDE5完！

有為 @uwitenpen

C,Dで普通に書いてTLEしたときかなり萎えた

よすぽ @yosupot

NFTがライブラリにないのヤバくない？ヤバイね

迷路 @pazzle1230

は〜beetさんに勝てる数少ない機会だと思ったのに

はむこ @hamko_intel

75th/3654 (Educational Codeforces Round 41 (Rated for Div. 2))

迷路 @pazzle1230

F、このmodは前にpulmnさんが言ってたやつだ（察し）となってまあすぐに諦めましたが

satanic@研究💪 @satanic0258

F,modが意味するようにそのままNTTできそうだったけどな

agw @masashinakata

Cが全く意味不明で酸欠になりそうだったけど、D解けてよかった。基本的には尺取り + std::setでやったんだけど、こういう相当ネチっこい尺取りが解けたのはかなり嬉しい♫

HIR180 @HIR180

CSA3位、かなり調子良かったけどEがちゃんと解けなかったので反省 (ごり押した)

はむこ @hamko_intel

なんか80位1000位2000位1000位80位みたいなパフォーマンス出すのが得意で、平均する青下位になる

有為 @uwitenpen

Fは超簡単で、P[y]=tと決め打つと、[(t-1)/2](t-2)!/(t-2-(y-1))!*(n-y-1)!になって、[(t-1)/2](t-2)!たちと1/1!,1/2!,..たちを畳み込みするとすべてのyについて求まる

beet @beet_aizu

Eのオーダー、BをバケットサイズとしてO(NB + Q(logN + log^2N log K A/B))

HIR180 @HIR180

Fは式を見ると、はい。

beet @beet_aizu

E、オーダーが一番汚い自信があるぞ

satanic@研究💪 @satanic0258

CSA A:1秒ごとにシミュレーション B:自分の行き先の結果をもらうメモ化再帰 C:(d,v,i)と(d,v-y,i)の2列をそれぞれ時間順(分母は払う)でソートし,前者へ(d,v+x,i)を挿入する位置p1,後者へ(d,v,i)を挿入する位置p2をそれぞれにぶたんしmin(p1,p2)を答える (→)

HIR180 @HIR180

Eみたいなの人よりlogを1つ多くつけてTLEすることが多すぎて良くないね

迷路 @pazzle1230

D、priority_queueなのか（適当にsetでやったため

satanic@研究💪 @satanic0258

(→) D:pairを持つ2つの昇順priority_queue(時間,i),(i,残り充電量)を用意し,現在時刻から(今見てる車の残り充電量),(次に来る車まで時間)の小さい方の操作をする E:マージソートの過程を残しておいて,B=300くらいでk<Bのときは各kでの記録をメモしRMQ,k>=Bのときは被覆する各列でkの倍数をにぶたん

beet @beet_aizu

レート微妙だなあ（いきれなくなるの嫌やが

satanic@研究💪 @satanic0258

Eの説明雑にしすぎた

有為 @uwitenpen

E, ブロックに分けて、ブロックごとに1~40000であまりとったときの最大値が分かればよく、1~200は普通にやって、残りは200個のポインタを動かしてO(n√(nlog n))くらい (ひどい)

beet @beet_aizu

あーlog一個取れるじゃん