A. Alice the Fan
状態数は十分少ないので，適当な dp により最適化できます．ルールが複雑なのでちょっと面倒ではあります．
B. Bimatching
左側頂点が $n$ 個，右側頂点が $m$ 個ある二部グラフ $G$ において，「左 $1$ 個と右 $2$ 個」の形の $3$ つ組をたくさんとる問題です．
左側の頂点 $v$ を $v_1,v_2$ に倍加して，さらに $v_1$ と $v_2$ の間にも辺を張ることで（二部とは限らない）$2n+m$ 頂点のグラフ $H$ を作ります．
$H$ において最大マッチングをとります．このマッチングにおいて，$v_1,v_2$ のうち少なくとも一方は飽和しています（$v_1v_2$ 辺があるので）．$v_1$ が非飽和ならば $v_1v_2$ 辺使うマッチングに取り換えることで，最大マッチングであって，すべての $v_1,v_2$ が飽和しているものをとることができます．
このマッチングの大きさを $n+k$ とするとき，$k$ 個の $3$ つ組を取り出すことが可能です．逆に $k$ 個の $3$ つ組がとれるなら大きさ $n+k$ のマッチングがとれます．
C. Cactus Search
適当解法が通ってしまいました．質問をして最悪ケースの返答がかえってきたときに残る候補頂点数がなるべく少なくなる質問を選んでいきます．
そして解説によればこの解法は正当性があるということに．
候補頂点への距離の総和が最小となる点を質問します．これは木の場合に重心を選ぶということの類似と見なせるかもしれません．
$S$ を候補頂点集合，質問した点を $v$，返答を $w$ とします．$T$ を新たな頂点集合とします．すると，
- $x\in T$ ならば $\mathrm{dist}(w,x) \leq \mathrm{dist}(v,x)-1$
- $x\in S\setminus T$ ならば $\mathrm{dist}(w,x)\leq \mathrm{dist}(v,x)+1$
となることと，$v$ を候補頂点への距離の総和が最小となるようにとったことから，$|T|\leq \frac12|S|$ が示せます．
Cactus やこの入力形式は NEERC の伝統のようですが，この解法は一般の連結グラフでも成立しますね．
D. Distance Sum
頂点重みも考える形に問題を一般化しておきます（$w_uw_v\dist(u,v)$ を求める問題）．
まずは次数 $1$ の頂点を葉を処理していきます．葉の近傍となる辺について，答に何回寄与するかは簡単に求まります．これを答に加算したら，この辺の長さは以降 $0$ として扱ってよいです．すると，辺を削除して頂点重みをマージしてもよいということになります．
この操作を可能な限り繰り返すと，$E-V$ の値を保ったまますべての頂点の次数を $2$ 以上にできます．このとき次数 $3$ 以上の頂点の個数は $O(E-V)$ です（本問の制約ではこれが小さな定数でおさえられている）．
次数 $3$ 以上の頂点を大事な頂点として，グラフを大事な頂点が次数 $2$ の頂点列で結ばれていると見なします．この頂点列ごとに，そこが始点である場合の答の計算をまとめて行うことを考えます．次数 $3$ の頂点がひとつもない場合には，どれかひとつを大事な頂点ということにしてしまえば同様です．
すると，あとは基礎的な計算問題になります．注目しているパスをメインパスと呼ぶことにしたとき，
- メインパスを適切に処理する．
- メインパスの外にある点については，メインパスの $2$ 端点からの距離の組が重要となるのでこれを最短路問題で計算する．実際には距離の組というよりもそれらの差分が重要となる．差分ごとに適切な値を持っておく．
- あとはメインパスの始点ごとに計算する．
メインパスごとに $O(N)$ 時間で計算できます．
Problem E. Easy Chess
気合という感じです．$2$ 行ずつとっていって，最後を適当に調整すればよいでしょう．
一応場合分けを減らすために，ある「経路」を考えたときに，「止まらなくてよいマス」を飛ばすことで経路長を調整するというロジックを入れて，いくつかの経路ですべてが網羅できるようにしました．
F. Fractions
$n$ が素数べきなら不可能です．そうでない場合には，ちょうど $2$ つの分数で条件を満たせます．
G. Guest Student
最初の曜日を全探索して $7$ 通り計算すればよいです．
H. Harder Satisfiability
難しかった．十分性については解説の証明も良くわからなかったので自分で考えた証明方針です．
2-SAT と同様の辺を張ります．$2N$ 個の頂点 $x_{v,i}$ （$1\leq v\leq N$, $i\in \{F,T\}$）があって，$x_{u,i}\to x_{v,j}$ 辺の存在と $x_{v,\overline{j}}\to x_{u,\overline{i}}$ 辺の存在が同値になっています．
$v$ が “forall” で量化されているとき，$v$ を forall 変数，$x_{v,i}$ を forall 頂点と呼ぶことにします．exist についても同様です．
$v$ の値を選ぶことは，$x_{v,F}$ と $x_{v,T}$ の間に適当な方向に辺を張ることと対応します．すべての値を選んだときに論理式全体が true になるのは，結果として任意の $v$ に対して $x_{v,F}$ と $x_{v,T}$ が同じ強連結成分に来ないということです．
まず次の $3$ つの必要条件があります．
- [1] $x_{v,F}$ と $x_{v,T}$ は同じ scc にはない．
- [2] $u<v$ で $u$ が exist 変数，$v$ が forall 変数であるとき，$x_{u,i}$ と $x_{v,j}$ は同じ scc にはない．
- [3] $u,v$ がともに で $u, v$ がともに forall 変数であるとき，$(u,i)\neq (v,j)$ ならば $x_{u,i}$ から $x_{v,j}$ へ到達することはできない．
必要性の証明
[1] は明らかです． [2] を示します．$u$ の真偽を適当に確定させたとき，$x_{u,i}\to x_{u,\overline{i}}$ またはその逆方向に有向辺が追加されます．すると，同じ scc にあることから $x_{v,j}\to x_{v,\overline{j}}$ またはその逆方向に有向パスができます．すると $v$ の真偽のうち片方しか使えなくなるので，$\forall v$ の条件を満たせなくなります． [3] を示します．$x_{u,i}\to x_{v,j}$ という有向パスが存在したとします．このとき $x_{v,\overline{j}}\to x_{u,\overline{i}}$ も存在します．$u$ の真偽を適当に決めて $x_{u,\overline{i}}\to x_{u,i}$ 辺を追加すると，$x_{v,\overline{j}}\to x_{v,j}$ に有向パスができます．すると $\forall v$ の条件を満たすことができなくなります．以上で [1], [2], [3] の必要性が確認できました．
十分性の証明
十分性を証明します．[1], [2], [3] が成り立っているとするとき，$v=1,2,3,\ldots$ 順に，exist 変数ならば真偽を適切に選べば，forall 変数ならばどちらの真偽を選んでも，[1], [2], [3] の条件が保たれることを確認すればよいです．$v=1$ の場合を確認すればよいです．
まず $v=1$ が exist 変数であるとします．$x_{v,T}\to x_{v,F}$ へ有向パスがあるならば，その方向に有向辺を追加します（真偽を確定させます）．これは到達可能性や強連結成分の情報を変化させないのでよいです．
これらの間に到達可能関係がないならば，どちら方向に辺を追加しても，強連結成分は変化しません．よって [1], [2] は大丈夫です．
[3] が成り立っているとき，次のうちどちらかが成り立ちます．- $x_{v,T}$ へ到達可能な forall 頂点は存在しない．
- $x_{v,T}$ から到達可能な forall 頂点は存在しない．
両方が成り立つと forall 頂点同士に到達可能関係ができてしまい [3] に矛盾するからです．
前者が成り立つとき，$x_{v,T}\to x_{v,F}$ 辺の追加，後者が成り立つとき $x_{v,F}\to x_{v,F}$ 辺の追加により [3] が保たれます．以上により，$v=1$ が “exist” 変数の場合には示されました．
$v=1$ が forall 変数であるときに，どちら方向に辺を追加しても 3 条件が保たれることを確認します．まず [3] が成り立っているとき辺の追加により強連結成分は変化しないので [1], [2] は大丈夫です．[3] が保たれることも exist 変数と同様に確認できます．
I. Interval-Free Permutations
simple permutation 数え上げという有名問題です．https://oeis.org/A111111
$\sum_{i\geq 1} i!x^i$ の逆関数の計算に帰着されます．本問題の場合にはラグランジュ反転を使ってクエリごとに $O(N\log N)$ 時間で計算できます．
J. JS Minification
読解を頑張ります，とはいえそれほど難しい読解ではないです．
まずは各点からなるべく長い token をとっていくというのを定義通りにやることで token に分解します．さらに word token については指定された方法で置換します（reserved token との重複をさせないように注意）．
できた token を $S_1, S_2, \ldots$ とします．token の間に半角スペースを挿入するかどうかを考えるだけです．
各 $i,j$ に対して，$S_i,\ldots,S_j$ を半角スペースなしに結合することが許容されるかを考えます．これらを結合したときに “longest token prefix” が $S_i$ になっているかを判定するのが主な課題です．より長い token がとれるのは，$S_i$ に $1$ 文字追加したものが token になる場合または，何文字か追加したものが reserved token になっている場合だけで，これを判定します．
この判定をすれば，あとは適当な dp や最短路問題で半角スペースの個数を最小化できます．
K. King Kog’s Reception
所要時間 $n$ の人は，所要時間 $1$ の人 $n$ 人に置き換えてよいです．各時刻で何人の待ち人が居るかを求められるようにしたいです．求値クエリは時刻 $t$ での待ち人の人数を出力すればよいです．
各時刻のイベントは，待ち人の人数に $x$ を加算し，$1$ を減算し，chmax(-,0) をするという形で書けるため，$x\matpsto \max(x+a,b)$ のタイプの関数合成のセグメント木でこれを行うことができます．
L. Lazyland
各タスクに割り当てられている人が複数いるとき，その最小コストのものから貪欲に使っていけばよいです．
M. Minegraphed
$1$ 階，$2$ 階，… のような構造を作って，各フロアを強連結成分に対応させます．上の階ほど topological 順が手前になるようにして，$i\to j$ 辺があるときにそこを空洞にして $i$ 階から $j$ 階まで落ちられるようにすればよいです．
