SRM 221 DIV1 Hard PresentationComp

問題 Editorial

問題

xとyからなる文字列に対して、いつでも

• 含まれる"yyyyyy"を削除する
• 含まれる"xxxxxxxx"を削除する
• 含まれる"xy"を"yyyyyx"に置換する

という操作ができる。
文字列Aに操作を0回以上繰り返してBにできることを(A ⇒* B)と書くとき、関係~を(A ~ B <-> ∃C, A ⇒* C ∧ B ⇒* C)を定義する。
与えられた文字列expressionに対して、(expression ~ R)となる、文字数最小であってその中で辞書順最小となるRを求めよ

解答

EditorialとPractice Roomのrng_58さんの解答を参考にした。
(⇒*)に対して一意に決まる標準形やそのハッシュのようなものがあれば、それが等しいかどうかで判別できる。
これはうまくやるとコードのふうになるらしい。
なんとなくそれっぽくはあるが、でも詳しくはわかってない。
答えは必ず12文字以下なので、全探索すればいい

コメント

自分で思いつける気がしない。
なんとなくそうなのはわかるんだけど、その考え方を一から思いつく思いつき方がわからない

コード

#include <string>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
using namespace std;
struct PresentationComp {
	int f(string s) {
		int x = 0, y = 0;
		rep(i, s.size()) if(s[i] == 'x') x ++; else y += x%2 ? 5 : 1;
		x %= 8, y %= 6;
		return x * 6 + y;
	}
	string simplify(string expression) {
		int c = f(expression);
		rep(i, 12) rep(j, 1<<i) {
			string s; rep(k, i) s += "xy"[(j >> (i-k-1)) & 1];
			if(f(s) == c) return s;
		}
	}
};