JOI 一次予選 2020 (第 1 回) C - マージ (5Q, 難易度 3)

マージソートのマージの部分を実装する問題ですね。
添字を順に進めていくような処理を実装します！　この実装は、のちにしゃくとり法を学ぶ際の参考にもなります。

• 問題へのリンク

問題概要

制約

• 

解法

問題文が複雑で、何をすればいいのかを理解するのが大変かもしれないですね。

一般に、数列 の先頭の要素を削除していく処理は実装が大変です (なお、数列を deque で実装するとか、数列を reverse して末尾から削除していくような実装をするなどの別解はあります)。

そこで、代わりに、数列 上の添字 と、数列 上の添字 を管理することにします。これらは「今この添字のある位置が疑似的に数列の先頭になっています」を表しています。

たとえば、上図のような状況を考えます。数列 の左 2 個 (2, 4) と、数列 の左 1 個 (3) がすでに削除されて、数列 に格納されている状態とします。

次のステップでは、数列 の真の先頭の要素 (疑似的に値 A[2] = 7) と、数列 の先頭の要素 (疑似的に値 B[1] = 8) とを比較します。A[2] の方が小さいので、A[2] を数列 に push して、 の添字 を 1 進めます。

このような処理を、添字 がそれぞれ数列 の終端に到達するまで繰り返せばよいでしょう。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < M; ++i) cin >> B[i];
    
    vector<int> C;
    int i = 0, j = 0;  // A 側の先頭の添字と B 側の先頭の添字
    while (i < N || j < M) {
        if (i == N) {
            // A 側が終端に達していたら B 側を入れて、B 側の添字 j を進める
            C.push_back(B[j]);
            ++j;
        } else if (j == M) {
            // B 側が終端に達していたら A 側を入れて、A 側の添字 i を進める
            C.push_back(A[i]);
            ++i;
        } else if (A[i] < B[j]) {
            // A の方が小さいとき、A 側を入れて、A 側の添字 i を進める
            C.push_back(A[i]);
            ++i;
        } else {
            // B の方が小さいとき、B 側を入れて、B 側の添字 j を進める
            C.push_back(B[j]);
            ++j;
        }
    }
    
    // 出力
    for (int i = 0; i < N + M; ++i) cout << C[i] << endl;
}