今回は制約が小さいため愚直に実装しても問題ありませんが、応用のためここではより計算量の良い別解をいくつか提示します。計算量はすべて高々\[O((N+M)\log(N+M))\]です。あらかじめ \(A\) と \(B\) をソートしておくものとします。

解法1.

　ある数がソート済みの配列に含まれるか(特にいくつ含まれるか)は二分探索によって \(O(\log M)\) で求められます。C++であればstd::lower_boundとstd::upper_boundが標準で存在するため、これらを用いるだけで良いです。同じ数に対して重複して操作しないように注意してください。

実装例(C++)はこちら

解法2.

　変数 \(i\) と \(j\) をそれぞれ \(1\) に初期化し、\(A_i\lt B_j\) ならば \(i\) をインクリメントし、\(A_i \geq B_j\) ならば \(j\) をインクリメントすることを繰り返します。\(i\gt N\) または \(j\gt M\) となったらそこで終了します。途中で \(A_i=B_j\) となればそれは条件をみたし、逆に条件をみたす数はこのような過程の途中で必ず得られることが容易にわかります。同じ数を重複して出力しないように注意してください。

実装例(C++)はこちら

解法3.

　以下の \(N+M\) 個の「二つ組」からなる列 \(C\) を考えます。

\[ C=((A_1,1),(A_2,1),\dots,(A_N,1),(B_1,2),(B_2,2),\cdots,(B_M,2))\]

　この \(C\) を辞書式にソートし、前から順に見ていったとき、ある数 \(x\) について \((x,1),(x,2)\) という並びが現れたら \(x\) は条件をみたすことがわかります。なおC++であれば「二つ組」およびそのソートはstd::pairを用いて簡潔に実装できます。

実装例(C++)はこちら