ABC332に出た。

A: やるだけ。金額はintに入る。

B: 問題文の通りに実装する。

C: 連続して予定のある全ての区間について、その全体日数とイベントに出る日数を数え、それぞれ全区間におけるmaxをとる。要件としては

• 最大日数分のTシャツ
• イベントに出る最大日数分のロゴTシャツ

であり、また最初の時点でM枚の普通のTシャツはあるので、整理すると max(0, 最大日数-最大イベント日数-M)+最大イベント日数 になる。

D: HとWが小さいので、行と列それぞれ順列を総当たりするのが筋が良さそうだと分かる。「頭のいい」やり方もあるのだろうか？

E: 解けず。区別できる物体を分けるような問題難しい。

F: 区間に何かする時点で双対セグ木か遅延セグ木を使うと分かる。双対セグ木で十分だったのだが手が滑って遅延セグ木を出してしまった。

ある要素について、期待値$x$であるところが確率$p$で値$y$に遷移するとすると、期待値は$x(1-p)+py$に変化する。ということで、x→ax+bとする作用素(a,b)を考え、(a,b)=(1-p,py)とすればよいことが分かる。各クエリについてこの作用素を$p=1/(R_i-L_i+1),y=X_i$として$[L,R]$に適用すればよい。

自信が無かったので確率$p_i$で値$x_i$になる場合を考えると期待値は$p_1{x}_1+p_2{x}_2+\dots$になって…みたいな考察から始めてるのはナイショ。最初から「この遷移考えるとただの一次関数だよねー」と出来れば良かったのに…