[ARC129] B - Range Point Distance

[ARC129] B - Range Point Distance

syamashi

[Q] https://atcoder.jp/contests/arc129/tasks/arc129_b
AよりBのほうが簡単かもしれない。
1.  Lの最大値と、Rの最小値を常に更新すればいい。
2.  Lmax - Rminで法則がみつかる。

Q. 
3
1 3
2 4
5 6

1.) 1 3 を考える。

1~30 で、それ以外は距離がスコアになっているので、こう。

0 1 2 3 4 5 6 7
===============
1 0 0 0 1 2 3 4 // Lmax = 1, Rmin = 3
最小は 0

2.)2 4 を考える。
0 1 2 3 4 5 6 7
===============
1 0 0 0 1 2 3 4 // Lmax = 1, Rmin = 3
2 1 0 0 0 1 2 3 // Lmax = 2, Rmin = 3
---- max ------
2 1 0 0 1 2 3 4
最小は 0

3.)5 6 を考える。
0 1 2 3 4 5 6 7
===============
1 0 0 0 1 2 3 4 // Lmax = 1, Rmin = 3
2 1 0 0 0 1 2 3 // Lmax = 2, Rmin = 3
5 4 3 2 1 0 0 1 // Lmax = 5, Rmin = 3
---- max ------
5 4 3 2 1 2 3 4
      ^   ^
     [3] [5]
Q. 最小は 1 だけど、どう求める?
A. 
ll dif = Lmax - Rmin = 5-3 = 2
これは、maxをとった配列のindex
max[Lmax] = max[5] = 2
max[Rmin] = max[3] = 2
と合致する。

LmaxRminの中間に近づくほど値が減少する。
その減少度合いは、
ll dis = dif/2 = 1
で求まる。

ll ans = dif - dis = 2 - 1 = 1

実装

int main(){
 cincout();
 
 ll N;
 cin >> N;
 ll up = oo;
 ll down = -oo;
 rep(n, N){
   ll L, R;
   cin >> L >> R;
   chmax(down, L);
   chmin(up, R);
   if (down <= up) cout << 0 << endl;
   else{
     ll dif = down - up;
     ll ans = dif - dif/2;
     cout << ans << endl;
   }
 }
}

https://atcoder.jp/contests/arc129/submissions/27426748

この記事が気に入ったら、サポートをしてみませんか?
気軽にクリエイターの支援と、記事のオススメができます!
তরকারীও রয়েছে
syamashi
非エンジニア。atcoder(highest:1844)/42Tokyo2月1期(pass)/セミリタイア(20190702最終出社)