https://csacademy.com/contest/ioi-2016-training-round-3/summary/
$N$頂点の木が与えられ、さらに2頂点のペアが$M$個与えられる。$M$個のペアを結ぶパスすべてが少なくとも一つの破壊された頂点を含むように頂点の部分集合を破壊するとき、破壊する頂点の集合の最小サイズを出力せよ。
$M$個のパスについて、そのパスに含まれるノードのなかで最も根に近いものはパスの両端のノードのLCAである。ここで、あるノードがどのペアのLCAでもないときにはそのノードを通るパスはすべてその親も通るので、そのノードを破壊する代わりにその親を破壊してもよい。以上のことから、破壊するノードが最少となるような選び方の中に、選ぶノードがすべていずれかのペアのLCAであるようなものが必ず1つは存在する。
以下、$M$個のペアのうちどれかのLCAであるようなノードのみを破壊することを考える。LCAであるようなノードを列挙し、下(根から遠いノード)から順に調べる。そのノードを必ず破壊しなくてはならない条件は、そのノードがLCAであるようなパスのうち破壊されていないものが1つ以上存在する場合であり、そうでない場合には代わりに1つ上のLCAを破壊してもよい。
このようにして、必ず破壊しなくてはならないノードのみを破壊する貪欲を行えば最適解が得られることが言える。あるノードを破壊したとき、そのノードを通るパスすべてに対して破壊されたことを記録しなくてはならないが、それは以下のようにして高速に行える。
各ノードに対してそのノードを端とするパスの番号をリストとして保持しておき、あるノードを破壊した際にそのノードを含むsub treeを走査して、sub treeに含まれるノードを端とするパスをすべて破壊する。ここで、sub treeを走査している間にすでに破壊したLCAにたどり着いた場合、そこより下は調べなくてよいので全体の計算量は$O(N+M)$となる。
解説AC。考察の前半はそこそこ典型っぽいと思った（解けたとは言ってない）。
$N$台のコンピュータで構成されるネットワークがある。ここで、各コンピュータ間でファイルを転送するのにかかる時間が与えられる(コンピュータAからBへの転送とコンピュータBからAへの転送にかかる時間が異なる場合もある)。1台のコンピュータからは同時に1台のコンピュータにしかファイルを転送できないとき、コンピュータ1にあるファイルをすべてのコンピュータへ転送し終わるまでにかかる時間の最小値を出力せよ。
DPテーブルを
$DP[i][S]=$はじめにノード$i$にファイルがあるとき、ノードの部分集合$S$にファイルを配り終えるまでの最小タイム
とする。ノードiから始めて集合$S$にファイルを配りたいとき、$S$の部分集合$s\; (i\notin s)$と$s$に含まれるノード$j$を選んで、 最初に$i$から$j$にデータを送る→$i$から$S\oplus s$($S$のうち$s$に含まれないノード)に、$j$から$s$にデータを(同時に)配る。これをすべての$s, j$について行えば、その中に最適な配り方が存在するはずである。$i$から配る集合と$j$から配る集合に同じノードは含まれないので、これらは完全に並行して行える。以上のことから、DPテーブルの更新は $$DP[i][S]=\min(DP[i][S],cost[i][j]+\max(DP[i][S\oplus s], DP[j][s]))$$ となる。
最終的な答えは、0-indexedで$DP[0][2^N-1]$である。
解説AC。なるほどなぁと思った。
あるメッセージを電信で送信することを考える。ここで、メッセージ中には$N$種類の文字が存在し、各文字が登場する回数が与えられる。電報では'.'と'_'の2種類の音を送信することができて、'.'は1秒、'_'は2秒で送信できる。各文字に'.'と'_'からなる信号を適切に割り当てることによって、メッセージを送信し終えるまでの時間を最小化せよ。ただし、ある文字に割り当てた信号が別の信号のprefixになっていてはならない(同じ信号列から2通り以上の読み取りかたができるような割り当てはできない)。
$N=1$の場合、自明である。以下、文字が2種類以上ある場合を考える。
前提として、使用する信号の集合が決定したとき、送信に要する時間が短い信号から順に頻度の高い文字に割り当てていくのが明らかに最適である。
以下、2種類の音からなる信号をbinary trieで管理することを考える。音のない信号を表すノードを根とし、各ノードは'.', '_'を表す2つのノードを子に持っている。根から辿ってそのノードにたどり着くまでに通った音の列がそのノードが表す信号となる。ここで、ある信号が他の信号のprefixになっていてはならないという制約より、使用する信号の集合でbinary trieを構築したとき、すべての信号はこのtrieの葉でなくてはならないことがわかる(ある信号が他の信号の祖先であってはならない)。
$N=2$のとき、使用する信号は".", "_"の2つとするのが明らかに最適である。一般の$N$について、binary trie上で1つ上のノードが他の信号とのLCAになっていない(その信号を1つ上のノードが表す信号に置き換えても他の信号が使えなくならない)ような信号は使う意味がない(1つ上のノードを使えば良い)ので、最適になりうる信号の集合は、$N=2$の場合から以下のような操作を繰り返して得られる集合であるといえる。
ここで、ある信号$s$について、その子は$s+$'.'と$s+$'_'であり、$s$の送信に$t$秒かかるとき、その2つの子を送信するのにかかる時間はそれぞれ$t+1, t+2$秒である。以上のことから、問題を以下のように読み替えることができる。
---
$N$要素の整数列$A$が与えられる。また、整数の集合$\{1, 2\}$を持っている。ここで、以下のような操作を$N-2$回繰り返す。
操作によって得られた$N$個の整数列を$B$とし、$A$と$B$をそれぞれsortする。$\sum_{i=0}^{N-1} A_iB_{N-i-1}$を最小化せよ。
---
その時点で持っている整数のなかで最大のものを$a_{\rm max}$とする。整数を展開する順番は最終的に得られる集合に関係ないので、$a_{\rm max}, a_{\rm max}-1$しか展開できない(それより小さい整数はもう展開しない)としても、そのような制限のない場合に作れた集合が作れなくなったりはしない。ここで
$DP[fixed][small][big]=$まだ展開する可能性がある$a_{\rm max}-1, a_{\rm max}$がそれぞれ$small, big$個あり、$a_{\rm max}-2$以下の整数を含むこれ以上展開しないことが決まっている整数が$fixed$個あるときの暫定送信時間
というDPを考える。ここで暫定送信時間とは、すでにそれ以上展開しないことが決まっている$fixed$個の整数を頻度の高い文字に対応させ、それ以外の文字の送信に暫定的に$a_{\rm max}-1$秒かかるとした場合の送信時間である。
ここで、DPの更新は次の2種類である。
初期状態は$DP[0][1][1]=right[0]$であり、それぞれの遷移は
となる。ここで、$right[i]$は$A_i$以降の累積和である。また、$a_{\rm max}-1$を1つも展開しないことは、$small=0$の状態ですべて展開することに対応する。時間、空間的制約がかなり厳しいので、$fixed$を$fixed\%2$に置き換えたり、ループ変数の範囲を制限したりする工夫が必要である。
最終的な答えは、$DP[N][0][0]$である。
解説AC。問題の読み替えまではできたが、DPが書けなかった。このDPはかなりレベル高いのでは……。editorialでは$fixed$がない二次元DPをしていたが、あまり理解していない。