Custom Stone Taking

この問題は、 DP を累積和で高速化することによって解くことができます。

まず、ゲーム的な DP （$\text{dp}[n] =$ 石が $n$ 個残っているときに今の手番の人が勝てるかどうか）を考えると、次のようになります。このとき、 $\text{dp}[N]$ が $\text{true}$ なら高橋くんの勝ち、そうでなければ青木くんの勝ちです。（なお、 $\wedge$ は AND 、 $\bar{x}$ は NOT の意味です。）

$$\begin{aligned} \text{dp}[0] &= \text{false} \\ \text{dp}[n] &= \overline{\bigwedge_{i = A_n}^{B_n} \text{dp}[n - i]} \end{aligned}$$

以上の二番目の式は、 $dp[n - B_i]$ から $dp[n - A_i]$ までに $\text{false}$ があれば $\text{true}$ 、そうでなければ $\text{false}$ となります。よって、 $\text{false}$ の個数の累積和を取ると、次のようにできます。（$\text{Σdp}[i]$ は $\text{dp}[0]$ から $\text{dp}[i]$ までにある $\text{false}$ の個数です。）

$$\begin{aligned} \text{Σdp}[0] &= 1 \\ \text{Σdp}[n] &= \text{Σdp}[n - 1] + \begin{cases} 0 & \text{Σdp}[n - A_i] - \text{Σdp}[n - B_i - 1] \ge 1 \\ 1 & \text{otherwise} \end{cases} \end{aligned}$$

このようにすると、 $\text{Σdp}[N] - \text{Σdp}[N - 1] = 0$ なら高橋くんの勝ちということになります。