問題はこちら
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)を作れるだけ作れば良いことは明らか
そうでない時、次のような手順を考える
１．G+2≦Bの間(1,3)を作る
２．その後、可能な限り(1,3)と(3,1)をセットで作る
３．最後にBが3個以上余っていれば(1,3)を作る
これが最適解であることを示す
手順１終了時点でBはGと等しいかG+1と等しい
手順２ではGとBを同数ずつ使っていくので、手順２終了時点でも同じであり、
この時点で(G,B)は(0,1)(1,2)(2,3)(3,4)(0,0)(1,1)(2,2)(3,3)のいずれかになっている
なので手順３終了時点では(G,B)は(0,1)(1,2)(0,0)(1,1)(2,2)のいずれかになっている（手順３終了後、G,Bは適当に入れ替えた）
(2,2)を除いては、floor((G+B)/4)個のアクセサリーが作られているのでこれで最適
(2,2)は、もし(G+B)/4個のアクセサリーが作れたとしたら、あまりは(0,0)となるはずだが、偶奇性からそれはありえない
よって結局これで最適
手順１を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
