C – Separated Lunch
$N\leq 20$
半分全列挙によって $O(N2^{N/2})$ 時間で解けます。
D – Laser Marking
$N\leq 6$
印字する順番を固定したうえで、直前に印字した線分を印字した方向で場合分けしながらシミュレーションすれば、 $O(N\cdot N!)$ 時間で解けます。
E – Sensor Optimization Dilemma 2
ある製造能力が達成可能かどうかで二分探索します。
生産能力あたりのコストが大きいほうの機械を導入する個数を、 $0$ 以上 $a$ 未満（ $a$ はもう一方の機械の生産能力）の範囲で変化させてコストの最小値を求めます。除算を $1$ 回した後は差分を加減算で調節すれば若干高速化します。計算量は $O(NA\log (AX))$ ( $A$ は $A_i$ , $B_i$ の最大値) です。
F – Shipping
$N\leq 100$
最適な行動は、
- (A) 出荷能力の限界まで使ってなるべく早く出荷する
- (B) ある注文が発生したタイミングに合わせて、（可能なら）その注文まで出荷する
の $2$ 種類で表せます。 (B) をチェックポイントにして、各始点から (A) をシミュレーション（注文の間隔が十分広いところは適切に出荷を省略する）すれば $O(N^2)$ 時間で解けます。（ 1 ms を取った実装の計算量は $O(N^2 \log N)$ です。）
G – Only One Product Name
$N\leq 26^2$
アルファベットを頂点、商品名を辺としたグラフにおいて強連結成分は簡単に処理したのち無視できます。商品名ごとに NG リスト内の occurrence を 1 つずつハイライトして、 $1$ つの文字列内に $2$ つのハイライトされた部分がある場合、その部分は「ある商品名の末尾から別の商品名の先頭までを、他の商品名を $0$ 個以上経由して連結」してできています。逆に、このように連結できるペアを作れれば、 DAG であることに注意すると作ったペアをすべて連結することでペアの数だけ NG リストの要素数が減ります。ペアの数の最大化は流量 $O(N)$ ・辺数 $O(N)$ の最大(整数)流で表せるので計算できます。