yukicoder : No.265 数学のテスト

266より、ずっとめんどい。
http://yukicoder.me/problems/605

問題

xの多項式Aを１階微分した多項式を"d{A}"で表現する。
"d{}"を含むxの多項式Sが与えられるので、xの各次数の係数を求めよ。

なお、計算過程でxの最高次はd以下(dは10以下)であることが保証されている。

解法

Editorialとは別解法。
Editorialは外側から各項の微分回数を求め、#*x*x*xの形の式にあたると、その分微分した。

自分の解法は逆にDFSで導関数内部から順次計算。
ガリガリ構文解析しつつ、部分文字列毎にxの0～10次の係数を求めていく。
途中係数が2^31超えることがあるので注意。

以下のコードでは先に括弧だけ処理している。

int N,D;
string S;
int E[101010];

vector<ll> dodo(int L,int R) {
	vector<ll> ret(11,0), C(11,0);
	int i;
	
	if(L>=R) return ret;
	if(S[L]=='+') return dodo(L+1,R);
	
	if(S[L]=='d') {
		ret=dodo(L+2,E[L]);
		FOR(i,10) ret[i]=(i+1)*ret[i+1];
		ret[10]=0;
		L=E[L]+1;
	}
	else {
		int cur=1;
		int di=0;
		while(L<R) {
			if(S[L]=='x') di++;
			else cur*=S[L]-'0';
			
			L++;
			if(L>=R || S[L]!='*') {
				L++;
				break;
			}
			L++;
		}
		ret[di]=cur;
	}
	
	C=dodo(L,R);
	FOR(i,11) ret[i]+=C[i];
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N>>D>>S;
	
	vector<int> v;
	FOR(i,N) {
		if(S[i]=='d') v.push_back(i);
		if(S[i]=='}') E[v.back()]=i, v.pop_back();
	}
	
	vector<ll> V=dodo(0,S.size());
	FOR(i,D+1) _P("%lld%c",V[i],(i==D)?'\n':' ');
}

まとめ

簡単な構文解析ライブラリ作ろうかなぁ。