Member SRM 503
あれっまたMemberだ。
250: Toasterなんとかかんとか
何種類かのトーストを焼きました。焼きすぎたトーストと焼かなさすぎたトーストの焼き時間が与えられます。最低何種類ですか?
まず、イベント全部混ぜてソート。oを焼きすぎた、xを焼かなさすぎたトーストのイベントとすると、最初がoだったり最後がxだったりするのはありえない→return -1;
つぎ
ooooo....oooooxxxxx....xxxxxのパターンは1種類で十分。
しかし、
ooooo....oooooxxxxx....xxxxxooooo....oooooxxxxx....xxxxxのパターンなどは1種類では出来ない。
まず、連続するoとxは圧縮して1つにできる。
すると上二つを除外したデータは必ず
oxoxoxox...xoxoxとなる。
ここで、
とすることが出来るので、せいぜい2種類しか必要ないことがわかる。
import java.util.*; public class ToastXToast{ public int bake(int []a,int[]b){ int[]c=new int[a.length+b.length]; for(int i=0;i<a.length;i++)c[i]=a[i]; for(int i=0;i<b.length;i++)c[a.length+i]=b[i]; Arrays.sort(c); boolean over[]=new boolean[c.length]; for(int i=0;i<c.length;i++){ for(int j=0;j<b.length;j++)if(c[i]==b[j])over[i]=true; } boolean now=false; if(over[0])return -1; if(!over[c.length-1])return -1; for(int i=0;i<c.length;i++){ if(over[i])now=true; else { if(now)return 2; } }return 1; } }
500:しりません
1000:しりません
Challenge:しりません
SystemTest:しりません
Result: 208.40 + 0 + 0 + 0 = 208.4 (238th)
Rating: 1431 -> 1519 (+88)
semiexpがここ最近毎回ぱない。毎回ってところが重要。
灰色抜け出しました。もうじき黄色でレーティング上げるべきな気がします。