C++で数値を表現するために必要な最小の演算子数を求めるアルゴリズム

問題の概要

正の整数 x が与えられ、「x (op1) x (op2) x (op3) x …」という形式の式を作ることを考えます。ここで op1、op2 などの各演算子には、加算（+）、減算（−）、乗算（*）、除算（/）のいずれかを使用できます。たとえば x = 3 のとき、「3 * 3 / 3 + 3 − 3」という式を書けば、その値は 3 になります。

式を組み立てる際には、次のルールが適用されます。

• 除算演算子（/）は有理数を返します。
• 括弧はどこにも置けません。
• 通常の演算の優先順位に従います。乗算と除算は、加算・減算よりも高い優先度を持ちます。
• 単項マイナス（負符号）は使用できません。

目的は、指定された値 target に一致する式を、できるだけ少ない演算子の数で構成することです。つまり、必要な演算子の最小個数を求めます。

たとえば入力が x = 4、target = 15 であれば、答えは 3 になります。15 は「4 * 4 − 4 / 4」と表現でき、ここで使われる演算子は *、−、/ の 3 個だからです。

解法のアプローチ

この問題は、target を x の冪（べき）の和と差で表現するという発想で、再帰的に解くことができます。大まかな手順は次のとおりです。

1. target が x と一致する場合は、演算子が不要なので 0 を返します。
2. x > target の場合は、「x から 1（x/x）を引き続ける方法」と「x/x を target 回並べる方法」の安い方を選び、min((x − target) × 2, target × 2 − 1) を返します。
3. sum = x、カウンタ t = 0 とし、sum が target 以上になるまで sum を x 倍しながら t を増やします。これで target 以上となる最小の x の冪が求まります。
4. sum がちょうど target に一致したら、t を返します。
5. 一致しない場合は、次の 2 通りの分岐を再帰的に評価します。
   • 超過分を差し引く方法： r = leastOpsExpressTarget(x, sum − target) + t（sum − target < target の場合のみ）
   • ひとつ下の冪から積み上げる方法： l = leastOpsExpressTarget(x, target − sum / x) + t − 1
6. 最後に min(l, r) + 1 を返します。

この解法のポイントは、target を x 進数的に捉えるところにあります。大きい冪から順に見ていき、各段階で「余った分を引く」か「足りない分を下の桁で補う」かを選択することで、無駄の少ない式を効率よく構成できます。

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
    public:
    int leastOpsExpressTarget(int x, int target) {
        if(target == x) return 0;
        if(x > target){
            return min((x - target) * 2, (target * 2) - 1);
        }
        lli sum = x;
        int t = 0;
        while(sum < target){
            sum *= x;
            t++;
        }
        if(sum == target) return t;
        int l = INT_MAX;
        int r = INT_MAX;
        if(sum - target < target){
            r = leastOpsExpressTarget(x, sum - target) + t;
        }
        l = leastOpsExpressTarget(x, target - (sum / x)) + t - 1;
        return min(l, r) + 1;
    }
};
main(){
    Solution ob;
    cout << (ob.leastOpsExpressTarget(4, 15));
}

入力

4, 15

出力

3

このコードでは、x = 4、target = 15 に対して「4 * 4 − 4 / 4」に相当する 3 という最小演算子数が出力されます。

計算量について

再帰の深さは、target を x で割り続けて小さくなるまでの回数、すなわち O(log_x(target)) のオーダーに収まります。各呼び出しで行われる処理はほぼ定数回であるため、target が非常に大きくなっても高速に動作する実用的なアルゴリズムです。