概要
解法
$a_i, b_i$ の上限を $K$ とします（$K = 300$）。$1$ が $n$ 個ある状態を、「状態 $n$」と呼ぶことにします。
まずは、各状態 $n$ から可能な遷移を求められるようにしておきます。遷移は、$n\to n+x (-K\leq x\leq K)$ の形で、どのような $x$ が可能かを求められればよいです。
各 $x$ に対して、遷移 $n\to n+x$ が可能な最小の $n$ を計算することができます。実際、与えられるルール $(a,b)$ で $b-a=x$ を満たすもののうち、$a$ の最小値がこれを与えます。これを前計算しておけば、各 $(n,x)$ に対して遷移 $n\to n+x$ が判定できるようになります。
本問題は状態 $n$ に到達するまでの最短経路を問うています。操作中に通ることのできる状態の最大値 $\text{MAX}$ が決まっていれば、BFS によって答は $O(K\cdot \text{MAX})$ 時間で計算することができます。
実は、$\text{MAX} = N + 2K$ ととることができます。次のような観察をすればよいです。
- $N$ へ到達する経路をひとつ固定する。$N+2K$ より大きな値を通ると仮定する。$i$ 回目の操作ではじめて $N+2K$ より大きくなって、その後 $j$ 回目の操作ではじめて $N+2K$ 以下に戻ってくるとする。このとき、$i$ 回目・$j$ 回目の操作を入れ替えることで、$N+2K$ よりも大きな状態を通る回数を減らすことができる。
$K$ 以上の状態に対して、可能な遷移の種類は一定であることから従います。
よって、$\text{MAX} = N + 2K$ ととって、本問題は
- 前計算 $O(K^2)$ 時間
- BFS $O(K\cdot \text{MAX})$ 時間
をあわせて、$O(K^2+NK)$ 時間で解くことができます。
