- https://codeforces.com/contest/1031 (Technocup 2019 – Elimination Round 2)
- https://codeforces.com/contest/1072 (div2)
- https://codeforces.com/contest/1071 (div1)
A. Cram Time
合計 $k$ を達成するには $\sum_{i=1}^k i\leq a+b$ が必要です．この必要条件のもと達成できます．$\{1,2,\ldots,k\}$ の部分和で $\sum_{i=1}^k i$ 以下の値を好きに作れることを示せばよく，これは大きい方から貪欲していけば帰納法で示せます．
B. Minimum path
答えの先頭から順に決めていきます．特定のパスは作らずに，あるマスまで答えと同じ文字列で到達するときの最小コスト（余せている変更回数の最大値）を持ちます．
C. Triple Flips
十分長ければできるというのが結論です．
「$N$ が十分大きいときに $N$ が小さい場合に帰着」「$N$ が小さい場合の解法」の 2 パートを実装しました．後者は最短路問題でよいです．
前者は，末尾が $0$ ならばそのまま $N$ を $1$ 減らし，そうでない場合には suffix に操作して，「$1$ 手で長さを $3$ 減らす」または「$2$ 手で長さを $6$ 減らす」ができることが確認します．$8$ 通り場合分け気合実装などをしました．
D. Familiar Operations
最悪ケースの操作回数を適当に見積もると，指数の合計が $30$ 程度以下の範囲だけで探索すればよいことになります．素数の頻度列として可能なものを分割数だけ列挙します．
これらの状態では約数の個数が同じ状態も多くあるので，最終状態の約数の個数を決め打って多点スタートで最短路問題をすることで，最終状態の約数の個数を決めた場合の答がまとめて計算できます．
E. Rain Protection
比較的やるだけではあります．端点が $(x_1,0), (x_2,h)$ である状態を座標平面上の $(x_1,x_2)$ に対応させます．各時刻の要請は，
- そもそも達成不可能
- $(x_1,x_2)$ が特定の点のときに達成可能
- $(x_1,x_2)$ が特定の線分上のときに達成可能
となります．特定の点も長さ $0$ の線分と思うことにして，これら線分を求めておきます．あとは元の問題の設定を忘れて，点 $(x_1,x_2)$ に関する問題を解きます．
解を二分探索することにします．時刻を順に見ながら，その時刻に存在可能な $(x_1,x_2)$ の領域がどのようになるものかを調べます．
領域に対する操作は次のようになります：
- 移動：$[-d,d]\times [-d,d]$ の形の正方形との Minkowski Sum をとる．
- 各時刻の要請：ある線分上に制限する．
領域は空にならない限り常に線分であることが言えるので，この線分を管理します．
Minkowski 和はいくつかの半平面（$1$ 次不等式）として書くことで線分との交わりを求めました．
