解説チラ見したら2^Nって書いてて終了

残りを見た

A 111の倍数ならYes

B 全部試す

C これratedで出てたら間違いなく死んでた
折れずに残っているものがあるとすると、AのmaxがLの候補
全部折れているとすると、Aのmaxとminの和がLの候補
で、実は候補はこれだけっぽい

F 「中央値を固定したときの判定問題 解いて」「わ わかんないっピ…」

F 「Nで割った余り」と「最後に決めた下位桁」のペアで遷移元を保持しながらBFSして、なるべく早く余り=0になったペアから遷移元を逆走すればいいと思ったんだけどTLE+WA

ABC442 oooooox

F 「どの行まで塗り分けを決めたか」「現時点で白は左から何列目までか」をキーに持って一旦DPを書くとO(N^3)になってアンハッピー
ここで「現時点で白は左から何列目までか」を配るDPではなく貰うDPで考え直すと、貰う元を降順に累積していけば良さそうなので、書き直すとO(N^2)になってハッピー

G 重さ3のアイテムの個数を決め打ちして三分探索か…？と思ったけどまとめきれず

E めっちゃ大変
点の位置をx軸・y軸・象限に従って8グループに分類し、時計回りにグループを横断しながらカウントしていく
軸上のグループは個数そのままでOK
象限上のグループは有理数x/yを考えると時計回りに昇順で管理できて、個数が二分探索できるようになる
モンスターAjとBjが同じグループなのに時計回りでは反対になるケースとかは、グループの横断開始とかをフラグに持って気合いで頑張る

配達員さんクソ寒い中ありがとう

おかえり1600💢

その上で、ある1つの商品iについて以下をそれぞれ考えて、本来の最大価値を実現できるか調べる
選ぶ場合→(①と②を合わせてM-P[i]円以下での最大価値)+V[i]
選ばない場合→(①と②を合わせてM円以下での最大価値)
ただし「①と②を合わせて」は愚直に判定するとO(M^2)で厳しいので、②の方は「◯円になる最大価値」を「◯円以下になる最大価値」としてまとめておく
(N*Mの配列を3つ使ったらMLEだったので、渋々2つにした)

D 22:15頃に順位表を見たら全人類通してたので仕方なく考え直すと、(出次数)^(経路の長さ)=4^10なんだからDFSで良くないか、と我に帰り、AC

F ある1つの商品iについて、それを選ぶ場合or選ばない場合を調べたい
そのためには商品i以外の選び方は最適化しておく必要があるので、商品1,2,...,Nを商品iを境目に分割するイメージを考えると、以下の情報があれば良さそう
①商品1,2,...,Nの順で選び方を決めるDP
②商品N,...,2,1の順で選び方を決めるDP

E (Aの個数)-(Bの個数)を考えたいので、まず(A,B,C)を(1,-1,0)に置き換えて累積和Dを取ると、部分文字列[l,r)における(Aの個数)-(Bの個数)がD[r]-D[l]で計算できる
条件はD[r]-D[l]>0ということなので、rの昇順にD[l]<D[r]となるlの個数を調べればよく、これはセグ木(と座標圧縮らしきもの)で求められる