解説

\(f(q) = \mathrm{dist}(1, q)\) とおくと、 \(f(q) = \min (q - 1, |1 - x| + 1 + |q - y|) = \min (q - 1, x + |q - y|)\) が成り立ちます。

この式から、 \(q-y\) の符号の違いによって、連立方程式が成り立つような \(2\) 式を得られれば、 \(x, y\) を得られることがわかります。

まず、 \(f(N)\) は \(x, y\) によらず \((x - 1) + 1 + (N - y) = x - y + N\) です。

ここで、 \(f(q)\) が \(q - 1\) か \(x + |q - y|\) かには単調性があります。すなわち、ある整数 \(m\) が存在して、次が成り立ちます。

\[ f(q)= \begin{cases} q-1 & (q < m) \\ x + |q - y| & (m \le q) \end{cases} \]

ただし、条件を満たす \(m\) が複数ある場合は、最小のものを考えることにします。

このような \(m\) について、 \(f(m) = x + |m-y| = x+y-m\) です。このことは、 \(x \rightarrow y\) の辺を通った後、頂点番号の小さいほうにもどるような経路で最短経路が達成できる頂点が存在することから示されます。

単調性より \(m\) は二分探索で求めることができます。従って、 \(f(N)\) と \(f(m)\) が得られ、これらから \(x, y\) を求めることができます。

具体的には、

\[ \begin{cases} f(N) = x - y + N\\ f(m) = x + y - m \end{cases} \]

から、 \(f(N) + f(m) = x - y + N + x + y - m = 2x + N - m\) より \(x = \frac{f(N) + f(m) + m - N}{2}\) です。さらに \(y= x + f(m) - m\) です。

以上より、 \(f(N)\) を求めるクエリと、 \(m\) を求める二分探索のクエリの高々 \(\lceil \log_2 N + 1 \rceil\) 回のクエリで \(x, y\) を求めることができます。

クレジット

原案： null0124

問題準備・解説： null0124

解法提供： nu50218

レビュー： Levixi

テスター： DEGwer

校正： nu50218