x + y = k となるx, yの場合の数

Study

本来解きたかったのは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$$

コメント

タイトルとURLをコピーしました