図解解説シリーズ
競技プログラミングを始めたばかりでAtCoderの解説やJOIの解説ではいまいちピンと来ない…という人向けに、図解を用いて解説を行います。
問題文
ARC129 B - Range Point Distance
図解解説
問題文を整理するために、具体的な数字を用いて、図示して考えてみます。
そこで、問題文に示されているdist(l,r,x)に具体的な数字を入れて考えます。まずl=2,r=4として、◯をl、●をrとして数直線に表したものが左上の図になります。xの値がlとrの間にあれば、答えは0（dist(2,4,2)=dist(2,4,3)=dist(2,4,4)=0）となります。また、xの値がl=2より小さければ、例えばx=0のときdist(2,4,0)=2-0=2（l>xのときdist(l,r,x)=l-x）となります。一方、xの値がr=4より大きければ、例えばx=5のときdist(2,4,5)=5-4=1（x>rのときdist(l,r,x)=x-r）となります。
従って、範囲が１つのとき、max(dist(2,4,x))を最小にするxは、2<=x<=4となる値を選べば良いので、答えは必ず０になります。
範囲が２つの場合を考えます。
【２つの範囲が重なっているとき】max(dist(1,3,x),dist(2,4,x))を最小にするxは、２つの範囲が重なっている値、つまりx=2（またはx=3）を選べば、dist(1,3,2)=0、dist(2,4,2)=0となり、答えは0になります。
【２つの範囲が重なっていないとき】max(dist(1,3,x),dist(5,7,x))を最小にするxを考えます。x=2からx=6を順次あてはめて計算を行うと、x=4のとき最小になることがわかります。つまり、左の範囲のr=3と右の範囲のl=5の中央値（x=4）が求めるxの値になり、答えは1となります。ここで、中央値が整数にならない場合を考えます。例えば、max(dist(0,2,x),dist(5,7,x))のときは、そのまま計算するとx=3.5になってしまいます。xが整数に反しますので、xの値を切り下げたx=3または、xの値を切り上げたx=4が求めるxの値となり、答えは2となります。
それでは、範囲が多くなったとき、どのように考えればよいでしょうか。
図のように、２つの場合で考えます。最初の例では、範囲が離れていますので、x=8で試しに計算を行なっています。すると、x=8を基準にして、左側にある範囲については、rの値を使ってdist(l,r,x)=x-rのように値を計算することになります。一方、右側にある範囲については、lの値を使ってdist(l,r,x)=l-xのように値を計算することになります。最終的に答えに影響する計算は、最小のrを含む範囲と、最大のlを含む範囲となります。さらによく観察すると、答えは最大のlと最小のrの距離の半分となります。答えが小数にはなりませんので、小数になる場合は求めた値を切り上げたものが答えになります。範囲が２つで離れているときの例でも同様に求めることができることを確認してみてください。
次の例では、すべての範囲が重なっています。このとき、先ほどの例で注目した最大のlと最小のrの位置関係を確認してみると、「最大のl<=最小のr」となっています。このときの答えは0ですので、最大のlと最小のrの大小関係に注意しながらプログラムを作成すればよいことがわかります。
解答例
最終的に作成したプログラムは以下の通りです。
前述の通り、すべての範囲から、最小のrと最大のlをまずは求めておきます。その後、最小のrと最大のlの大小関係から答えを求めます。
「最大のl<=最小のr」のときは、すべての範囲が重なっているので、答えは0になります。一方、「最大のl>最小のr」のときは、最大のlと最小のrの距離の半分（小数値となる場合は切り上げ）となります。
import math
N = int(input())
mxL = -float('inf')
mnR = float('inf')
for i in range(N):
l,r = map(int,input().split())
mxL = max(mxL,l)
mnR = min(mnR,r)
if mxL<=mnR:
print(0)
else:
tmp = math.ceil(abs(mxL-mnR)/2)
print(tmp)