ABC199 B 解答

B - Intersection（37）

問題文

長さ N の数列 A = (A1, A2, A3, … , AN ), B = ( B1, B2, B3, … , BN)が与えられます。
以下の条件を満たす整数 x の個数を求めてください。
1 ≤ i ≤ N を満たす全ての整数 i について Ai ≤ x ≤ Bi

制約

1 ≤ N ≤ 100
1 ≤ Ai ≤ Bi ≤ 1000
入力に含まれる値は全て整数

考察

条件を満たす数字を求めていきます。

色々な解き方があると思いますが、できる限り工夫をせずにありのままで解いていきたいと思います。

ということで、各条件に含まれる数を積み立てていきましょう。

例を挙げて見ます。入力例１です。

2
3 2
7 5

１つ目の条件は3~7ですので、3~7にブロックを積みます。２つ目は2~5ですね。同じようにブロックを積みます。その結果が次のようになります。

このブロックが条件の個数まで積み上がっている数字は全部の条件をくぐり抜けた猛者ということになります。つまりこの子達が何個あるかを出力してあげればACがもらえます。

答えは求まりましたが、計算量を確認して見ましょう。

最も計算時間がかかるのは、条件が100個ありその全てが1~1000のときですね。この場合には全部一つずつ見ていくと、100と1000の掛け算で10^5です。これなら全然間に合います。

こんな感じで実装しましょう。

実装

 #include <bits/stdc++.h> #define  rep(i,n) for(int i=0;i<n;++i) #define  reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
   int n;
   cin >> n;
   vector<int> v(1001,0);
   vector<int> a(n),b(n);
   rep(i,n) cin>>a[i];
   rep(i,n) cin>>b[i];

   rep(i,n)
   {

       for(int j =a[i];j<=b[i];++j)
       {
           ++v[j];
       }
   }
   int ans = 0;
   reps(i,1,1001) 
   {
       if(v[i]==n) ++ans;
   }
   cout << ans << endl;
   return 0;
}

あとがき

できる限り、そのままやることで答えを求めました。もう少し工夫をするなら次のような図になると思います。

この場合、下限となるAの最大値と、上限となるBの最小値の間の数が満たすことになります。

ans = min(B) - max(A) +1

ですかね。minとmaxの大きさが逆転して、ansがマイナスだったら一個もこの通路を抜けられないため答えは0となります。