2018年に開催されたICPCアジア地区予選横浜大会の出題問題より、いくつかの典型的な実装手法とアルゴリズムの考え方を解説します。

1. 文字列と数値の混合ソート

文字列中に含まれる数値とアルファベットを個別に識別し、辞書順および数値の大きさに基づいた比較を行う問題です。主なロジックは以下の通りです。

• 両文字列が完全に一致する場合は対象外とする。
• 数値の出現位置を比較し、先に数値が現れた方を優先する。
• 数値同士を比較し、値が小さい方を優先する。
• 数値以外の文字は通常の辞書順で比較する。
• 前方の文字列が後方の接頭辞である場合は、前方を優先する。

bool compareStrings(const string& lhs, const string& rhs, const string& target) {
    if (lhs == target) return false;
    
    int l = 0, r = 0;
    while (l < lhs.size() && r < target.size()) {
        if (isdigit(lhs[l]) && !isdigit(target[r])) return true;
        if (!isdigit(lhs[l]) && isdigit(target[r])) return false;

        if (isdigit(lhs[l])) {
            long long valL = 0, valR = 0;
            while (l < lhs.size() && isdigit(lhs[l])) valL = valL * 10 + (lhs[l++] - '0');
            while (r < target.size() && isdigit(target[r])) valR = valR * 10 + (target[r++] - '0');
            if (valL != valR) return valL < valR;
        } else {
            if (lhs[l] != target[r]) return lhs[l] < target[r];
            l++; r++;
        }
    }
    return lhs.size() < target.size();
}

2. 等差数列の最長部分列

与えられた数列から要素を選び、最長の等差数列を作成する問題です。動的計画法（DP）を用いて、末尾2要素を状態として管理します。

int solveArithmetic(vector<int>& nums) {
    int n = nums.size();
    sort(nums.begin(), nums.end());
    vector<vector<int>> dp(n, vector<int>(n, 2));
    int maxLen = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            int diff = nums[i] - nums[j];
            int prevVal = nums[j] - diff;
            auto it = lower_bound(nums.begin(), nums.end(), prevVal);
            if (it != nums.end() && *it == prevVal) {
                int k = distance(nums.begin(), it);
                dp[j][i] = max(dp[j][i], dp[k][j] + 1);
            }
            maxLen = max(maxLen, dp[j][i]);
        }
    }
    return maxLen;
}

3. 緊急避難時間のシミュレーション

避難者が出口に到達するまでの時間を算出し、出口が混雑する場合の待ち時間を考慮する問題です。各人の到達時間をソートし、時間が重複した場合には順次プラス1秒ずつ加算していくことで最終的な避難完了時刻を算出します。

int calculateEvacuation(int R, int S, vector<pair<int, int>>& pos) {
    vector<int> times;
    for (auto& p : pos) {
        int t = (R - p.first + 1) + abs(p.second - S);
        times.push_back(t);
    }
    sort(times.begin(), times.end());
    for (size_t i = 0; i + 1 < times.size(); ++i) {
        if (times[i + 1] <= times[i]) {
            times[i + 1] = times[i] + 1;
        }
    }
    return times.back();
}