この問題は、ソースコードを公開に設定しているので、
暇な人は初めてこの問題に取り組む人の為に
分かりやすいソースコードを提出してくださると助かります。
二分探索
ある条件を満たす最小の数等を求めるときに使いますが、
汎用性が高く、覚えて損無し覚えず損ばかりの考え方です。
たとえば、左から順番に小さい順に並べられたデータがN個あるとします。
この中から T以下の値の個数を求めるアルゴリズムを考えます。
単純にデータの i番目の値がTより小さいかを判断し、
Tより大きくなったらその時の i-1 を出力すれば正しい結果が求められます。
この考え方を 線形探索 と呼びます。たぶん。
しかし、この解法を用いると、最大N回の判断が必要になってしまいます。
更に、この処理をM回行うとすると、最大 M*N回判断が必要になることが分かります。
ここで注目するべきなのは、
a番目の値がTより大きかった場合、
数は小さい順に並んでいるため、
(a < i) である i番目の値は全てTより大きいのが分かる
という点です。
当然その逆も然り、
a番目の値がTより小さかった場合、
数は小さい順に並んでいるため、
(i < a) である i番目の値は全てTより小さいのが分かる
といえます。
このことを利用すると、最大の判断回数を大きく減らすことが出来ます。
最初に1 ~ N番地の真ん中の番地(N/2番地)の値を見て、
大きかったら1 ~ N/2の真ん中の番地の値を見る、
小さかったらN/2 ~ Nの真ん中の番地の値を見る、
を繰り返していくことによって、
探索の対象となる範囲を半分ずつに削ることができます。
このような考え方を、二分探索と呼びます。
具体的な疑似ソースを以下に示します。
探索の対象となる範囲の左端の番地を始まりの番地に、右端の番地を終わりの番地に設定。
while( 左端の番地 < 右端の番地 ){
調べる番地 = (左端の番地 + 右端の番地)/2 ;
if( 調べた番地の値がＴより大きい ){
右端の番地 = 調べた番地 - 1 ;
}
else {
左端の番地 = 調べた番地 + 1 ;
}
}
当然ですが、上記のソースは今回の問題に対しての例であり、
問題によっては上記のソースに対して臨機応変に処理を書き換える必要があります。
ソースで覚えるのではなく、ソースがどんな動作を行っているのかを理解してください。
分からないことが有れば各々の先輩に聞いてください。
それでは、以下の問題を解いてみましょう。
問題
N個の整数データと、M個の命令が与えられます。
データは与えられる順に、1,2,3, ... ,N 個目と表します。
データは小さい順にソートされています。
命令は以下のようになっています。
T
この命令では、Tが入力されるので、
与えられたデータの中に、T以下の値がいくつあるかを出力してください。
詳しくは、入出力例を参考にしてください。
制約
- 1 ≦ N ≦ 1,000,000
- 1 ≦ M ≦ 100,000
- 0 ≦ Datai , T ≦ 1,000,000,000
- Datai ≦ Datai+1
部分点
配点の20%分は N,M ≦ 1000 を満たします。
これは、線形探索でTLEにならない範囲です。
入出力形式
入力形式
N Data1 Data2 ... DataN M T1 T2 .. .. .. TM
出力形式
命令毎に、T以下の値の数を出力し改行してください。
入出力例
入力例
5 10 20 30 40 50 3 20 35 8
出力例
2 3 0
一つめの命令では、20 が与えられます。
20 以下の値は 10 , 20 なので 2 を出力します。
二つめの命令では、35 が与えられます。
35 以下の値は 10 , 20 , 30 なので 3 を出力します。
三つめの命令では、8 が与えられます。
8 以下の値は一つもないので 0 を出力します。