A. Subscribers

難しい． 解答例

$m=|X \cap Y|$の最大値および最小値を求める問題．最大値が$\min \{|X|,|Y|\}$なのは分かる．最小値には「どちらも購読していない人たちが$0$人以上でなければならない」という条件が入る：$|X \cup Y|=|X|+|Y|-|X \cap Y|=a+b-m$より，先の人数は$n-(a+b-m) \ge 0$，移項して$m \ge a + b - n$が必要．加えて$m \ge 0$であるから，連立させて$m \ge \max \{(a+b-n), 0\}$となる．

B. Touitsu

最初なんとなくどれかに揃えれば良さそうな気がしたがそんなことは無かった．$a,b,c$の$i$文字目について多数決を採ればよい．どれも異なればコストは+2, 1ペアだけあれば+1, すべて揃っていれば+0． 解答例

C. Diffrent Strokes

解答例

高橋くんが目標を実現するための手段としては「自分のスコアを大きくする」以外に「青木さんのスコアを小さくする」もある．ここから考えると，高橋くんが$a[i]$番目を取ると青木さんは$b[i]$を取れないから高橋くんは$a[i]+b[i]$だけ得すると考えられる．よって$a[i]+b[i]$をソートし，これが大きい順に$a[i]$を取ればよい．青木さん視点でも同様に考えれば$b[i]+a[i]$の大きい順に取りたいこととなる．したがって先のソート結果から二人して大きい順に取って行き，高橋くんの手番ではスコアに+$a[i]$を，青木さんの手番では-$b[i]$していけばよい．

editorial

解説では片方の得点だけを考えてよいようにゲームを変形している．青木さんがすべて食べた状態，すなわち高橋くんのスコアが$-\sum b[i]$の状態から高橋くんが$i$を選んで自分のスコアに$a[i]+b[i]$加算する（青木さんが$i$を選んでもスコアが変動しない）ゲームを考えても同じこと．すると両者が注目すべきは高橋くんのスコアだけになる：高橋くんは自分のスコアを増大させることだけに専念すればよいので$a[i]+b[i]$の大きいほうから取って行けばよい．青木さんが出来ることは高橋くんが高いスコアを取れないように妨害する，すなわち$a[i]+b[i]$の大きいほうから取っていくことだけである．

D. Restore the Tree

トポロジカルソートはこの前やったこともあり使いそうだとは思ったもののどう使えばいいかわからず撤退．閉路ができるのではと疑ってしまったのだが全くそんなことは無かった（木構造に対して親から子孫に矢印を引くので子孫から親方向の辺が作られることはない）．

解説(editorial?)

解答例

根からトポロジカルソートすると（根は入力辺が無い点を調べればすぐに求まる），その結果はすべての辺のin/out順に並んでいる．いま要素$v$に入る辺が$p,q$（出現順序もこの通りとする）から出ているとき，元々の木に存在した辺は$q \to v$．

証明（editorialが分からなかったので独自解釈，したがって誤りがありそう）：$p \rightarrow v$が元々の辺だったとすると，操作によって$q \rightarrow v$を引く条件から元々の木にも$q$から$v$に至る経路$q \to s_1 \to ... \to s_{k-1} \to s_k \to v\ (k \ge 1)$^[1]が存在することとなる． まず元々は木構造であるから合流地点は存在しない：いま$v$に入る辺は$p \to v$と$s_k \to v$があり，これらが同一でなければならないから$s_k=p$である．ここで$q$から$v$への経路は$q \to s_1 \to ... \to s_{k-1} \to p \to v$となるが，これに含まれる各頂点はこの順序でトポロジカルソートに現れるはずである．これは$p,q$の順序に矛盾．

一方で$q \rightarrow v$が元々の辺であるとすれば$p \to ... \to q \to v$となり，問題なく操作によって$p \rightarrow v$を引くことが可能．辺の出自が$p_1,p_2,...,p_l,q$と3頂点以上の場合も各$p_i$と$q$に対して同様の議論を適用すれば$q \rightarrow v$以外あり得ないことが分かりそう．

最初トポロジカルソートにおいて右側の要素の深さは左の要素と同等またはそれ以上だと勝手に思っていたのだがそんなことはない（wikipediaの図からも分かる）．木構造でも片方の子を深く掘れば反例が作れる．

追記：editorial式

上を踏まえてeditorialを読むとそれなりに分かった気になれた：点$v$に入る辺を$\{x_i \to v\}$（$x_i$はトポロジカルソートに従って整列されているとする）とすると，合流地点が存在しないことから元の木での$x_i$から$v$への経路はすべてただひとつの辺$p_v \to v$に合流する（$p_v \coloneqq$元の木での$v$の親）．よって$x_i$は$p_v$の祖先（またはそれ自身）であるから，$x_1, ..., x_k, p_v, v$はトポロジカルソートにおいてこの順に現れることが分かる（重複部については順不同とする）．いま$\{x_i\}$の中に$p_v$が存在するが，それは$x_k$しかあり得ない．

こうして見ると合流地点の非存在性を意識できなかったことが敗因な気がする．

別解

本番で思いついたものの詰めきれずに捨てた解法だったがこれでも正解できるようだ．各頂点について根からの距離が最長となるような経路が元の木の経路となる．理由としては操作によって追加される辺は先祖から子孫を繋ぐ，すなわち根からの距離を減少させるようにしか張れないことが挙げられそう．これにより距離最大以外の経路を採用すると最大長の経路が作れなくなって矛盾する（と思う）．

今回のようなDAGの最長経路の求め方を検索すると，トポロジカルソートを利用したものが出てくる．GeeksforGeeksによると，トポロジカルソート順に頂点を調べ，そこを始点とする辺の終点について距離を更新していけばよいとのこと．理由が書かれていないので推測：通り過ぎた頂点に対して新たに最長経路が見つかるとそこから到達する頂点すべてに対して再計算が必要になるが，トポロジカルソート順だと一度通り過ぎた点はもう使われないために再計算が起こらないから？ 解答例

ところで提出を眺めていると上位陣にこれをBFSで求めている解答が複数存在した^[2]． BFSのアルゴリズムを思い出すと，BFS順で最後に点$v$に到達するときが根から$v$までの最長経路となる（最短経路から順に見つかっていくので）．したがってBFS順で最後になるまでは無視し，最後になったらようやく遷移をすればよい．最後かどうかは$v$に到達する辺の個数を数えておけば判断可能で，このときに親ノードを記録し，遷移をしていく．重みが一定の場合にしか使えなそうだが考え方として面白かった． 解答例

最初は「根からDFSをして各頂点に対して根からの最長距離を記録しておけば，もう一度DFSをすることでその情報から経路を復元できる」という方針を立てていたのだがこの方針だと例の再計算を何回も行うことになりTLE．

---

1. 後にも述べるが木は合流地点を持たないため$p \to v$と$q \to v$が同時に辺であることはない．従って$s_1$は必ず存在する． ↩︎

2. https://atcoder.jp/contests/nikkei2019-qual/submissions/4100659 など． ↩︎