コンテストページ
https://codeforces.com/contest/1290
解法
✔A - Mind Control
最終形が分かると、その両端の大きい方を取ればよいです。
何人にどちらを説得するかを決めると、最低限左右がどれだけなくなるのかがわかりますから、 そこから更に説得できなかった方々が左右から取る個数を全探索するイメージです。 これは、先述の両端の Max を前計算してあれば、sliding minimum です。（愚直で OK です。）
さらにこれらのすべての戦術をためして max を取ればよいです。
✔B - Irreducible Anagrams
irreducible であるかどうかを判定するのは、26 次元の格子上のパスが与えられて、 それと非交差なパスで同じ目的地に行けることです。（もしくは 1 文字の場合は例外です。）
この条件は、文字の種類が 3 種類以上であるか、2 種類であって先頭と最後が互いに異なることです。
構成は、同じ文字連打で出来ます。
✔C - Prefix Enlightenment
スイッチが頂点でライトが辺だと思いましょう。
簡単のため、どのライトも丁度 2 つのスイッチにつながっているとしましょう。 すると、ついているライトは traversal、消えているライトは non-traversal であるように二部グラフにできます。 スイッチを押す操作は、頂点を向こう岸に移動させる操作に対応します。
さて、ライトをどんどん増やしていきましょう。ユニオンファインドです！ traversal な辺をなくせばよいですから、連結成分ごとに小さい方の岸の頂点数がコストです。 連結成分ごとに 岸 0 の頂点と 岸 1 の頂点の個数を保持です。
ところで先程無視をしたことを考えましょう。片方だけが頂点につながっている場合があります。 この場合は、「動かざる頂点」につなぎましょう。 「動かざる頂点」につながっている連結成分では、コストは常にそれと反対岸の超点数です。
次にどこにもつながっていない辺を考えましょう。これはコスト 0 です。
ツイッターのご様子
A について
最悪なのでAはO(N^2)書いた気がするな
— olphe (@_olphe) February 2, 2020
B について
いやbaaabみたいなやつが作れると思っていたため...(目がない)
— idsigma (@IKyopro) February 2, 2020
わかります。
C について
Codeforces 616 div1
— tarattata (@tarattata1) February 2, 2020
A: 誤読でハマった。最終的に残った両端の大きいほうをとるので、その取り方の範囲を選ぶ
B: 既約anagramの条件の考察をいいかげんにやってしまいハマった。落ち着いて考え直してAC。
C: 差分更新Union-findを使いたいんだけど、未準備のため勉強してた。時間切れ。
これは私も初め思ったのですが、岸の割当を予めやっておくことで、ただの Union-Find でもできることに気づいてしまいました。天才ですね。
Cこれなに？各スイッチが影響出来るライトの集合でマージテクとかして地獄になってたんだけど 楽に出来るのか？
— 卒論に内容はいらない！ (@kyort0n) February 2, 2020
闇実装です。
C激重実装しか思いつかずに死んでた
— ふっぴー (@fuppy_kyopro) February 2, 2020
A：数列の N-M 個ズレな組の最大値をとっていってから、O(n^2) OK とのことなので削り方は愚直に全探索した
— けんちょん (@drken1215) February 2, 2020
B：1 文字は Yes、3 種類以上は Yes、1 種類 (2 文字以上) は No、2 種類のときは両端が異なれば Yes で等しいと No
C：F2 体を載せた重み付き Union-Find を頑張って更新した
結果
3 完で悲しい気持ちになっていたのですが、案外順位は良くてびっくりしてしまいました。(comming soon)
