C++で最適な除算式を求めるアルゴリズム

問題の概要

正の整数のリストが与えられ、隣接する整数同士で浮動小数点数の除算を行うことを考えます。例えば、[2,3,4] は 2 / 3 / 4 として評価されます。ここで、演算の優先順位を変更するために、任意の位置に任意の個数の括弧を挿入することができます。目的は、計算結果が最大になるように括弧を配置し、その式を文字列形式で返すことです。ただし、式には冗長な括弧を含めてはいけません。

例えば、入力が [1000,100,10,2] の場合、出力は "1000/(100/10/2)" となります。

解法のポイント

この問題には重要な数学的な性質があります。除算の連鎖において結果を最大化するには、最初の数を分子とし、残りのすべての数を分母側にひとまとめにするのが常に最適です。

x1 / x2 / x3 / ... / xn に対して x1 / (x2 / x3 / ... / xn) という括弧を付けると、式は x1 × x3 × x4 × ... × xn ÷ x2 と等しくなります。x1 は必ず分子に現れ、それ以外の各数は分母または分子のどちらかに一度だけ現れるため、x2 以外の数をすべて分子側へ移動させたこの形が理論上の最大値となります。

アルゴリズムの手順

• n := nums 配列のサイズとする
• n が 0 の場合は空文字列を返す
• num := nums[0] を文字列に変換したもの
• n が 1 の場合は num をそのまま返す
• n が 2 の場合は num + "/" + nums[1] を文字列に変換したものを返す(括弧は不要)
• den := 空文字列
• i を 1 から n − 1 までループする:
  • den := den + nums[i] を文字列に変換したもの
  • i が n − 1 でない場合、den := den + "/"
• num + "/(" + den + ")" を返す

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string optimalDivision(vector<int>& nums) {
      int n = nums.size();
      if(n == 0) return "";
      string num = to_string(nums[0]);
      if(n == 1) return num;
      if(n == 2) return num + "/" + to_string(nums[1]);
      string den = "";
      for(int i = 1; i < n; i++){
         den += to_string(nums[i]);
         if(i != n - 1) den += "/";
      }
      return num + "/" + "(" + den + ")";
   }
};
main(){
   vector<int> v = {1000,100,10,2};
   Solution ob;
   cout << (ob.optimalDivision(v));
}

入力

[1000,100,10,2]

出力

1000/(100/10/2)

計算量

配列を一度走査して結果文字列を組み立てるだけなので、時間計算量は O(n)、空間計算量も結果文字列の格納分を含めて O(n) です。要素数が増えても線形時間で処理できる、非常に効率的な解法といえます。