- https://codeforces.com/contest/1085
- https://codeforces.com/contest/1086 (div1)
- https://codeforces.com/contest/1087 (div2)
問題番号はdiv1．
A. Connect Three
ある点から 3 点までのパスの和集合．座圧して定数個の候補を試す．
B. Minimum Diameter Tree
辺の長さは葉の近くにしかないとしてよいことが証明できます．中心から見て葉以外のところに辺重みがあればそれを深いところにうつすという議論をします．
C. Vasya and Templates
lcp(A,B) のところまでは S もこれらに一致させる必要があります．lcp のところは全文字探索してしまいます．lcp を超えると，まだ A と一致しているならば最大の文字， B と一致しているなら最小の文字を使うようにして割り当てていきます．これで候補 $O(K)$ 通りです．
D. Rock-Paper-Scissors Champion
グーで優勝可能な人数を数える．という類の問題を 3 回ときます．
グーで優勝可能な条件を考えます．自分の左側，右側だけで見て勝てるという条件に分解できます．
自分が列の左端だとします．
- 右側にチョキが居る場合：必ず勝てる．
- 自分，誰か，チョキ，誰か．という状態にしたあとのことを考察する．
- 右側がグーとパーだけからなる：パーが存在するならば勝てない，そうでなければ勝てます．
E. Beautiful Matrix
辞書順何番目かなので，prefix を固定したときの数え上げを考えます．すると，次の問題が出てきます：長さ $n$ の列 $A, B$ があって A, B それぞれは disjoint である．$A_i=B_j$ となる $(i,j)$ が $k$ 組あるとする．$B$ の順列で $A_i\neq B_i$ となるものを数えよ．まずはこの答を各 $(n,k)$ について求めておきます．例えば包除原理と畳み込みでできます．
各 prefix に対して次に今あるよりも小さい数を書いたとき数え上げ総数を考えます．これは直前の行で既に登場しているか否かによって値が変わるので，それに応じて足します．
F. Forest Fires
$f(t)$ を $t$ 秒後に被覆されている部分の面積とします．これは $O(N\log N)$ 時間で計算可能です（https://judge.yosupo.jp/problem/area_of_union_of_rectangles）．
一方 $f(t)$ を包除原理により求めることを考えると，いくつかの長方形の共通部分面積の足し引きとして $f(t)$ を表せます．共通部分は面積が正になってからは $2$ 次多項式です．よって $f(t)$ は何らかの区間ごとに $2$ 次以下の多項式です．
区間の切れ目が，$|x_i-x_j|/2$ などであることも上の導出から分かります．結局 $O(N^2)$ 個の区間に対して $2$ 次以下の多項式をつなげた関数になっています．
それぞれの区間では包除原理を用いない通常の計算を行って $3$ つの $t$ での値を求めてから多項式補間すれば，すべての $f(t)$ が $O(N^3\log N)$ 時間で手に入ります．
