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

メモ

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

yukicoder No.91 赤、緑、青の石

問題はこちら
No.91 赤、緑、青の石 - yukicoder

O(1)解
石の色は忘れてR≦G≦Bとしてよい。R個以上作れることは自明
Rの石を2個つかって他の石と交換する操作では、作れるようになるアクセサリーの数が増えることはない
なぜなら、もしR2個でGを作ったとすれば、最終的にR個のアクセサリーを作るためには、G,Bいずれかから再びR2個を作らねばならず、Gから作ると明らかに損、Bから作るならはじめからB2→G1と交換すれば良いため
また、G,BがR個未満になるような交換の仕方をすることも同様にありえない
なのでまず最初にR個のアクセサリーを作ったと考えR=0としてよい
残った(G,B)個の石でアクセサリーを作ることを考える
「他の石と交換する」ということをやめ、問題を次のように読み替える
「1個のアクセサリーを作るためには(1,3)個または(0,5)個の石が必要(順不同)。(G,B)個の石から最大何個のアクセサリーが作れるか」
(1,3)ではあわせて4個、(0,5)ではあわせて5個の石が必要なので、可能な限り前者を使うのが良い
もし3G≦Bなら、まず(1,3)でG個作り、残ったBで(0,5)を作れるだけ作れば良いことは明らか
そうでない時、次のような手順を考える
1.G+2≦Bの間(1,3)を作る
2.その後、可能な限り(1,3)と(3,1)をセットで作る
3.最後にBが3個以上余っていれば(1,3)を作る
これが最適解であることを示す
手順1終了時点でBはGと等しいかG+1と等しい
手順2ではGとBを同数ずつ使っていくので、手順2終了時点でも同じであり、
この時点で(G,B)は(0,1)(1,2)(2,3)(3,4)(0,0)(1,1)(2,2)(3,3)のいずれかになっている
なので手順3終了時点では(G,B)は(0,1)(1,2)(0,0)(1,1)(2,2)のいずれかになっている(手順3終了後、G,Bは適当に入れ替えた)
(2,2)を除いては、floor((G+B)/4)個のアクセサリーが作られているのでこれで最適
(2,2)は、もし(G+B)/4個のアクセサリーが作れたとしたら、あまりは(0,0)となるはずだが、偶奇性からそれはありえない
よって結局これで最適

手順1を1度実行する毎にG,Bの差は2個縮むので、ループしなくとも(B-G)/2個作るとすれば良い

以上の考察をコードにまとめる

int main(){
	int r,g,b,s=0,t;
	scanf("%d%d%d",&r,&g,&b);
	if(r>g)r^=g^=r^=g;
	if(g>b)b^=g^=b^=g;
	if(r>g)r^=g^=r^=g;
	//ソート
	s=r;
	g-=r;
	b-=r;
	//まずr個作る
	if(3*g<=b){
		s+=g;
		b-=3*g;
		printf("%d",s+b/5);
		return 0;
	}
	t=(b-g)/2;
	s+=t;
	g-=t;
	b-=3*t;
	//手順1
	t=g/4;
	s+=t;
	g-=t*4;
	b-=t*4;
	//手順2
	if(b>=3)s++;
	//手順3
	printf("%d",s);
	return 0;
}

条件分岐ヤダー

O(N)解
「一番多い石」を2個使って「一番少ない石」を1個作る、という操作を、この操作によって作れるアクセサリーの数が減ることがない間続ける
つまり、「最多」と「最少」の差が2より大きい間

int main(){
	int r,g,b,s=0,t;
	scanf("%d%d%d",&r,&g,&b);
	if(r>g)r^=g^=r^=g;
	if(g>b)b^=g^=b^=g;
	if(r>g)r^=g^=r^=g;
	while(b-r>2){
		b-=2;
		r++;
		if(r>g)r^=g^=r^=g;
		if(g>b)b^=g^=b^=g;
		if(r>g)r^=g^=r^=g;

	}
	printf("%d",r);
	return 0;
}

あとはこれをちゃちゃっと圧縮

#define f(a,b)a>b?a^=b^=a^=b:0,
a,b;
main(c){
	for(scanf("%d%d%d",&a,&b,&c);f(a,b)f(b,c)f(a,b)c-a>1;a++)c-=2;
	a=!printf("%d",a);
}

125B