Codeforces ECR #064 : G. Optimizer

これは通常回で出したら文句の多そうな問題。
https://codeforces.com/contest/1156/problem/G

問題

変数の代入と、二項演算子で構成された式が複数行からなるプログラムが与えられる。
このプログラムは最終的にresという変数に値を代入するものだとする。
同一の結果を返すプログラムのうち、行数を最小化した例を答えよ。

解法

地道に最適化していく。
単なる変数の代入であれば、以後参照を置き換えるだけでいいし、二項演算子で演算後の代入の場合、以前に同じ式が登場していればそれを再利用する。

結果としてresへの代入が前倒しになるかもしれない場合に注意。
例えばy=x, z=y, res=zみたいのはres=xとなる。

あとはひたすらコーナーケースを考慮して頑張る。

int N;
set<string> S;
string L[1010],R1[1010],R2[1010],O[1010];
map<string,string> name;
string lastres;
map<string,vector<string>> M;
map<string,int> line;
map<string,string> cache;

string nex(string s) {
	int i=s.size()-1;
	while(1) {
		s[i]++;
		if(s[i]=='z'+1) {
			s[i]='a';
			i--;
		}
		else break;
	}
	return s;
	
}


string tag() {
	static string s="aaaa";
	s=nex(s);
	while(S.count(s)) s=nex(s);
	
	return s;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(i,N) {
		cin>>s;
		x=s.find('=');
		L[i]=s.substr(0,x);
		s=s.substr(x+1);
		x=s.find_first_of("$^#&");
		if(x!=string::npos) {
			R1[i]=s.substr(0,x);
			O[i]=s.substr(x,1);
			R2[i]=s.substr(x+1);
			
			if(name.count(R1[i])==0) name[R1[i]]=R1[i];
			if(name.count(R2[i])==0) name[R2[i]]=R2[i];
			R1[i]=name[R1[i]];
			R2[i]=name[R2[i]];
			
			name[L[i]]=tag();
			
			string tmp=R1[i]+O[i]+R2[i];
			if(cache.count(tmp)) {
				name[L[i]]=cache[tmp];
				if(L[i]=="res") lastres=name[L[i]];
				L[i]="";
			}
			else {
				cache[tmp]=name[L[i]];
			}
			
		}
		else {
			R1[i]=s;
			if(L[i]==R1[i]) {
				L[i]=="";
				continue;
			}
			if(name.count(R1[i])==0) name[R1[i]]=R1[i];
			R1[i]=name[R1[i]];
			name[L[i]]=R1[i];
		}
		if(L[i]=="res") lastres=name[L[i]];
		L[i]=name[L[i]];
		
		//cout<<L[i]<<" "<<R1[i]<<" "<<O[i]<<" "<<R2[i]<<endl;
	}
	
	if(lastres=="") return _P("0\n");
	
	set<string> T;
	T.insert(lastres);
	vector<string> ret;
	for(i=N-1;i>=0;i--) {
		if(L[i].size()&&T.count(L[i])) {
			if(O[i].size()) {
				if(L[i]==lastres) {
					L[i]="res";
				}
				ret.push_back(L[i]+"="+R1[i]+O[i]+R2[i]);
				T.insert(R1[i]);
				T.insert(R2[i]);
			}
		}
	}
	
	if(ret.empty()&&lastres!="res") ret.push_back("res="+lastres);
	
	cout<<ret.size()<<endl;
	reverse(ALL(ret));
	FORR(r,ret) cout<<r<<endl;
	
}

まとめ

こういうのは大学の授業でやれっていう意見を見かけた。