Educational Codeforces Round 60

スポンサーリンク

A. Best Subsegment

最大平均は $\max A$ で,長さ 1 の場合に実現できます. $\max A$ からなる最長 subarray を求めればよいです.

B. Emotes

大きい方から 2 種しか使わないとしてよいです.

C. Magic Ship

$t$ 秒で目標達成可能ならば $t+1$ 秒でも可能です.よって二分探索するのが簡単です.

D. Magic Gems

$\sum_k (x+x^M)^k=\dfrac{1}{1-x-x^M}$ の係数.

E. Decypher the String

インデックスの $26$ 進法での $0, 1, 2$ 桁目を文字としてクエリすると,変換後の各文字がどこから来ているかが分かります.長さ $26^3$ まで対応可.

F. Crisp String

残る文字集合として可能なものを列挙できればよいです.

隣接が許可されない文字 a, b の 2 種を固定して,これを残せる文字集合に反映させます.間にある文字集合を見ると,残る文字集合としてある集合の部分集合が禁止されるという形になるので,禁止集合の極大なものを入れておいて部分集合側に伝搬させます.

G. Recursive Queries

$p$ の cartesian tree を作っておくと,$f(l,r)$ は cartesian tree の各ノードの区間 $[a_i,b_i)$ として $\sum_i |[l,r)\cap [a_i,b_i)|$ というように表せます.

$[l,r)$ を平面上の点 $(l,r)$ と見なすと,適当な長方形領域内の点に適当な $l,r$ の 1 次式を足す形になります.よって,$1$ 次式を足すのは $l$ の係数や $r$ の係数を足せばよいです.よって長方形加算,点取得のクエリになります.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました