Hatena::Grouptopcoder

kuuso1の日記

2014-05-09

SRM582 Div2Med/Div1Easy

| 02:22 | SRM582 Div2Med/Div1Easy  - kuuso1の日記 を含むブックマーク はてなブックマーク - SRM582 Div2Med/Div1Easy  - kuuso1の日記

  • 魔法少女たちの強さがintの配列で与えられる。
  • 敵は数グループおり、それぞれの強さと数がセットで与えられる。
  • 魔法少女たちはそれぞれ、自分の強さ以下の強さの敵を倒すことができるが、1匹倒すたびに疲労が1蓄積する。

敵を全滅させることができる戦い方のうち、少女たちの疲労の偏りをなくして全体を均一にするときの、最小値を求める。

倒せない時は-1を返す。

(制約)魔法少女の数、敵の種類≦50

   強さ:それぞれ≦100(div2)/10000(div1).敵の数:Div2Med 100(div2)/1E14(div1)

少女一人ずつがN回まで戦うことができるとして、Nについて2分探索する。

Div2Medは制約が小さいので、線形探索でも間に合いそう。

というか、小ささに騙されて最初適当に実装したら全然通らなかった。

public class SpaceWarDiv1 {
    public long minimalFatigue(int[] magicalGirlStrength, int[] enemyStrength, long[] enemyCount) {
	int N=magicalGirlStrength.Length;
	int M=enemyStrength.Length;
	Array.Sort(magicalGirlStrength);
	SortedList<int,long> SL=new SortedList<int,long>();
	for(int i=0;i<M;i++){
		if(!SL.ContainsKey(enemyStrength[i]))SL.Add(enemyStrength[i],0);
		SL[enemyStrength[i]]+=enemyCount[i];
	}

	if(SL.Keys[SL.Count-1]>magicalGirlStrength[N-1])return -1;

	long enemyall=0;
	for(int i=0;i<M;i++)enemyall+=enemyCount[i];
	
	long F=0;
	long l=0;
	long r=enemyall;
	
	while(r-l>1){
		F=(r+l)/2;
		bool chk=judge(F,SL,magicalGirlStrength);
		if(chk)r=F;
		if(!chk)l=F;
	}
	
	while(judge(F,SL,magicalGirlStrength))F--;
	while(!judge(F,SL,magicalGirlStrength))F++;
	return F;
    }
    
    bool judge(long F_,SortedList<int,long> SL_,int[] MGS){
    	SortedList<int,long> SL=new SortedList<int,long>();
    	for(int i=0;i<SL_.Count;i++)SL.Add(SL_.Keys[i],SL_.Values[i]);
    	
    	for(int i=0;i<MGS.Length;i++){
    		long res=F_;
    		for(int j=0;j<SL.Count;j++){
    			if(SL.Keys[j]>MGS[i])break;
    			
    			if(SL.Keys[j]<=MGS[i]){
    				if(res>=SL[SL.Keys[j]]){
    					res-=SL[SL.Keys[j]];
    					SL[SL.Keys[j]]=0;
    					continue;
    				}else{
    					SL[SL.Keys[j]]-=res;
    					res=0;
    					break;
    				}
    			}
    		}
    	}
	if(SL[SL.Keys[SL.Count-1]]>0)return false;
	return true;
    }

どうでもいいが初めてSortedListを使ってみた。この問題ではあんまりメリットはないな。。。