AtCoder ABC #264 (freee プログラミングコンテスト2022) : G - String Fair

久々に良い出来。
https://atcoder.jp/contests/abc264/tasks/abc264_g

問題

空でない文字列Sの美しさを以下のように決める。
3文字以下の文字列と、その文字列に対する点数が幾通りか設定されている。
S中に上記文字列が部分文字列として含まれている場合、そのつど対応する点数が美しさに計上される。

Sの美しさとして考えられる最大値を求めよ。また、無限に大きくできる場合、無限大と解答せよ。

解法

Sが1文字のケースは先に列挙しておく。
以下の値の最大値を考える。
dp(x,y) := Sの末尾2文字がx,yの場合の美しさの総和

ダイクストラ法の要領で、dp(x,y)に対応する状態に対し、さらに後ろに1文字を付け加えるパターンを総当たりしていこう。
この時、美しさを無限に大きくできる場合はダイクストラ法が終了しない。
そこで、以下のコードでは適当な回数で終了しない場合、無限大と解答した。

int N;
ll P1[26];
ll P2[26][26];
ll P3[26][26][26];
ll dp[26][26];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>s>>x;
		FORR(c,s) c-='a';
		if(s.size()==1) {
			P1[s[0]]=x;
		}
		if(s.size()==2) {
			P2[s[0]][s[1]]=x;
		}
		if(s.size()==3) {
			P3[s[0]][s[1]][s[2]]=x;
		}
	}
	ll ma=-1LL<<60;
	//1文字
	FOR(i,26) ma=max(ma,P1[i]);
	//2文字
	priority_queue<pair<ll,int>> Q;
	FOR(y,26) FOR(x,26) {
		ma=max(ma,P2[y][x]+P1[y]+P1[x]);
		dp[y][x]=P2[y][x]+P1[y]+P1[x];
		Q.push({-dp[y][x],y*26+x});
	}
	//2文字
	FOR(i,26) ma=max(ma,P1[i]);
	
	int loop=1000000;
	while(Q.size()) {
		loop--;
		if(loop==0) {
			cout<<"Infinity"<<endl;
			return;
		}
		ll co=-Q.top().first;
		int c1=Q.top().second/26;
		int c2=Q.top().second%26;
		Q.pop();
		if(dp[c1][c2]!=co) continue;
		ma=max(ma,co);
		FOR(i,26) {
			ll sc=co+P3[c1][c2][i]+P2[c2][i]+P1[i];
			if(sc>dp[c2][i]) {
				dp[c2][i]=sc;
				Q.push({-sc,c2*26+i});
			}
		}
	}
	cout<<ma<<endl;
}

まとめ

これは割とすんなり。