C++で解くビトニック数列への要素挿入クエリの解法

この問題では、ビトニック数列とQ個のクエリが与えられます。各クエリには1つの整数が含まれており、その整数を数列に挿入した後のビトニック数列の長さを毎回出力することが求められます。さらに、すべてのクエリの処理が終わった後に、最終的なビトニック数列を出力します。

問題の概要

ここでは、ビトニック数列と、それぞれ追加対象の整数を1つ含むQ個のクエリが与えられます。各クエリの要素を順番に数列へ追加し、その都度ビトニック数列の長さを返します。そして、すべてのクエリが完了した時点で、最終的なビトニック数列を出力します。

ビトニック数列とは

ビトニック数列とは、ある点（ビトニックポイントと呼ばれます）まで単調に増加し、その後は減少していく特殊な形式の数列です。

例：1, 5, 6, 8, 9, 7, 5, 2

問題を理解するための具体例

入力

bseq = {1, 4, 6, 5, 2, 1}
Q = 2
Query = {5, 6}

出力

7 7
{1, 4, 5, 6, 5, 2, 1}

解説

1つ目のクエリでは、挿入する値は5です。5は数列の増加部分に挿入できるため、数列は{1, 4, 5, 6, 5, 2, 1}となり、長さは7になります。

2つ目のクエリでは、挿入する値は6ですが、6は現在の最大値であるため挿入できません。よって、6は挿入されません。

最終的な数列は{1, 4, 5, 6, 5, 2, 1}となり、長さは7です。

解法アプローチ

この問題を解くためには、ビトニック数列を2つの集合に分割します。1つは最大値までの増加部分に対応する集合、もう1つは減少部分に対応する集合です。

挿入対象の各要素については、以下のケースが考えられます。

ケース1（要素が最大値より大きい場合）

要素を増加側の集合の末尾に追加し、最大値を更新します。

ケース2（要素が最大値より小さい場合）

まず増加側の集合に同じ値の要素が存在しないかを確認し、存在しない場合はそこに挿入します。すでに存在する場合は、減少側の集合を調べ、追加できるかどうかを判定します。

ケース3（要素が最大値と等しい場合、または増加・減少の両方の集合に同じ値が存在する場合）

その要素は追加できないため、挿入を行いません。

各クエリの処理が完了するごとに、両方の集合の長さを合計することで、ビトニック数列の長さを求めます。

length(bseq) = length(incSet) + length(decSet)

すべてのクエリが終了したら、incSet（増加側の集合）を出力してからdecSet（減少側の集合）を出力することで、最終的なビトニック数列を構成します。

ソリューションの動作を示すプログラム

サンプルコード

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

void calcBitonicSeqLenth(int bSeq[], int n, int query[], int Q){
    int maxVal = INT_MIN;
    for (int i = 0; i < n; i++)
        maxVal = max(maxVal, bSeq[i]);
    set <int> incSet, decSet;
    incSet.insert(bSeq[0]);
    decSet.insert(bSeq[n - 1]);
    for (int i = 1; i < n; i++)
        if (bSeq[i] > bSeq[i - 1])
            incSet.insert(bSeq[i]);
    for (int i = n - 2; i >= 0; i--)
        if (bSeq[i] > bSeq[i + 1])
            decSet.insert(bSeq[i]);
    decSet.erase(decSet.find(maxVal));
    for (int i = 0; i < Q; i++) {
        if (maxVal <= query[i]) {
            maxVal = query[i];
            incSet.insert(query[i]);
        }
        else {
            if (incSet.find(query[i]) == incSet.end())
                incSet.insert(query[i]);
            else
                decSet.insert(query[i]);
        }
        int length = incSet.size() + decSet.size();
        cout<<"For query "<<(i+1)<<": The length of Bitonic Sequence is "<<length<<endl;
    }
    cout<<"The Bitonic Sequence at the end of all queries is : ";
    set<int>::iterator it;
    for (it = incSet.begin(); it != incSet.end(); it++)
        cout<<(*it)<<" ";

    set<int>::reverse_iterator revIt;

    for (revIt = decSet.rbegin(); revIt != decSet.rend(); revIt++)
        cout<<(*revIt)<<" ";
}
int main(){
    int bSeq[] = { 1, 4, 6, 5, 2, 1 };
    int n = sizeof(bSeq) / sizeof(bSeq[0]);
    int Q = 2;
    int query[] = { 6, 5 };
    calcBitonicSeqLenth(bSeq, n, query, Q);
    return 0;
}

出力

For query 1: The length of Bitonic Sequence is 6
For query 2: The length of Bitonic Sequence is 7
The Bitonic Sequence at the end of all queries is : 1 4 5 6 5 2 1

クエリ1の処理後はビトニック数列の長さが6、クエリ2の処理後は7となり、すべてのクエリ終了後の最終的なビトニック数列は「1 4 5 6 5 2 1」になります。