技術室奥プログラミングコンテスト#4 Day1 : L - じゃんけん

なんか難易度が下がった気がする。
https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_l

問題

頂点にグーチョキパーが書かれた木を成すグラフを用いてじゃんけんを行う。
両プレイヤーは、任意の頂点から開始し、じゃんけんのたびにその場にとどまるか隣接点に移動するか選ぶことができる。
その後、両プレイヤーのいる頂点の内容をじゃんけんの手として出す。

じゃんけんで勝つとX点、あいこだとY点もらえる。
相手の移動経路がわかっている場合、自分は最適な移動経路を取ると最大何点取れるか。

解法

O(頂点数×じゃんけん回数)で間に合うので、じゃんけん毎に各位置にいる際の最大得点を求めていけばよい。

int N,M;
int K;
int X,Y;
vector<int> E[2020];
string D;
string S[2020];

int dp[2020][2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K>>X>>Y;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,N) {
		cin>>S[i];
		E[i].push_back(i);
	}
	
	FOR(j,K+1) FOR(i,N) dp[j][i]=-(1<<30);
	dp[0][0]=0;
	FOR(i,K) {
		cin>>x;
		D=S[x-1];
		FOR(x,N) {
			FORR(e,E[x]) {
				int sc=dp[i][x];
				if(S[e]==D) sc+=Y;
				if(S[e]=="G"&&D=="C") sc+=X;
				if(S[e]=="C"&&D=="P") sc+=X;
				if(S[e]=="P"&&D=="G") sc+=X;
				dp[i+1][e]=max(dp[i+1][e],sc);
			}
		}
	}
	cout<<*max_element(dp[K],dp[K]+N)<<endl;
	
}

まとめ

余り迷うことなく愚直に総当たりするだけなので、なんでこの位置に置いたんだろう。