読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.437 cwwゲーム

No.437 cwwゲーム - yukicoder

dfsするだけ
Nの桁数は高々13なので、適当にやってもどうにかなる

#define max(p,q)p<q?p=q:0
char s[99];

//今まで使った数を引数とし、残りの数で作れる最大の値を返す関数
int f(used){
	int i,j,k,t,m=0;
	for(i=0;s[i];i++)for(j=i+1;s[j];j++)for(k=j+1;s[k];k++){
		if(used>>i&1||used>>j&1||used>>k&1||s[i]=='0'||s[i]==s[j]||s[j]!=s[k])continue;
		//選んだ3つの数字が使用済みだったり、cww数にならないときはダメ
		t=(s[i]-'0')*100+(s[j]-'0')*10+s[k]-'0'+f(used^1<<i^1<<j^1<<k);
		//そうでないなら、こうしてできたcww数と残りで作れる最大値の和を調べる
		max(m,t);
	}
	return m;
}

int main(){
	gets(s);
	printf("%d",f(0));
	return 0;
}


縮める
fの引数を「使った数」ではなく「残った数」にすると少し短くなる

char s[99];
f(u,i,j,k,m){
	for(i=m=0;s[j=i];++i)for(;s[k=++j];)for(;s[++k];)
	u>>i&u>>j&u>>k&s[i]!=48&s[i]!=s[j]&s[j]==s[k]?m=fmax(m,(s[i]-48)*100+(s[j]-48)*10+s[k]-48+f(u^1<<i^1<<j^1<<k)):0;
	//s[j]==s[k]などの真偽値を返す項があるので、u>>i&1の&1を省略することが出来る
	return m;
}
x;main(){gets(s);x=!printf("%d",f(-1));}

s[i],s[j]が何度も登場するのでこれは適当な記号で置くことにする
(s[i]-48)*100+(s[j]-48)*10+s[k]-48の計算部分では、s[j]==s[k]になっていることを利用しつつ短くまとめる

char s[99];
f(u,i,j,k,m,p,q){
	for(i=m=0;p=s[j=i];++i)for(;q=s[k=++j];)for(;s[++k];)
	u>>i&u>>j&u>>k&p!=48&p!=q&q==s[k]?m=fmax(m,p*100+q*11-5328+f(u^1<<i^1<<j^1<<k)):0;
	return m;
}
x;main(){gets(s);x=!printf("%d",f(-1));}

mainの部分は、getsをfの引数に押し込める
またp!=48の部分は、pの値が48~57のいずれかであることから、p>48と書ける

char s[99];
f(u,i,j,k,m,p,q){
	for(i=m=0;p=s[j=i];++i)for(;q=s[k=++j];)for(;s[++k];)
	u>>i&u>>j&u>>k&p>48&p!=q&q==s[k]?m=fmax(m,p*100+q*11-5328+f(u^1<<i^1<<j^1<<k)):0;
	return m;
}
x;main(){x=!printf("%d",f(~!gets(s)));}

最後に配列サイズをごまかして完成

char s[99];
f(u,i,j,k,m,p,q){
	for(i=m=0;p=s[j=i];++i)for(;q=s[k=++j];)for(;s[++k];)
	u>>i&u>>j&u>>k&p>48&p!=q&q==s[k]?m=fmax(m,p*100+q*11-5328+f(u^1<<i^1<<j^1<<k)):0;
	return m;
}
x;main(){x=!printf("%d",f(~!gets(s)));}

210B