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

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

解説

この課題におけるポイントは次の 3 つである．

1. 整数列 A, B の共通要素のみを出力できているか．
2. 同じ要素を複数回出力していないか．
3. 結果を昇順で出力できているか．

この課題には様々な解法が存在する．以下では整数列 A, B の各要素の最大値を max(A,B) で表す．

解法 1 (各数が存在するか調べる)

まず，上記ポイントの 3 を達成することを考える．課題の制約より，整数列 A, B の各要素は 1 以上 100 以下である．したがって，1 以上 100 以下の整数 i を順に処理し，出力するかしないかを決定する．このとき，ポイント 2 も達成されている．

ポイント 1 より，その数 i を出力するための条件は，i が A と B の両方に含まれていることである．まず A の各要素を順に調べ，i が出現するか求める．次に B の各要素を順に調べ，i が出現するか求める．そしてその結果に基づき i を出力するか判定する．

この解法の時間計算量は O(max(A, B) (N + M)) である．(つまり，計算時間が max(A, B) (N + M) に比例する．)

解法 2 (解法 1 の高速化)

解法 1 では整数 i が A と B の両方に含まれるかを判定するのに毎回 O(N+M) 時間かかっていた．これを高速化することを考える．

要素数が max(A, B) 程度の大きさの配列 existA[] を用意し，0 で初期化する．整数列 A の各要素 A_j を順に調べ existA[Aj] を 1 にすることを繰り返す．この結果，配列 existA[] は添字の数が A に含まれるのかを表す配列となる．つまり，existA[i] が 1 のとき数 i は A に含まれ，0 のとき数 i は A に含まれないことを指す．B に対しても同様の操作を行う．

これにより，整数 i が A と B の両方に含まれるかを O(1) 時間で判定できるようになる．

この解法の時間計算量は O(N + M + max(A, B))) である．

解答例(C++) はこの解法 2 を実装している．

解法 3 (照らし合わせ)

まず，上記ポイントの 1 を達成することを考える．2 重ループを実装し，整数列 A と B の各要素を順に照らし合わせていく．今 A_i と B_j を照らし合わせていると仮定すると，もし A_i = B_j ならその数は答えに含まれる．

ただし，このままでは，ポイントの 2 と 3 を満たすとは限らない．

そこで，照らし合わせの結果答えに含まれることがわかった数たちを一時的に配列に保存する．次に多くの言語に標準で実装されている sort 関数などを用いて要素を昇順に並べ替える．これでポイントの 3 が達成できる．(配列の大きさに注意すること．)

また，出力する際には，今出力しようとしている要素が直前の要素と異なる場合のみ出力するようにすることで，ポイントの 2 を達成できる．

この解法の時間計算量は O(NM log(NM)) である．

解法 4 (解法 3 の高速化)

解法 3 では A のある要素に着目したあと，同じ数が B にも含まれるか調べるのに，毎回 O(M) 時間かかっていた．これを高速化することを考える．

予め整数列 B をソートしておく．これにより，ある数が B に含まれる個数を二分探索により O(log M) 時間で求められる．

この解法の時間計算量は O(M log(M) + N log(M)) である．

解答例(C++,別解) はこの解法 4 を実装している．

解法 5 (解法 3 の高速化)

予め整数列 A, B をそれぞれソートしておく．

変数 i と j をそれぞれ 0 に初期化し，A[i] ＜ B[j] なら i を 1 加算，A[i] ＞ B[j] なら j を 1 加算することを繰り返す．A[i] と B[j] が等しい場合，その数は答えに含まれる．

ただし，ポイント 2 を満たすよう，実装に注意する必要がある．

この解法の時間計算量は O(N log(N) + M log(M)) である．

なお，この解法はマージソートと呼ばれるソートアルゴリズムと関係がある．