kmjp's blog

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

Codeforces ECR #055 : F. Speed Dial

これは自力では解けなかったな。
https://codeforces.com/contest/1082/problem/F

問題

N種類の電話番号と、それぞれの入力回数が与えられる。
これらを入力するわけだが、ここでK個のショートカットキーを定義できる。
これらショートカットキーは、任意に決めることができ、番号のprefixの入力にのみ利用できる。

適切なショートカットキーを設定したとき、ショートカットキー以外のボタン押下回数を最小化せよ。

解法

Trie木を作り、そこでDPしていく。
各状態について、以下を求めていこう。
f(v, d, k) := Trie木のv以下のsubtreeにおいて、最寄りのショートカットキー設定済みの祖先の位置がdで、v以下でk回ショートカットキーを定義済み

あとは木DPの要領で、子頂点毎のショートカットキー設定回数が計K回となるように足し合わせていく。

int id=1;
int nex[505][10];
int D[555];
int val[555];
int memo[555][555][12];

int N,K;
string S[505];
int M[505];

int dfs(int cur,int pd,int K) {
	if(memo[cur][pd][K]>=0) return memo[cur][pd][K];
	
	int dp[11]={};
	int i,j,k;
	FOR(i,10) if(nex[cur][i]>=0) {
		int tmp[11]={},tmp2[11]={};
		FOR(j,11) tmp[j]=dfs(nex[cur][i],pd,j);
		FOR(j,11) tmp2[j]=1<<30;
		FOR(j,11) FOR(k,11) if(j+k<=10) tmp2[j+k]=min(tmp2[j+k],dp[j]+tmp[k]);
		swap(dp,tmp2);
	}
	
	int ret=dp[K]+val[cur]*(D[cur]-pd);
	
	// take here
	if(K>0) ret=min(ret,dfs(cur,D[cur],K-1));
	
	return memo[cur][pd][K]=ret;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	MINUS(nex);
	FOR(i,N) {
		cin>>S[i]>>M[i];
		int cur=0;
		FORR(s,S[i]) {
			s-='0';
			if(nex[cur][s]==-1) {
				nex[cur][s]=id++;
				D[nex[cur][s]]=D[cur]+1;
			}
			cur=nex[cur][s];
		}
		val[cur]+=M[i];
	}
	
	MINUS(memo);
	cout<<dfs(0,0,K)<<endl;
	
}

まとめ

もっと計算量の多い方法は思いついたけど、これは思いつかなかった。