yukicoder No.457 (^^*)

・O(|S|^3)
各カッコ対に対して、その間に'^^*'があるかどうか判定する
当然TLE

・O(|S|^2)
各'('について、そこから右に見て'^^*'があった以降にある')'の数を数える
(*^^)も同様
17/01/31修正

char s[10010];i,j,L,R;
int main(){
	gets(s);
	for(i=0;s[i];i++)if(s[i]=='('){
		
		//(^^*)
		j=i;
		while(s[j]!='\0'&&s[++j]!='^');
		while(s[j]!='\0'&&s[++j]!='^');
		while(s[j]!='\0'&&s[++j]!='*');
		while(s[j]!='\0'){
			if(s[j]==')')L++;
			j++;
		}
		
		//(*^^)
		j=i;
		while(s[j]!='\0'&&s[++j]!='*');
		while(s[j]!='\0'&&s[++j]!='^');
		while(s[j]!='\0'&&s[++j]!='^');
		while(s[j]!='\0'){
			if(s[j]==')')R++;
			j++;
		}
		
	}
	printf("%d %d",L,R);
	return 0;
}

・O(|S|)
よく考えれば上でやったことをDPにすればO(|S|)だった。
左から順に見ていって ( , (^ , (^^ , (^^* ,(^^*)　が各々いくつあるかを覚える
右も同様

int main(){
	int i,dpL[5]={},dpR[5]={};
	char s[10010];
	gets(s);
	for(i=0;s[i];i++){
		switch(s[i]){
			case '(':
				dpL[0]++;
				dpR[0]++;
				break;
			case '^':
				dpL[2]+=dpL[1];dpL[1]=dpL[0];dpL[0]=0;
				dpR[3]+=dpR[2];dpR[2]=dpR[1];dpR[1]=0;
				break;
			case '*':
				dpL[3]+=dpL[2];dpL[2]=0;
				dpR[1]+=dpR[0];dpR[0]=0;
				break;
			case ')':
				dpL[4]+=dpL[3];
				dpR[4]+=dpR[3];
		}
	}
	printf("%d %d",dpL[4],dpR[4]);
	return 0;
}

とりあえずゴルフした限りではO(|S|^2)の方が短くなった

・O(|S|)
超素直に

i,d[10];
main(){
	for(;read(0,&i,1);)
	//')'のとき
	i&1?d[4]+=d[3],d[9]+=d[8]:
		//'^'のとき
		i&4?d[2]+=d[1],d[1]=*d,*d=0,d[8]+=d[7],d[7]=d[6],d[6]=0:
			//'('のとき
			~i&2?++*d,d[5]++:
				//'*'のとき
				i>11?d[3]+=d[2],d[2]=0,d[6]+=d[5],d[5]=0:
					0;
	i=!printf("%d %d",d[4],d[9]);
}

206B

・O(|S|^2)
まずざっくりと。
tL,tRで状態を保存して遷移をチェックする

char s['~~'];i,j,L,R,tL,tR;
main(){
	for(gets(s);s[i];tL=tR=0,i++)for(j=i;s[++j];)if(s[i]=='('){
		tL<2&s[j]=='^'|tL==2&s[j]=='*'?++tL:s[j]==')'?tL+=tL>2,L+=tL>3:0;
		tR<3&tR>0&s[j]=='^'|!tR&s[j]=='*'?++tR:s[j]==')'?tR+=tR>2,R+=tR>3:0;
	}
	i=!printf("%d %d",L,R);
}

これをぎゅっとする
'^'が94、'*'が42、'('が40、')'が41

tL<2&s[j]=='^'|tL==2&s[j]=='*'?++tL:s[j]==')'?tL+=tL>2,L+=tL>3:0;
tL>1|s[j]-94&&tL-2|s[j]%7:s[j]==')'&&tL>2?L+=++tL>3:0:++tL;
tL>1|s[j]-94&&tL-2|s[j]%7:s[j]&tL>2?L+=++tL>3:0:++tL;

if(s[i]=='(')tL>1|s[j]-94&&tL-2|s[j]%7:s[j]&tL>2?L+=++tL>3:0:++tL;
tL>1|s[j]-94&&tL-2|s[j]%7:s[j]&tL>2?L+=++tL>3:0:s[i]%8||++tL;

ということでループ圧縮も一緒にして

#define f(X,Y,Z,W)X|s[j]-94&&Y|s[j]%7?s[j]&Z>2?W+=++Z>3:0:s[i]%8||++Z,
char s['~~'];
i,j,p,q,L,R;
main(){
	for(gets(s);s[++j]?f(p>1,p-2,p,L)f(q-1&q-2,q,q,R)1:(p=q=0,s[j=++i]););
	i=!printf("%d %d",L,R);
}

197B

17/07/15追記
頑張るとO(|S|)解の方が短くなった。
条件分岐を見直し、defineを有効活用した

#define f(n)d[n]+=d[n-1],
d[];
main(i){
	for(;read(0,&i,1);)
	//')'のとき
	i&1?f(4)f(9)0:
		//'^'のとき
		i&4?f(2)d[1]=*d,*d=0,f(8)d[7]=d[6],d[6]=0:
			//'*'のとき('\n'もここに)
			i&2?f(3)d[2]=0,f(6)d[5]=0:
				//'('のとき
				++*d+d[5]++;
	printf("%d %d",d[4],d[9]);
}

178B

メモ

yukicoderでゆるふわgolf

yukicoder No.457 (^^*)