TopCoder SRM 588 Div 2 oo- 1180->1211

またDiv 1になりました

250: KeyDungeonDiv2

いくつかのドアがあり、それぞれいくつかの赤の鍵穴と緑の鍵穴がある。
また赤の鍵と緑の鍵と白の鍵の個数が与えられる

赤の鍵と緑の鍵はそれぞれの色の鍵穴に対してだけ使用できる。
白の鍵はどの鍵穴に対しても使用できる
ドアを開け終われば鍵は再利用できる。

このときドアをいくつ開けられるか答える

それぞれのドアについて開けられるか確かめるだけ

public class KeyDungeonDiv2 { 

  public int countDoors(int[] doorR, int[] doorG, int[] keys) { 
    int count = 0; 
    int L = doorR.length; 

    for(int i = 0; i < L; i++) { 
      if(doorR[i] <= keys[0] + keys[2]) { 
        int res = Math.min(Math.max(0, keys[2] - doorR[i] + keys[0]), keys[2]); 
        if(doorG[i] <= keys[1] + res) { 
          count++; 
        } 
      } 
    } 

    return count; 
  } 

}

500: GUMIAndSongsDiv2

ある時間Tの間にいくつかの曲を選んで歌う。
その曲自体の時間の他に、曲のトーンの違いの大きさによる時間が必要になる
このとき、歌える最大曲数を答える。

歌う曲の順番はトーンが小さい順、あるいは大きい順にすれば良い
曲の数が最大15なので、ある曲を含むかどうかのすべての場合について計算しても十分間に合う

import java.util.ArrayList; 
import java.util.Collections; 

public class GUMIAndSongsDiv2 { 

  public int maxSongs(int[] duration, int[] tone, int T) { 
    int count = 0; 
    int upper = 1; 
    int L = duration.length; 
    upper <<= L; 
    for(int i = 1; i < upper; i++) { 
      int temp = i; 

      ArrayList<Integer> list = new ArrayList<Integer>(); 

      int time = 0; 
      for(int j = 0; j < L; j++) { 
        if(temp % 2 == 1) { 
          list.add(tone[j]); 
          time += duration[j]; 
        } 
        temp /= 2; 
      } 

      Collections.sort(list); 

      int num_item = list.size(); 

      int start = list.get(0); 
      for(int k = 1; k < num_item; k++) { 
        int now = list.get(k); 

        time += now - start; 

        start = now; 
      } 
      if((time <= T) && (num_item > count)) { 
        count = num_item; 
      } 

    } 
    return count; 
  } 

}