Codeforces #459 Div1 B. MADMAX

珍しく重要な条件が先頭に書いてある…。
http://codeforces.com/contest/917/problem/B

問題

DAGを成す有向グラフが与えられる。
各辺には文字が設定されている。

このグラフを用いて2人げゲームを行う。
初期状態では両プレイヤーの石がいずれかの頂点に置かれている。

両者交互に自分の石を現在いる頂点から伸びている辺の接続先に移動させる。
ただし、直前に相手が使った辺に設定された文字より辞書順で前の文字の辺は利用できない。
自身のターンで石をどこにも移動できないと負けである。

両者の初期位置に対し、最適手を打った場合の勝者はどちらかを判定せよ。

解法

win(自身の現在位置, 相手の現在位置, 相手の直前手の文字) という関数を考えメモ化再帰すればよい。

int N,M;
int D[101][101];
int memo[101][101][101];

int win(int a,int b,int pre) {
	if(memo[a][b][pre]>=0) return memo[a][b][pre];
	int ret=0;
	int i;
	FOR(i,N) if(D[a][i]>=pre && win(b,i,D[a][i])==0) ret=1;
	return memo[a][b][pre]=ret;
}




void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>s;
		D[x-1][y-1]=s[0]-'a'+2;
	}
	
	MINUS(memo);
	
	FOR(x,N) {
		FOR(y,N) {
			if(win(x,y,1)) cout<<"A";
			else cout<<"B";
		}
		cout<<endl;
	}
	
}

まとめ

本番、DAGの記載をなかなか見つけられず、「ループがあったらどうすんだこれ…」と悩んでしまった。