C++で配列を回文にするために必要な最小マージ操作回数を求める方法

問題概要

この問題では、n個の正の整数からなる配列 arr[] が与えられます。私たちのタスクは、配列を回文にするために必要なマージ操作の最小回数を見つけることです。

回文配列とは、回文文字列と同様に、インデックス i と n-1-i の位置にある要素が同じ値である配列のことを指します。

例

{5, 1, 7, 2, 7, 1, 5}

この配列は左右対称になっているため、回文配列です。

問題の詳細

配列に対して操作を行い、回文の状態にする必要があります。配列に対して有効な唯一の操作はマージ操作で、これはインデックス i と i+1 の隣接する2つの要素を足し合わせて1つにまとめる操作です。

与えられた配列を回文にするために必要な、この操作の最小回数を返すことが求められます。

具体例で問題を理解しましょう。

入力

arr[] = {4, 1, 7, 6, 1, 5}

出力

2

説明

この場合、2回のマージ操作が必要です。

まず、インデックス0と1の要素(4と1)をマージすると、配列は {5, 7, 6, 1, 5} になります。

次に、インデックス2と3の要素(6と1)をマージすると、配列は {5, 7, 7, 5} となり、回文が完成します。

解法アプローチ

この問題に対するシンプルな解法は、ツーポインター法を使うことです。配列の先頭を指す start と、末尾を指す end の2つのポインターを用意します。両方のポインターが出会ったとき(start == end)、その時点で配列は回文になっています。

start と end のポインターを動かしながら、以下の条件に基づいて操作を実行します。

• arr[start] == arr[end] の場合: 現在の位置で回文の条件を満たしているため、両方のポインターを内側へ移動します。つまり start++ と end-- を実行します。

• arr[start] > arr[end] の場合: 末尾側の値が小さいため、end 側でマージ操作を実行し、mergeCount を1増やします。

• arr[start] < arr[end] の場合: 先頭側の値が小さいため、start 側でマージ操作を実行し、mergeCount を1増やします。

start と end が出会った時点で、累積したマージ回数を結果として返します。

この解法の動作を示すプログラムは以下の通りです。

サンプルコード

#include <iostream>
using namespace std;
int findMergeCount(int arr[], int n){
   int mergeCount = 0;
   int start = 0;
   int end = n-1;
   while(start <= end){
      if (arr[start] == arr[end]){
         start++;
         end--;
      }
      else if (arr[start] > arr[end]){
         end--;
         arr[end] += arr[end+1] ;
         mergeCount++;
      } else {
         start++;
         arr[start] += arr[start-1];
         mergeCount++;
      }
   }
   return mergeCount;
}
int main(){
   int arr[] = {4, 1, 7, 6, 1, 5};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"配列を回文にするために必要なマージ操作の最小回数は "<<findMergeCount(arr, n);
   return 0;
}

出力

配列を回文にするために必要なマージ操作の最小回数は 2

まとめ

このアルゴリズムは、両端から中央に向かってポインターを移動させながら、値が小さい側を隣接要素とマージしていくことで、配列を回文に変換します。計算量は O(n) であり、非常に効率的な解法です。マージ操作のたびに配列の要素が更新されるため、実際の回文化の過程も正確にシミュレートできる点がポイントです。