kmjp's blog

競技プログラミング参加記です

LeetCode Weekly Contest 428 : 3389. Minimum Operations to Make Character Frequencies Equal

最近難易度8の問題増えてきたね。
https://leetcode.com/problems/minimum-operations-to-make-character-frequencies-equal/description/

問題

アルファベット小文字で構成される文字列Sが与えられる。
Sに以下の処理を行うとき、Sの各文字の登場頻度が等しくなるようにするのに必要な最小処理回数を求めよ。

  • Sから1文字消す
  • Sに任意の1文字を足す
  • Sの任意の1文字を、次の文字にする。なお、z→aにはできない。

解法

登場頻度cを総当たりする。
a-zの各文字の登場頻度を0にするケースとcにするケースの最小処理回数をDPで順次求めて行く。
その際、もし1つ前の文字が元々c個以上でd個ある場合、文字を次の文字にする手段を取ることで、(d-c)個までは今見ている文字の数をノーコストで増やすことができる。

int dp[27][2];

class Solution {
public:
    int makeStringGood(string s) {
		int C[27]={};
		FORR(c,s) C[c-'a'+1]++;
        
        int ret=1<<30;
        int i,x,y;
        FOR(i,20100) {
			FOR(x,27) dp[x][0]=dp[x][1]=1<<20;
			dp[0][0]=0;
			FOR(x,26) {
				dp[x+1][0]=min(dp[x][0],dp[x][1])+C[x+1];
				dp[x+1][1]=min(dp[x+1][1],dp[x][0]+abs(C[x+1]-i));
				dp[x+1][1]=min(dp[x+1][1],dp[x][1]+abs(C[x+1]-i));
				if(C[x+1]<=i&&C[x]+C[x+1]>=i) dp[x+1][1]=min(dp[x+1][1],dp[x][0]);
				if(C[x]+C[x+1]<i) dp[x+1][1]=min(dp[x+1][1],dp[x][0]+abs(C[x+1]+C[x]-i));
				if(C[x]>=i&&C[x+1]<=i&&C[x+1]+(C[x]-i)>=i) dp[x+1][1]=min(dp[x+1][1],dp[x][1]);
				if(C[x]>=i&&C[x+1]+(C[x]-i)<=i) dp[x+1][1]=min(dp[x+1][1],dp[x][1]+abs(C[x+1]+(C[x]-i)-i));
			}
			ret=min(ret,dp[26][0]);
			ret=min(ret,dp[26][1]);
		}
        return ret;
    }
};

まとめ

最終的なコードは長くないけど、余った文字の扱いでちょっと迷う問題。