C++でリストをk個の連続増加要素からなるサブリストに分割できるか判定するプログラム

問題概要

数値のリスト nums と整数 k が与えられたとします。このとき、「リストを、それぞれがちょうど k 個の連続的に増加する値を含むサブリストに分割できるかどうか」を判定するのが本記事のテーマです。

たとえば、入力が nums = [4, 3, 2, 4, 5, 6]、k = 3 の場合、出力は True になります。リストを [2, 3, 4] と [4, 5, 6] に分割でき、どちらのサブリストも3つの要素を持ち、値が1ずつ増加しているためです。

解法の考え方

この問題は、各数値の出現回数をマップ(連想配列)で管理し、貪欲法でグループを組み立てることで解けます。ポイントは、「自分より1小さい値がマップに存在しないキー」を探すことです。そのような値は既存の連続列の後ろに付けられないため、必ず新しいグループの先頭にならなければなりません。

具体的には、次の手順で処理を進めます。

1. マップを定義する:キーに数値、値に出現回数を格納します。
2. 出現回数をカウントする:リスト内の各要素 it について、m[it] を1ずつ増やします。
3. フラグ ok を true で初期化する。
4. マップが空でなく、かつ ok が true の間、以下を繰り返します:
   • ok を false に設定します。
   • マップ内の各キーと値のペア it について調べます:
     • (it.key − 1) がマップに存在しない場合(= グループの先頭候補):
       • flag を true に設定します。
       • i を it.key から it.key + k − 1 まで動かし、すべての i がマップに存在するか確認します。1つでも欠けていれば flag を false にします。
       • flag が true のままなら、it.key から it.key + k − 1 までの各値のカウントを1減らし、カウントが0になったキーはマップから削除します。その後 ok を true にして内側のループを抜けます。
5. 結果を返す:マップが空になっていれば true(分割成功)、要素が残っていれば false を返します。

この手順では、常に「先頭になり得る値」から順に k 個ずつ消費していくため、重複する値があっても各コピーが正しく別グループの先頭として扱われ、分割の可否を正確に判定できます。

C++での実装例

以下は、上記のアルゴリズムを実装したC++のコードです。

#include<bits/stdc++.h>
using namespace std;
class Solution {
    public:
        bool solve(vector<int> nums, int k) {
            map <int, int> m;
            for(auto& it : nums){
                m[it]++;
            }
            bool ok = true;
            while(m.size() && ok){
                ok = false;
                for(auto& it : m){
                    if(!m.count(it.first - 1)){
                        bool flag = true;
                        for(int i = it.first; i <= it.first + k - 1;i++){
                            if(!m.count(i))
                                flag = false;
                        }
                        if(flag){
                            for(int i = it.first; i <= it.first + k - 1;i++){
                                m[i]--;
                                if(m[i] == 0)
                                    m.erase(i);
                            }
                            ok = true;
                            break;
                        }
                    }
                }
            }
            return m.empty();
        }
};
main(){
    vector<int> v = {4, 3, 2, 4, 5, 6};
    Solution ob;
    cout << ob.solve(v, 3);
}

コードのポイント

• map<int, int> を使うことで、各値の出現回数をキーの昇順に自動的に管理できます。
• m.count(it.first - 1) が0のとき、そのキーは連続列の先頭候補です。
• k 個そろった時点でまとめてカウントを減らし、0になったキーを erase で削除します。
• すべての要素を消費できていれば m.empty() が true を返します。

実行結果

入力

{4, 3, 2, 4, 5, 6}

出力

1

出力が 1(true)となり、リストを [2, 3, 4] と [4, 5, 6] に分割できることが確認できました。