これ難易度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なので最初構えちゃった。