[AtCoder] ABC 077 C – Snuke Festival

2019年5月10日

問題

方針

二分探索

整列された配列に対してある値より大きいまたは小さいものの個数を求めるには、二分探索を使って求めることができます。C++ には “lower_bound" と “upper_bound" があるのでその二つを求めることができます。これらの詳細については、lower_boundとupper_boundの使い方を参照すると良いと思います。

• ある値 \( \mathrm{key} \)より小さい配列 \( \mathrm{A} \) の要素の個数 \( n \) を求める場合

auto Iter = lower_bound(A.begin(), A.end(), key);
long n = Iter - A.begin();

• ある値 \( \mathrm{key} \)より大きい配列 \( \mathrm{C} \) の要素の個数 \( n \) を求める場合

auto Iter2 = upper_bound(C.begin(), C.end(), key);
long n = B.end() - Iter;

基準値を考える

どのパーツを基準にして考えるかですか、答えから言うと、中部のパーツを基準にして二分探索を行えば良いです。

例えば、上部のパーツを基準にして考えると、\( A_i \) を固定して、次に、\( A_i < B_j \) を満たす全ての \( B_j \) を基準にして、配列 \( C \) を二分探索する必要があります。

一方で、中部のパーツを基準に対して考えると、\( B_i \) を固定して、配列 \( A \) に対して \( B_i \) よりも小さい要素の個数を求め、配列 \( C \) に対して \(B_i \) よりも大きい要素の個数を求めればよいことが分かります。

コード

真ん中を固定して計算量を減らすという問題は他のも出てくると思います。