C++で解く：銀行の金庫から回収できる紙幣の最大枚数を求めるアルゴリズム

3つの整数 k、l、m と、n 個の要素を持つ配列 A が与えられているとします。ある強盗が銀行強盗に失敗しましたが、銀行内のすべての金庫を開けることには成功していました。そこへ別の人物が現れ、この失敗した強盗に便乗して、金庫からお金を盗み出そうと考えます。

金庫は一列に並んでおり、すべての金庫には合計で n 枚の紙幣が残っています。i 番目の紙幣は A[i] 番目の金庫の中にあります。現在、銀行の従業員は k 番目の金庫におり、警備員は2名配置されています。1人目の警備員は l（l < k）番目の金庫、すなわち従業員の左側を警備しており、もう1人の警備員は m（m > k）番目の金庫、すなわち右側を警備しています。2人の警備員は一切動きません。

この人物は毎秒ごとに、「現在いる金庫の紙幣をすべて回収する」か「隣接する金庫へ移動する」のいずれかの行動を選択できます。ただし、窃盗の容疑をかけられるリスクがあるため、警備員が見張っている金庫には決して立ち入ることができません。この条件下で、この人物が集められる紙幣の最大枚数を求めるのが本問題です。

たとえば、k = 5、l = 3、m = 7、A = [4, 7, 5, 5, 3, 6, 2, 8] という入力の場合、出力は 4 になります。これは、2人の警備員の間（4番目〜6番目の金庫）に存在する紙幣がちょうど4枚であるためです。

解法のステップ

この問題を解くために、以下の手順に従います。

• カウンター c1 を 0 で初期化します。
• 配列 A の各要素 x について、「x が l より大きく、かつ m より小さい」という条件を満たす場合に c1 を1増やします。
• 最終的な c1 の値を結果として返します。

ここでのポイントは、警備員が動かないため、2人の警備員の間にある金庫（l < x < m）にはいつでも自由にアクセスできるという点です。したがって、複雑なシミュレーションは不要で、その範囲内に存在する紙幣を単純に数え上げるだけで答えが得られます。

c1 := 0
n := size of A
c1 := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
    x := A[i]
    if x > l and x < m, then:
        (increase c1 by 1)
return c1

C++による実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(int k, int l, int m, vector<int> A){
   int c1 = 0, x;
   int n = A.size();
   c1 = 0;
   for (int i = 0; i < n; i++){
      x = A[i];
      if (x > l && x < m)
         c1++;
   }
   return c1;
}
int main(){
   int k = 5;
   int l = 3;
   int m = 7;
   vector<int> A = { 4, 7, 5, 5, 3, 6, 2, 8 };
   cout << solve(k, l, m, A) << endl;
}

入力

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

出力

4