tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

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となる。
ここで、
f:id:tozangezan:20110417031316j:image
とすることが出来るので、せいぜい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がここ最近毎回ぱない。毎回ってところが重要。

灰色抜け出しました。もうじき黄色でレーティング上げるべきな気がします。