リストの左端または右端から解ける問題の数を数えるC++プログラム

要素数 n の配列 A と、ある数値 k があるとします。コンテストには n 問の問題が出題されており、Amal の問題解決能力は k です。Amal は常にリストの左端または右端から問題を選んで解き、難易度が k より大きい問題は解くことができません。そして、左右両端の問題の難易度がどちらも k を超えると、そこで作業をやめます。私たちの課題は、彼が解くことのできる問題の数を数えることです。A[i] は i 番目の問題の難易度を表します。

例えば、入力が A = [4, 2, 3, 1, 5, 1, 6, 4]、k = 4 の場合、出力は 5 になります。まず左端の難易度 4 の問題を解き、続いて右端の難易度 4 の問題を解きます。その後、右端の問題(難易度 6)は解けないため、今度は左側から難易度 2、3、1 の問題を順番に解いていきます。結果として、合計 5 問を解くことができます。

解法の手順

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

n := size of A
l := 0
r := n - 1
for initialize i := 0, when i < n, update (increase i by 1), do:
    if A[i] <= k and l is same as i, then:
       (increase l by 1)
while A[r] <= k, do:
   (decrease r by 1)
if l is same as n, then:
   return n
Otherwise
   return n - 1 - r + l

アルゴリズムの考え方

このアルゴリズムでは、まず左端から順に要素を調べ、難易度が k 以下である限りポインタ l を進めます。これにより、Amal が左側から連続して解ける問題の数が求まります。次に右端からも同様にポインタ r を進め、右側から解ける問題の範囲を特定します。最終的な答えは「左から解けた問題数 l」と「右から解けた問題数(n - 1 - r)」の合計になります。すべての問題が解ける場合(l が n と等しい場合)は、そのまま n を返します。

実装例

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

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A, int k) {
   int n = A.size();
   int l = 0, r = n - 1;
   for (int i = 0; i < n; ++i) {
      if (A[i] <= k && l == i)
         ++l;
   }
   while (A[r] <= k)
      --r;
   if (l == n)
      return n;
   else
      return n - 1 - r + l;
}
int main() {
   vector<int> A = { 4, 2, 3, 1, 5, 1, 6, 4 };
   int k = 4;
   cout << solve(A, k) << endl;
}

入力

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

出力

5