LeetCode Weekly Contest 116 : 964. Least Operators to Express Number

これ難易度8でもいい気がする。
https://leetcode.com/contest/weekly-contest-116/problems/least-operators-to-express-number/

問題

数X,Tが与えられる。
Xを複数並べて、間に演算子を挟みTを作りたい。
演算子の優先順は一般的な数字と同じで、かつ括弧や単項のマイナスは利用できない。
演算子の数の最小値を求めよ。

解法

演算子数を数えるとややこしいので、Xの数を数え最後に1引くことを考える。
括弧が使えないので、乗算除算だけで生成されるXの累乗を加減算し、Tを作ろう。
1を作るのにはX/XでXが2個、X^n(n≧1)を作るにはXがn個いる。

あとは、このXの累乗を加減算してTを作る。
TをX進数とみなし、下の桁からXの累乗を引いて0にしていくことを考える。
下からn桁目(nは0-index)が0ではないkである場合、k*(X^n)を引く場合と(X-k)*(X^n)を足して繰り上げを狙うパターンがある。
これら両方をメモ化再帰しながら探索していこう。

class Solution {
public:
	int B;
	map<pair<int,int>,int> memo;
	
	int dp(int cur,int step) {
		cur=abs(cur);
		if(cur==0) return 0;
		if(cur==1) return (1+abs(step));
		if(memo.count({cur,step})) return memo[{cur,step}];
		
		if(cur%B==0) {
			return memo[{cur,step}]=dp(cur/B,step+1);
		}
		else {
			return memo[{cur,step}]=min(dp(cur/B,step+1)+(cur%B)*(1+abs(step)),dp(cur/B+1,step+1)+(B-(cur%B))*(1+abs(step)));
		}
	}
    int leastOpsExpressTarget(int x, int target) {
		B=x;
        memo.clear();
        return dp(target,-1)-1;
    }
};

まとめ

難易度9なので最初構えちゃった。