鉄道駅の列車スケジューリングシステムでは、入口軌道と出口軌道の間にN本の平行軌道が配置されています。各列車は入口から任意の軌道を選択して進入し、最終的に出口から離脱します。例えば、入口で{8, 4, 2, 5, 3, 9, 1, 6, 7}の順番で待機している9本の列車がある場合、これらを番号の降順で出口から離脱させるために必要な最小限の平行軌道数を求める必要があります。

入力形式

最初の行に整数N (2 ≤ N ≤ 10⁵)が与えられ、次の行に1からNまでの整数の順列が与えられます。数字はスペースで区切られています。

出力形式

入力された列車を番号の降順でスケジュールするために必要な最小限の軌道数を一行に出力します。

まず、非効率なアプローチを見てみましょう。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> tracks;
    int trainCount, currentTrain;
    cin >> trainCount;
    int maxValue = 0;
    
    for (int i = 0; i < trainCount; i++) {
        cin >> currentTrain;
        
        if (i == 0) {
            tracks.push_back(currentTrain);
            maxValue = currentTrain;
            continue;
        }
        
        if (currentTrain > maxValue) {
            tracks.push_back(currentTrain);
            maxValue = currentTrain;
        } else {
            if (tracks.size() == 1) {
                tracks[0] = currentTrain;
                maxValue = currentTrain;
            } else {
                sort(tracks.begin(), tracks.end());
                for (int j = 0; j < tracks.size() - 1; j++) {
                    if (currentTrain > tracks[j] && currentTrain < tracks[j+1]) {
                        if (maxValue == tracks[j+1]) {
                            maxValue = currentTrain;
                        }
                        tracks[j+1] = currentTrain;
                        break;
                    }
                }
            }
        }
    }
    
    cout << tracks.size();
    return 0;
}

この基本的なアプローチでは、各軌道の末端値を配列に格納し、現在の列車が最大値より大きい場合は新しい軌道を開設し、そうでない場合は最も近い値を検索して置換します。しかし、この方法では一部のテストケースで時間制限を超えてしまいます。

そこで、セット（デフォルトで昇順ソートされる）を使用した効率的な解決策を以下に示します。

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> trackEndings;
    int trainCount, currentTrain;
    cin >> trainCount;
    
    for (int i = 0; i < trainCount; i++) {
        cin >> currentTrain;
        
        if (i == 0) {
            trackEndings.insert(currentTrain);
            continue;
        }
        
        auto it = trackEndings.lower_bound(currentTrain);
        if (it != trackEndings.end()) {
            trackEndings.erase(it);
        }
        
        trackEndings.insert(currentTrain);
    }
    
    cout << trackEndings.size();
    return 0;
}

この解決策では、lower_bound()メソッドが入力値より大きい最小値を返します。これにより、現在の列車を配置できる最適な軌道を効率的に見つけることができます。見つかった場合はその軌道の末端値を更新し、見つからない場合は新しい軌道を追加します。このアプローチにより、O(n log n)の時間計算量で問題を解決できます。