C++で警察官が泥棒を捕まえる問題を貪欲法で解く方法

問題概要

この問題では、n個の要素からなる配列が与えられます。配列の各要素には「P（警察官）」または「T（泥棒）」のいずれかが格納されており、1人の警察官は1人の泥棒を捕まえることができます。ただし、警察官は自分の位置から距離k以内にいる泥棒しか逮捕できません。この制約のもとで、警察官たちが捕まえられる泥棒の最大数を求めるのが目的です。

入出力例

入力 −

array = {T, P, P, P, T, T, T}
K = 2.

出力 − 3

説明 − ここでは、各警察官がそれぞれ泥棒を1人ずつ捕まえます。

インデックス1のPが、インデックス0のTを逮捕。
インデックス2のPが、インデックス4のTを逮捕。
インデックス3のPが、インデックス5のTを逮捕。

これは、警察官が自分から距離2以内にいる泥棒を捕まえられるため許容される動作です。

解法のアプローチ

この問題を解くには貪欲アルゴリズム（greedy algorithm）を活用します。発想としては、「警察官に最も近い泥棒を優先的に捕まえる」方法と「逆に最も遠い泥棒を捕まえる」方法の2通りが考えられます。しかし、どちらの戦略でも、警察官がある一定の距離にいる泥棒を捕まえなければならないケースが存在するため、常に最適解が得られるとは限りません。

そこで、以下のようなアルゴリズムを採用すると、最も有望な結果を得ることができます。

まず、最初の警察官と最初の泥棒のインデックスから処理を開始します。|index(P1) − index(T1)| ≤ k が成立すれば、その泥棒は逮捕可能なので、次の警察官・泥棒のペアを確認します。条件を満たさない場合は、min(p, t)、すなわち現在見ているインデックスが小さい方のポインタを1つ進めて、次の警察官または泥棒の位置を確認します。この判定をすべての警察官と泥棒に対して繰り返し、最後に捕まえた泥棒の総数を出力します。

C++での実装例

上記のアルゴリズムを実装したプログラムが以下の通りです。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int policeThief(char arr[], int n, int k){
    int caught = 0;
    vector<int> thieves;
    vector<int> policemen;
    for (int i = 0; i < n; i++) {
        if (arr[i] == 'P')
            policemen.push_back(i);
        else if (arr[i] == 'T')
            thieves.push_back(i);
    }
    int thief = 0, police = 0;
    while (thief < thieves.size() && police < policemen.size()) {
        if (abs(thieves[thief] - policemen[police]) <= k) {
            caught++;
            thief++;
            police++;
        }
        else if (thieves[thief] < policemen[police])
            thief++;
        else
            police++;
    }
    return caught;
}
int main(){
    int k, n;
    char arr2[] = {'P', 'T', 'T', 'P', 'P', 'T', 'T', 'T', 'T', 'P' };
    k = 2;
    n = sizeof(arr2) / sizeof(arr2[0]);
    cout << "Maximum number of thieves that can be caught by police is :"<<policeThief(arr2, n, k);
    return 0;
}

実行結果

Maximum number of thieves that can be caught by police is :4

計算量の分析

• 時間計算量： O(n) — 配列を一度だけ走査し、警察官と泥棒の位置を先頭から順に比較しながら処理を進めるため、要素数に対して線形時間で完了します。
• 空間計算量： O(n) — 警察官と泥棒のインデックスをそれぞれ別のベクターに格納して管理します。