kmjp's blog

競技プログラミング参加記です

yukicoder : No.1612 I hate Construct a Palindrome

I hate系しばしば遭遇するな。
https://yukicoder.me/problems/no/1612

問題

N頂点の連結無向グラフが与えられる。
各辺には1つ文字が設定されている。

1番の頂点からN番の頂点まで辺をたどって移動する際、経由した辺の文字を順に並べたものが回文でないようにしたい。
2N-1回以下の移動で条件を満たすものを示せ。

解法

全辺同じ文字の場合、どうやっても回文になるので解なし。
そうでない場合、2種類以上の文字を含む経路を求めよう。
これはBFSしたのち復元すればよい。

その結果が回文の場合、無駄に始点か終点の周りを適当に1往復する経路を追加すると回文ではなくなる。

int N,M;
int C[201010];
vector<pair<int,int>> E[101010];
int from[101010][27];
int from2[101010][27];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(from);
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>s;
		E[x-1].push_back({y-1,i});
		E[y-1].push_back({x-1,i});
		C[i]=s[0]-'a';
	}
	queue<int> Q;
	FORR2(e,x,E[0]) {
		from[e][C[x]]=-2;
		from2[e][C[x]]=x;
		Q.push(e*100+C[x]);
	}
	while(Q.size()) {
		int cur=Q.front()/100;
		int c=Q.front()%100;
		Q.pop();
		FORR2(e,x,E[cur]) {
			if(c==26||c!=C[x]) {
				if(from[e][26]==-1) {
					from[e][26]=cur*100+c;
					from2[e][26]=x;
					Q.push(e*100+26);
				}
			}
			else {
				if(from[e][c]==-1) {
					from[e][c]=cur*100+c;
					from2[e][c]=x;
					Q.push(e*100+c);
				}
			}
		}
	}
	
	if(from[N-1][26]>=0) {
		vector<int> V;
		int cur=N-1;
		int c=26;
		while(cur!=0||c!=0) {
			V.push_back(from2[cur][c]);
			x=from[cur][c];
			if(x==-2) break;
			cur=x/100;
			c=x%100;
		}
		
		V.push_back(E[0][0].second);
		V.push_back(E[0][0].second);
		
		reverse(ALL(V));
		cout<<V.size()<<endl;
		FORR(v,V) cout<<(v+1)<<endl;
		return;
	}
	
	cout<<-1<<endl;
	
}

まとめ

★3としては手ごろな問題。