F 問題「タイトル未定」解説

部分点（2点）解法

部分点制約は以下の通り：

• $N ≦ 10$．
• $K_i = 2$．

$K_i = 2$ なので，どの点に対しても条件は「自分以外で一番近い点への距離が $D_i$」となる．

このとき，各点に対して座標 $X_i + D_i$ か $X_i - D_i$ の少なくとも一方には点があるから， どちらの点があるかを全探索すればよい．

ただし，$X_i + D_i$ または $X_i - D_i$ に常に新しい点を置けばよいというわけではないことに注意． この候補地点にすでに他の点があるときは，置いてしまうといけない場合がある．

なので，候補地点にすでに点がある場合は置かない，とするか，そもそも両方ともに新しい点はないという場合も 考えて $3^N$ 通りを全部試しても良い．

満点解法

「$X_i$ から見て $K_i$ 番目に近い点への距離が $D_i$ である」という条件はそのままでは扱いにくいので， なんとかして扱いやすい形に変えたい．

そこでこの条件を「距離 $D_i$ 未満のところには点が $K_i$ 個以上あってはいけない」かつ 「距離 $D_i$ 以下のところには点が $K_i$ 個以上なければいけない」と言い換える． すると，「$K_i$ 番目に近い」といった扱いづらい形から， ある範囲に存在する点の個数に関する条件に変えることができる．

ここで $S[x]$ を「座標が $x$ 以下の点の個数」と定義する． $S$ がわかればある座標にある点の個数もすべて分かる（$S[x] - S[x - 1]$ 個の点が座標 $x$ にある）から， $S$ が満たすべき条件を考えて，そのような $S$ が存在するかどうかを調べることにする．

まず，定義より明らかに，任意の整数 $x$ に対して以下が成り立つ必要がある．

• $S[x] ≦ S[x + 1]$．

次に，はじめからある $N$ 個の点について，ある座標 $x$ に元から点が $p$ 個あったとすると次の式が成り立っていないといけない．

• $S[x] ≧ S[x - 1] + p$．

最後に条件について考える．「$X_i$ から見て $K_i$ 番目に近い点への距離が $D_i$ である」という条件は（さっきの言い換えから分かるように）以下の $2$ つの不等式が成立することと同値である．

• $S[X_i + D_i - 1] - S[X_i - D_i] < K_i$．
• $S[X_i + D_i] - S[X_i - D_i - 1] ≧ K_i$．

答えが impossible であるかどうかは，以上の式を満たすような $S$ が存在するかどうかを判定すれば分かる． 以上の不等式はすべて「変数 ≦ 変数 + 定数」の形で表されており，この形の制約式は最短路問題として解けることが知られている（いわゆる「牛ゲー」）．

ここから牛ゲーの簡単な解説なので知っている人は読み飛ばして構いません

（単一始点）最短路問題は，グラフ上である始点 $s$ から他のすべての頂点への最短路を求める問題である．

いま，始点 $s$ からある頂点 $v$ までの最短距離を $d_v$ とする． 明らかに $d_s = 0$ が言える（グラフ上に $s$ から到達できる負閉路がないとする）．

グラフ上に辺 $(u, v)$ があり，そのコストが $w$ のとき，この辺が $d$ に課す制約について考える．

始点 $s$ から頂点 $u$ への最短距離が $d_u$ で，その後辺 $(u, v)$ を使って頂点 $v$ へ行くことを 考えると，頂点 $v$ へは少なくとも距離 $d_u + w$ で行けることがわかる．つまり，

• $d_v ≦ d_u + w$．

が成り立つ．（等号でなくて不等号なのは，$(u, v)$ を使うより短い経路があるかもしれないから）

$d$ を具体的に求めるときは辺のコスト $w$ がすべて非負のときは Dijkstra 法が使え，そうでないときも Bellman-Ford 法が使える．（グラフに負閉路があるときはそのような $d$ は存在しない）

制約を満たすような $d$ はいくらでも存在するかもしれないが，最短路問題によって求められるものは その中でも $d_v$ がとりうる最大の値になっているという性質がある． （不等式制約は $d_v$ を上から抑える形になっているため，ありうる最大の値が最短距離に対応する）

よって，上のような形の不等式制約があったときには，対応するグラフ上での最短路問題を解くことで それを満たすような $d$ が存在するかどうかを判定し， もし存在するなら $d_v$ を最大にするような $d$ の具体例を求めることができる．

ここまで牛ゲーの解説です

$S$ が満たすべき制約式から対応するグラフを作って最短路を求めるが，注意する点がいくつかある．

• 座標の範囲は $32$ ビットと広いので全部の座標に対応する頂点は作れないから，上の不等式で注目した点に関してだけ不等式を作る．（座標圧縮のイメージ）
• 制約 $S[x] ≦ S[x + 1]$ は座標圧縮後の点についてのみ辺を張る．
• 最短路問題によって得られるのは $S[x]$ の最大値なので，使う点の個数を減らしたいという要求と相反する．なので，$S[∞]$ を始点として最短路を考え，(-使う点の個数)を最大化すると考える必要がある．

ダミーの頂点 $S[-∞]$ を作っておけば $-S[-∞] - N$ が条件を満たすために必要な追加する点の最小個数になる． 実際に点の座標を復元する際には，座標を小さい方から見ていって $S$ が増加するタイミングでその座標を必要な個数だけ出力すればよい．