A

はい

B

はい

C

与えられた列が framed かどうかの述語の特性関数 $\chi$ を使って、求める値は \(\sum _ {p \in \mathcal{S} _ n} \sum _ {\lbrack l, r \rbrack} \chi(p_l, p _ {l + 1}, \dots, p_r)\) と書ける。 内側の $\sum$ から先に考える。 後で $(r - l + 1)!$ を掛けることにして $p_l \lt p _ {l + 1} \lt \dots \lt p_r$ を仮定すれば $p _ {l + i} = p_l + i$ である。 よって $l$ の値と $r - l$ の値と $p_l$ の値が何通りかだけ考えればよい。 $O(N)$。

D

乱択

元々の問題は venue-sensitive な部分集合 $s$ の存在判定だが、これは $\vert s \vert = 2$ と仮定し対だけ考えれば十分。 A, B それぞれで overlap をする対の個数を数え、不一致なら明らかに venue-sensitive な対が存在する。 もちろん逆は言えない。 そこで乱択。 A, B の要素を適当にいくつか取り出して、それらに対して対の個数を数えることをする。 $k$ 回繰り返してすべて対の個数が一致していれば venue-sensitive な対は存在しないと見なす。 繰り返し回数 $k$ として計算量は $O(k \cdot N \log N)$。

ちゃんと通る乱択のはずだけどテストケースが弱いらしいので実は嘘かも？

セグ木

A をイベントソートし、各時刻 $t$ ごとに次をする: $X = \lbrace i \mid t \in \lbrack sa_i, ea_i \rbrack \rbrace$ として $\exists t’.~ \forall i \in X.~ t’ \in \lbrack sb_i, eb_i \rbrack$ を判定する。 そのような $t’$ がないなら venue-sensitive である。 これは座標圧縮して区間 add 区間 max のセグ木で可能。$O(N \log N)$。

リンク

  • https://codeforces.com/contest/1284

  • F, G は読んですらいないがちょっと気になる

  • https://ngtkana.hatenablog.com/entry/2020/01/04/235946