JOI logo
第20回日本情報オリンピック　一次予選(第3回)

2020年11月22日
情報オリンピック日本委員会

問題
３ 		　　比較 (Comparison)　(配点 100点)
　　時間制限 : 2 sec / メモリ制限 : 1024 MB

解説

すべての (i, j) の組について Ai ≦ Bj であるかどうかを調べればよい． 時間計算量は O(NM) である．(解答例(C++))

また i を固定すると，配列 B で Ai 以上の数がいくつあるかを求める問題になる． これは配列 B を事前にソートしておくと，二分探索により時間計算量 O(log M) で求めることができる． この解法の時間計算量は O((N+M) log M) である．(解答例(C++,別解))