yukicoder : No.572 妖精の演奏

なんとか全完できて良かったけど、Codeforcesにはだいぶ出遅れた。
https://yukicoder.me/problems/no/572

問題

M種類の音符を計N回叩く。
i番の音符のあとj番を叩くと得点A[i][j]が得られる。

N回音符を叩いた場合に得られる総得点の最大値を求めよ。

解法

全体で(i+1)回の音符を叩いたとき、最初にx番、最後にy番を叩くケースの総得点の最大値をf(x,y,i)とする。
となる。なお、zは音符のパターン全通りチェックする必要があるが、jはどこか１つの値でチェックすればよい。

よって行列累乗の要領でf(x,y,*)を求めることができるので、x,yを総当たりしつつf(x,y,N-1)の最大値を求めていけばよい。

ll N;
int M;
ll A[35][31][31];
ll B[35][31][31];

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N>>M;
	
	FOR(y,M) FOR(x,M) {
		cin>>A[0][y][x];
	}
	FOR(i,34) {
		FOR(x,M) FOR(y,M) {
			FOR(z,M) A[i+1][x][y]=max(A[i+1][x][y],A[i][x][z]+A[i][z][y]);
		}
	}
	
	N--;
	ll ret=0;
	FOR(i,34) {
		if(N&(1LL<<i)) {
			FOR(x,M) FOR(y,M) {
				FOR(z,M) B[i+1][x][y]=max(B[i+1][x][y],B[i][x][z]+A[i][z][y]);
				ret=max(ret,B[i+1][x][y]);
			}
		}
		else {
			FOR(x,M) FOR(y,M) B[i+1][x][y]=B[i][x][y];
		}
	}
	
	cout<<ret<<endl;
}

まとめ

解きながら「ん、これ★２か？」と思いつつ、writer名を見て納得してしまった。
このwriterさん、どうも自作の問題の難易度を過小評価する傾向があるのよね。
もうちょっと自信持って難易度つけていいと思いますよ(過小評価しすぎると逆に嫌味にも見えてしまうし…)。