本来解きたかったのはAtCoderのこの問題です。

B - Quadruple
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
解説PDFもYouTube解説もありますが、基礎というか前半部分で実装するx + y =kは頻出かなと思ったのでメモを残します。
問題文
\(x, y, k \in \mathbb{Z}\) が \(a \leq x \leq b, \quad c \leq y \leq d\)を満たし、\(k\)を任意の定数としたとき、\(x + y = k\)となる場合の数を求めよ
解説
2つの数直線を縦で足し合わせると常に\(k\)となるように噛み合わせる。

xの数直線は右が正、yの数直線は左が正となることに注意する。
以下のように色付けされた場所の長さが、求めたい場合の数である。

色付けされた部分の左側を\(l\)、右側を\(r\)とすると、
$$\begin{eqnarray*}
l &=& \text{max}(a, k-d)\\
r &=& \text{min}(b,k-c)\\
\end{eqnarray*}$$
\(l,r\)自身をあわせた範囲が答になるので、
$$r – (l – 1) = \text{min}(b, k-c) – \text{max}(a, k-d) + 1$$
コメント