1回の操作毎に、Aの合計がBの合計より1ずつ大きくなっていくので、最初からAの合計の方が大きければ無理なのは分かる。
それ以外で無理なのは？
入力例2では、Bの合計の方が大きいのに、正解はNoとなっている。実際にやってみる。
5 3 1 4 1 5 2 7 1 8 2
ここで、最終状態の差し引きが0、またはAへの操作が残っていた場合は残りを消費することで帳尻あわせが可能
しかし、Bへの操作が残っていた場合、全体の合計から、これ以上操作することは出来ない。これで判定できる。
二分探索
まず、追加する辺の数は $N-M-1$ 本。（最終的に木にした時の辺の数が $N-1$ 本、現在が $M$ 本）
そのために必要な頂点が $2(N-M-1)$ 個なので、これが $N$ より大きい場合、不可能。逆にこれさえ満たしていれば大丈夫。
各木を他と繋ぐためには、相手はどうあれ、必ず木の中の1頂点から辺を伸ばす必要がある。それは各木の最小コスト点を選べばよい。
各木から伸ばした辺の相手を考える。
より具体的に、いま、2個の連結済みの木(AとBとする)に新しい木(Cとする)を繋ごうとしている時、Cを繋ぐ辺の相手となるA,B側の頂点を考える。
すると、下図で、A,Bは2つの木を●によって繋いだ後の状態（●はA,Bそれぞれでコスト最小の点）。そこにCを繋ごうと思ったら、Cのコスト最小点と、A,Bの●以外でコスト最小点を繋ぐのがよい。
A B C
○ ○ ○
/\ /\ /\
○○ ○○ ○○
/ /\ /
○○●--●
これを、「A～Cを繋いだ木に、Dを繋ぐと……」と次々考えていくと、結局は「各木の中でコスト最小の点の合計」＋「それ以外の点から、全体が $2(N-M-1)$ になるまでコストが小さい方から選んだ点の合計」が答えとなる。
1本の辺のコストを、2頂点で別々に考えるのは思い至らなかった。
特定できないのはどういう場合か。
…… ＼ ● ／|＼ ○ ○ ○ １ ２ ３
たとえばこんな部分木を考えると、●より上側の頂点(●含む)にいくら観測所があろうと、●の下側に観測所が無いと、○はどれも同じ距離になる。
ならばということで１に観測所を作っても、２と３はまだ区別できない。１と２に観測所を作ると、３を区別できるようになる。
つまり、「全ての頂点に対して、その子の部分木のうち、観測所が含まれなくてよいのは1つまで」と条件を読み替えられる。
ただ、その考えだけだと、こんな時に上手くいかない。
１
／＼
２ ３
／＼
４ ５
／＼
６ ７
６か７のどちらかに観測所を1つ作るだけで「全ての頂点に対して、その子の部分木のうち、観測所が含まれなくてよいのは1つまで」という条件は満たされるが、たとえば１と４の距離が同じになってしまう。
この場合、次数が3以上の頂点を根にすることで、何故か上手くいく。それで上手くいく理由が、いまいち分からない……
３ ／|＼ １ ４ ５ ／ ／＼ ２ ６ ７
「木の辺に対して値が与えられ、経路に対しxorする」という操作は、
「木の頂点に対して値が与えられ、任意の2点を同時にxorする」と読み替えられる。全頂点の値を0にするのがゴール。
木の頂点の値が表すのは、その頂点から出ている全辺の値のxor。すると、経路の途中の頂点は同じ値を2回xorされるので変わらない、というテクニックらしい。なるほどー。これなら、考えるのが楽になる。
まず全頂点の初期値を求め、任意の2点で同じ初期値ならババ抜きのようにその2点で打ち消し合えばよい。
残るのは、0～15の頂点が、たかだか1個ずつ。制約が15とか、いかにも全探索してくださいと言わんばかりなので、そうする。
H - Generalized Insertion Sort
2000点問題にしては、まだ「何をやればいいのか理解できる」
ある頂点 $v$ に対し、そこに入る値($v$)を探して根まで持ってきて、その次の操作で $v$ に入れる、ということを繰り返すとできるのはできるが、1個ずつやると回数制約的に無理。
根まで持ってくるのに $O(N)$、それを全 $N$ 頂点に行うと、計 $O(N^2)$。これを全体で $O(N \log{N})$ に抑えられたら、25000回に間に合う。
それには、解説の用語を借りると「葉パス頂点」について一度に値を設定する方法が考えられる。
○
／｜＼
● ○ ●
／ ／｜＼
● ○ ● ●
／＼ ｜
● ● ●
「各葉から、2つ以上の子を持つ頂点が出てくる手前まで辿った経路上の頂点」を「葉パス頂点」と呼ぶ。これらに正しい値を $O(N)$ で入れ、木から切り落とす。すると残りの木からは新たに葉パス頂点が生まれる。これを根が葉パス頂点になり、正しい値が入るまで繰り返す。これは、$O(\log{N})$ 以内に収まる。
具体的な操作方針は、
操作毎に、「葉パス頂点に入るべき値が割り振られている中で、最も深い頂点」が分かるよう、情報を更新する。
考察中、どの変数が「値」を指すのか「頂点」を指すのかごっちゃになって大変だった。こういうのをスッキリ整理して考えられるようになりたい。