- https://codeforces.com/contest/1259 (Technocup 2020 – Elimination Round 4)
- https://codeforces.com/contest/1276 (div1)
- https://codeforces.com/contest/1277 (div2)
A. As Simple as One and Two
ある文字まで残すかどうかを決めたときの状態は，「o」「on」「t」「tw」「なし」としてよいです．この 5 状態で dp をして復元します．
B. Two Fairs
$a$ を除いたときの連結成分分解，$b$ を除いたときの連結成分分解を求めておけばよいです．
C. Beautiful Rectangle
$H\leq W$ として $H\times W$ の長方形を埋められる多重集合がどのようなものかを考えます．同じ数は $H$ 個までしか使えません．この必要条件は十分条件にもなります．個数の大きい方から対角に埋めていけば OK です．
| 0 | 4 | 8 | 12 | 16 |
| 17 | 1 | 5 | 9 | 13 |
| 14 | 18 | 2 | 6 | 10 |
| 11 | 15 | 19 | 3 | 7 |
$H$ 個ずつ埋める間はひとつの斜め線を上から下に埋めていくだけなので大丈夫で，$H-1$ 個以下になると $2$ つの斜め線にまたがるパターンも出てきますがこれも $H-1$ 以下なので大丈夫です．
D. Tree Elimination
気合木dpで．各 subtree と親を結ぶ辺について「その辺を操作する時点で親が残っている・いない」「その辺を操作する時点で子が残っているいない」「その辺の操作で親を消すかどうか」「その辺の操作で子を消すかどうか」等を状態として木dpの計算です．
E. Four Stones
$d = \gcd(a_2-a_1,a_3-a_2,a_4-a_3)$ とすると，$a_i$ は $\pmod{2d}$ で一定です．この不変量のもと全部作れるというのが結論になります．操作は可逆なので，$0\leq a_i<2d$ の状態に $500$ 手以内で持っていけることを示せばよいです．適当な座標変換により $d=1$ としておきます．
まず，$\max(a)-\min(a)\leq 1$ を目指します．$x = a_2-a_1, y=a_3-a_2, z=a_4-a_3$ として，$\max(x,y,z)$ を減らしていきます．2nd max が max に比べて十分大きければ簡単です．max がその他に比べて巨大すぎるときには $O(1)$ 回で max を定数倍以下に減らせません．この場合には，2nd, 3rd max がフィボナッチ数列の増大度で増えるような操作を行って，max に対して十分な大きさになったタイミングで max を減らすように動けばよいです．max を定数倍減らすために $O(\log a)$ 回の操作以下で，$O(\log(a)^2)$ の操作回数です．ただし最悪ケースを引いた後には 3 つの gap のスケールが近づいていることから最悪ケースが続くことはないので実際にはもっと良いかもしれません．
全体が幅 $1$ におさまるようになったら，それを座標 $0,1$ のところまで持ってくることを次の目標とします．以降，適当な $2$ つの石を重ねて（操作も必要なら $2$ 回セットで行って）石を $3$ つと考えます．$2$ つの gap が Fibonacci 数を保つように広げていき，原点を含むように広げてから，逆に Fibonacci 数を保つように狭めていけばよいです．
F. Asterisk Substrings
アスタリスクの左につける文字列を固定したときに，右側につけられるものの種類を数える．ということをします．
左につける文字列については，reverse(S) の suffix tree を構築してノードごとに考えます．あるノードについて，
- 左につける文字列の種類数は単にその suffix tree のノードに対応する文字列の個数）
- 右につける文字列の種類数は、そのアスタリスクの位置に対応する suffix を選んで残したときの長さの和と、lcp の和から求まる
という要領です．suffix の追加削除を木上のマージテクのようにやれば，suffix の追加削除とそれらの間の lcp の計算を $O(N\log N)$ 回やればよくなります．
