087 - Chokudai's Demand（★5） Editorial by Kazu1998k
解答の方針
\(X=x\) のときに \(P\) スヌーク以下で到達できるような街の組の個数を \(\tau(x)\) と書くことにする. このとき, \(\tau (x)\) は広義単調減少であることがわかる.
$\tau(x)$ が広義単調減少であることの証明
$\operatorname{dist}(i,j; x)$ が $x$ について広義単調増加であることの証明
$A$ を空でない集合, $f,g : A \to \mathbb{N}$ を写像とする. 任意の $a \in A$ で $f(a) \leq g(a)$ ならば, $\min f(A) \leq \min g(A)$ である.
$P_W(x)$ で 歩道 $W$ における $X=x$ のときの最小スヌークとすると, 任意の $i,j$ -Walk において, $x \leq x'$ ならば, $P_W(x) \leq P_W(x')$ であることがわかる. よって, 全ての $ij$ -Walk を考えると, $\operatorname{dist}(i,j; x) \leq \operatorname{dist}(i,j; x')$ であることがわかる.
このことから,
\[x \leq x' \Rightarrow [\operatorname{dist}(i,j; x) \leq P] \geq [\operatorname{dist}(i,j; x') \leq P]\]
なので, \(1 \leq i < j \leq N\) に関して和を取ることで,
\[x \leq x' \Rightarrow \tau(x)=\sum_{1 \leq i < j \leq N} [\operatorname{dist}(i,j; x) \leq P] \geq \sum_{1 \leq i < j \leq N} [\operatorname{dist}(i,j; x') \leq P]=\tau(x')\]
となり, \(\tau(x)\) は広義単調減少である.
\(\tau(x)\) が広義単調減少なので, 以下の場合はすぐに答えを導くことができる. ただし, \(\infty\) は十分大きい整数とする.
- \(\tau(\infty)>K\) のとき: \(\tau(x)=K\) となることは無いので, 答えは \(0\) である.
- \(\tau(\infty)=K\) のとき: \(x \geq \infty\) なる全ての整数 \(x\) は \(\tau(x)=K\) となるので, 答えは \(\infty\) である.
以下, \(\tau(\infty)<K\) とする. また, \(\tau(x)\) は非負整数値を取るので,
\[\tau(x)=K \iff \tau(x) \geq K かつ (\tau(x) \geq K+1 ではない )\]
であることから, \(\theta(k)\) で \(\tau(x)=k\) を満たす正の整数 \(x\) の個数とすると, 答えは
\[\theta(K)-\theta(K+1)\]
である. ここで, \(\theta(k)\) は, \(\tau(x)\) の計算量を \(O(H)\) としたとき, 2分探索を利用することにより, \(O(H \log A_{\max})\) で求めることができる.
\(\tau(x)\) の求め方
解答の方針が求まったので, \(\tau(x)\) を求める方法を考える. 今回は \(N \leq 40\) と制約が比較的小さめなので, Warshall–Floyd 法を利用することができる. Warshall–Floyd 法は任意の頂点間の最短距離を計算量 \(O(N^3)\) で求めることができる.
よって, \(\tau(x)\) を \(O(N^3)\) で求めることができるので, 計算量 \(O(N^3 \log A_{\max})\) で求めることができた.
posted:
last update: