- https://codeforces.com/contest/1781 (VK Cup 2022 – Отборочный раунд (Engine))
- https://codeforces.com/contest/1782 (Div. 1 + Div. 2, based on VK Cup 2022 – Elimination Round)
A. Parallel Projection
どの方向から降りるかで $4$ 通りを計算．
B. Going to the Cinema
参加者は sort したときの prefix です．それぞれ判定します．
C. Equal Frequencies
使う種類数を固定するごとに解きます．
D. Many Perfect Squares
$2$ 個以上が同時に平方数になるパターンが十分少ないです．$a_i+x=s^2$, $a_j+x=t^2$ のとき $(s+t)(s-t)=a_i-a_j$ から約数列挙を利用して候補となる $x$ を列挙します．
E. Rectangle Shrinking
もとの面積と同じものが実現できます．サンプルから推測可能かもしれません．
これが成り立つ前提で示そうとすると解きやすくなります．まず各種類（上・下・上下）ごとに，和集合を変えないまま交わりがなくなるように縮めます（成立を可能しているのでやっても大丈夫）．
上のみ・下のみであるようなものだけを置いておきます．その後に上下にまたがるやつを置くことを考えます．この際，そのまま置いてしまうと既存のタイルを分断してしまうパターンに気を付けます．
分断してしまうのはその区間に空きマスがないときだけで，そういうものがないときは縦方向に縮めて使えばよいです．
F. Bracket Insertion
累積和が $a$ のところに $b$ 回挿入する方法（つまり “((()))” の中央部分だけに挿入して正しいカッコ列にする方法）の個数 dp[a][b] を求めます．
計算では，$a$ を止めたときの dp テーブル自身の畳み込みが欲しくなります．これも dp テーブルが埋まるたびに合わせて計算するようにすれば，全体で $3$ 乗時間ですべて計算できます．
G. Diverse Coloring
実験すれば，頂点数が $4$ 頂点以下の例外を除き，最小値は単に $n\bmod 2$ になることが観察できます．あとはこれを構成的に証明できればよいです．
$2$ つの子がどちらも頂点数 $5$ 以上であれば，subtree を再帰的にで解いてから根を決めればよいです．どちらも頂点数 $4$ 以下である場合は個別処理します．問題となるのは片方の subtree だけが頂点数が $4$ 以下の場合ですが，これらも適当な場合分けで解けます．
H2. Window Signals (hard version)
$k=2$ とします．bounding box の大きさを固定して解きます．禁止されるパターンを数えます．
壊れたマスが来ない位置は，自由です．あるマスに壊れたマスを持ってきてもう一方を box の外にできるなら，そのマスは on になっている必要があります．
それ以外の条件としては，マス x, y について，$x,y$ が同時に壊れたマスに重ねられる場合には，どちらかが on である必要があります．そのような条件によってパス分解すると，いくつかのマスの列があってその列上では off が連続しないという条件に分解できます．
これらの条件ごとの数え上げの積をとれば良さそうです．が，bounding box に関する条件もあります．これは，$4$ 辺上に on があるかという $16$ 状態を持てばよいです．
これを実装すると，$n=\max(H,W)$ として, 計算量 $\Theta(n^4)$ になります．定数倍をある程度頑張れば十分間に合います．
例えばパスの長さに対する何かは，最初に前計算しておけます．パスの先頭・末尾に対する $16$ 通りの bit がどれであるかも含めて前計算しておきます．同じ種類のものを何度も or convolution で畳み込むことになりますが，何を何回畳み込むかだけを計算しておいて最後にまとめて畳み込みます．畳み込みは or convolution なので，適当なゼータ変換により各点積に帰着しておきます．
そのようなことを十分実装したら AC になりましたが，実行時間にはかなり余裕があったので，いくつかのアイデアは不要だったかもしれません．
