表題の問題について、自分の理解のために簡単にまとめます。

問題

目的

AtCoder Beginner Contest 261 A - Intersectionについて、解説のページは下記です。

読むと、答えは $max(0,min(R_1,R_2)−max(L_1,L_2))$ で求めることができると知りました。なぜこの回答でいいのかを、公式の説明動画を元に簡単にまとめます。

今回の問題は、赤の線と青の線のどちらも含むXが何個あるか求める問題を言い換えることができます。

式にすると下記のようになります。

$\displaystyle L_1 ≦ X ≦ R_1$

$\displaystyle L_2 ≦ X ≦ R_2$

まずは、２つの式の左辺について考えます。

この時、 $L_1$ と $L_2$ のうち、大きい値を選択し、その値よりもXが大きければ、Xの条件は満たされます。

よって、 $max(L_1,L_2) ≦ X$ が成り立ちます。・・・①

次に、２つの式の右辺について考えます。

この時、 $R_1$ と $R_2$ のうち、小さい値を選択し、その値よりもXが小さければ、Xの条件は満たされます。

よって、 $X ≦ min(R_1, R_2)$ が成り立ちます。・・・②

①、②より、下記式が成り立ちます。

$\displaystyle max(L_1,L_2) ≦ X ≦ min(R_1, R_2)$

よって、今回の問題の答えは $min(R_1, R_2)−max(L_1,L_2)$ で求まりそうです。

しかし、上記だと、線が被っていない場合を考慮できていません。下記図のように、左から、1,3,5,7が与えられた場合を考えてみましょう。

すると、 $max(L_1,L_2)$ = $5$ , $min(R_1, R_2)$ = $3$ となり、 $min(R_1, R_2)−max(L_1,L_2)$ = $3 - 5$ = $-2$ となります。しかし、今回の問題では、被っていない場合は0を出力することが期待されます。

計算結果がマイナスの場合、0に出力するためにmaxを利用します。すると、最終的な答えは $max(0,min(R_1,R_2)−max(L_1,L_2))$ となります。

一応Pythonでの実装を載せます。この短さで解けて感動です。

if __name__ == "__main__":
    l1, r1, l2, r2 = map(int, input().split())
    print(max(0, min(r1, r2) - max(l1, l2)))