yukicoder No.291 黒い文字列

DPの状態遷移を考えるのに2時間くらいかかってしまった……

dp[i][a][b][c][d]=(i文字目まで見て、Kがa個、内KUがb個、内KURがc個、内KUROがd個あるときのKUROIの内数)　として配るDPを考える
K,U,R,O,Iの各文字がきたらそれを使わない理由はないので

(i+1)文字目が
Kのときdp[i+1][a+1][b][c][d]=dp[i][a][b][c][d]
Uのときdp[i+1][a][b+1][c][d]=dp[i][a][b][c][d]
Rのときdp[i+1][a][b][c+1][d]=dp[i][a][b][c][d]
Oのときdp[i+1][a][b][c][d+1]=dp[i][a][b][c][d]
Iのときdp[i+1][a][b][c][d]  =min(dp[i][a][b][c][d]+1,d)
?のとき上記全て（ただしこのときは同じ箇所に2回以上配る可能性があるので、単なる代入ではなくもとの値とmaxをとる必要がある）
いずれでもない時
　　　 dp[i+1][a][b][c][d]  =dp[i][a][b][c][d]

というように更新していける。
配り先は(Kの個数)>(KUの個数)となるようなものも含まれてしまうが、配り元の方で気をつけておけば問題ない
最大値が更新されるのはIまたは?がきた時だけであることに注意
dpの初期値は-1とかにしておかなければならないが面倒なのでさぼって、実際の値+1を保存することにする
（値が0のところからは配り始めない）

一見すると状態数が|S|^5、a≧b≧c≧dを考慮しても|S|^5/24だが、完成するKUROI文字列の個数は高々|S|/5なので、K,KU,KUR,KUROの完成数もそれを上限として打ち切って良い。
すると|S|^5/625＝1.6*10^7となり通る

#define f(i,e)for(i=0;i<=e;i++)
#define max(p,q)(p<(q)?p=q:p)
char s[110];
dp[110][22][22][22][22];
i,a,b,c,d,t,ans;
int main(){
	*****dp=1;
	for(gets(s);s[i];i++)f(a,20)f(b,a)f(c,b)f(d,c)if(t=dp[i][a][b][c][d]){
		if(s[i]=='K'||s[i]=='?')max(dp[i+1][a+1][b][c][d],t);
		if(s[i]=='U'||s[i]=='?')max(dp[i+1][a][b+1][c][d],t);
		if(s[i]=='R'||s[i]=='?')max(dp[i+1][a][b][c+1][d],t);
		if(s[i]=='O'||s[i]=='?')max(dp[i+1][a][b][c][d+1],t);
		if(s[i]=='I'||s[i]=='?')max(ans,max(dp[i+1][a][b][c][d],d<t?d:t+1));
		max(dp[i+1][a][b][c][d],t);
	}
	printf("%d",ans-1);
	return 0;
}

さて、これを縮める。
まずdp[ ][ ][ ][ ][ ]とs[i]==' 'が目につくのでこれをどうにかしたい。
tをポインタにすればt=&dp[ ][ ][ ][ ][ ]とかでいい感じにできそう。
char*を用意してs[i]を消し、s[i]=='?'は適当な文字でおく。

#define f(i,e)for(i=e+1;i--;)
#define m(p,q)(p<(q)?p=q:p)
char s[110],*p=s;
q[22][22][22][22][102];
i,a,b,c,d,x,*t;
main(S){
	*****q=1;
	for(gets(s);*p;p++,i++)f(a,20)f(b,a)f(c,b)f(d,c)
		*(t=&q[a][b][c][d][i])?
			x=*p-63,
			*p-75&&x||m(t[1086097],*t),
			*p-85&&x||m(t[49369],*t),
			*p-82&&x||m(t[2245],*t),
			*p-79&&x||m(t[103],*t),
			*p-73&&x||m(S,m(t[1],d<*t?d:*t+1)),
			m(t[1],*t)
		:0;
	i=!printf("%d",S-1);
}

iが要らなくなったので消して

#define f(i,e)for(i=e+1;i--;)
#define m(p,q)(p<(q)?p=q:p)
q[22][22][22][22][102],*t,a,b,c,d,x;
char s[110],*p=s;
main(S){
	*****q=1;
	for(gets(s);*p;p++)f(a,20)f(b,a)f(c,b)f(d,c)
		*(t=&q[a][b][c][d][p-s])?
			x=*p-63,
			*p-75&&x||m(t[1086097],*t),
			*p-85&&x||m(t[49369],*t),
			*p-82&&x||m(t[2245],*t),
			*p-79&&x||m(t[103],*t),
			*p-73&&x||m(S,m(t[1],d<*t?d:*t+1)),
			m(t[1],*t)
		:0;
	x=!printf("%d",S-1);
}

373B

メモ

yukicoderでゆるふわgolf

yukicoder No.291 黒い文字列