【今日の精進】ABC264G - String Fair

毎日格上の問題を倒すやつの75日目です。

問題リンク

atcoder.jp

問題概要

文字列の美しさを決めるよ。

審査項目は 個あって、 個目は、「部分文字列に が含まれていたらその数と の積だけ得点が与えられる」というものだよ。

得点の最大値を求めるか、そんなものはないと宣言してね。

解法

文字の組を頂点、そこから 文字追加したときに得られる点数を辺の重みとした有向辺の上の最大ウォークを求める問題です。

また、これは辺の重みを反転するとワーシャルフロイド法で全点間の距離を求めればよくなります。

提出コード

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF=pow(2,61)-1;

int main(){
    int N;
    cin>>N;
    unordered_map<string,ll> ser;
    for(int i=0; i<N; i++){
        string T;
        ll P;
        cin>>T>>P;
        ser.emplace(T,P);
    }
    string emp="";
    vector<vector<ll>> dist(676,vector<ll>(676,INF));
    for(int i=0; i<26; i++){
        for(int j=0; j<26; j++){
            for(int k=0; k<26; k++){
                ll pos=0;
                pos+=ser[emp+char(k+'a')];
                pos+=ser[emp+char(j+'a')+char(k+'a')];
                pos+=ser[emp+char(i+'a')+char(j+'a')+char(k+'a')];
                dist[i*26+j][j*26+k]=-pos;
            }
        }
    }
    for(int i=0; i<676; i++){
        for(int j=0; j<676; j++){
            for(int k=0; k<676; k++){
                dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]);
            }
        }
    }
    ll ans=-INF;
    for(int i=0; i<676; i++){
        for(int j=0; j<676; j++){
            ll pos=0;
            ans=max(ans,ser[emp+char(i/26+'a')]);
            pos+=ser[emp+char(i/26+'a')];
            pos+=ser[emp+char(i%26+'a')];
            pos+=ser[emp+char(i/26+'a')+char(i%26+'a')];
            ans=max(ans,-dist[i][j]+pos);
            ans=max(ans,pos);
            if(i==j&&dist[i][j]<0){
                cout<<"Infinity\n";
                return 0;
            }
        }
    }
    cout<<ans<<endl;
}

Submission #48182422 - freee Programming Contest 2022（AtCoder Beginner Contest 264）

感想

計算量悪いのをcppでごまかす屑