ARC116Eとxmas16Hの関係性 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

このツイートによると、ARC116E は xmas16H を少しいじると解けるらしいです。
かなりびっくりしたので証明をしようとしてみたら出来ました。

これら２つの問題はいずれも整数 N, K と N 頂点の木が与えられます。
（xmasの方は重み付きですが、重みなしの問題で考えます）

ARC116Eの概要

K 頂点選んで、各頂点から選ばれた頂点までの距離の最大値を最小化せよ

xmas16Hの概要（ちょっと変えてるけど）

K+1 頂点選んで、選ばれた頂点間の距離の最小値を最大化せよ

双対感があると言われれば、そんな気もしなくはない？

これらの問題の答えをそれぞれ $X, Y$ とすると、 $X = \lceil Y/2 \rceil$ が成り立つことを証明します。

とりあえずサンプルとしてパスグラフを考えてみると、

$X = \lceil (\lceil N/K \rceil -1)/2 \rceil$
$Y = \lfloor (N-1)/K \rfloor = \lceil N/K \rceil -1$

となり、たしかに成り立っています。（厳密に書きましたが、だいたいで良いです）

$X \geq \lceil Y/2 \rceil$ と $X \leq \lceil Y/2 \rceil$ に分けて証明します。

$X \geq \lceil Y/2 \rceil$

$2X+1 \gt Y$ を示す。

ある頂点から距離 $X$ 以内の頂点の集合をエリアと呼ぶことにする。
エリアから 2 つの頂点を選ぶと、それらの距離は $2X$ 以下になる。
ARC116E で $X$ を達成する解を 1 つとると $K$ 個のエリアで全頂点が被覆できるため、
互いの距離が $2X+1$ 以上になるように頂点を選ぶとき、高々 $K$ 頂点しか選ぶことができない。
よって、 $2X+1 \gt Y$ 。

$X \leq \lceil Y/2 \rceil$

$2(X-1)+1 \leq Y$ を示す。

ARC116E の判定問題は以下のアルゴリズムで解ける。

根を適当に選んで根付木にし、以下を繰り返す
残っている頂点のうち最も深いものを v とする
v の $X$ 個上の祖先を選び、距離 $X$ 以内の頂点を候補から消す

一方、xmas16H の判定問題は以下のアルゴリズムで解ける。

根を適当に選んで根付木にし、以下を繰り返す
残っている頂点のうち最も深いものを v とする
v を選び、距離 $Y-1$ 以内の頂点を候補から消す

これらのアルゴリズムは 3. のみが異なるが、実は挙動はほぼ同じである。
特に、 $Y$ が奇数の場合は $X=(Y-1)/2$ とすると完全に等しい。
祖先を選ぶか v を選ぶかの差は"祖先"以下の部分木内でしか生まれないが、
いずれにせよ"祖先"以下の部分木内の頂点は全て候補から消されるため、等しくなる。
（最も深いものを v としているのが効いている）

ARC116E の答えが $X$ であることから、 $X-1$ で上記のアルゴリズムを実行すると $K+1$ 個以上の頂点が選ばれるはずである。
つまり xmas16H で $Y=2(X-1)+1$ としたときの判定問題は True となるはずであり、 $2(X-1)+1 \leq Y$ が示された。