SRM 588 div2

初するめ。

250 KeyDungeonDiv2

鍵は消え去らないので普通に左から見ていく。
足りない分は白鍵で補充してやる。

class KeyDungeonDiv2 {
public:
  int countDoors(vector <int> doorR, vector <int> doorG, vector <int> keys) {
    int n = sz(doorR) ;
    int ret = 0;
    rep(i,n){
      int redkey = keys[0];
      int greenkey = keys[1];
      int whitekey = keys[2];
 
      int red = doorR[i],green = doorG[i];
      redkey -= red; 
      greenkey -= green;
      if(redkey >= 0 && greenkey >= 0){
	ret++;continue;
      }
      int a = 0;
      if(redkey < 0)a -= redkey;
      if(greenkey < 0)a -= greenkey;
      if(whitekey >= a)ret++;
    }
    return ret;
        
  }
};

500 GUMIAndSongsDiv2

区間の差を最小限に抑えるには、
toneを基準に歌をソートしてやる。

あとは
dp[今の個数][一個前の歌の添字] = 最短時間
やって、

dp[i][j] <= T のうち 最大の i が答えである。

class GUMIAndSongsDiv2 {

public:

  int maxSongs(vector <int> duration, vector <int> tone, int T) {	  
    vector < int > d = duration;
    int n = sz(d);
    vector < Pi > v;

    rep(i,n)
      v.pb(mp(tone[i],d[i]));
    sort(ALL(v));
    int dp[55][55];

    // fr : tone , sc : d
    rep(i,n+1)rep(j,n)dp[i][j] = INF;
    rep(i,n)dp[1][i] = v[i].sc;
	  
	  
    // dp[今の個数][一個前の歌の添字] = 最短時間
    reps(i,2,n+1)
      rep(j,n)
      rep(k,j)
      dp[i][j] = min(dp[i][j],dp[i-1][k] + v[j].sc + abs(v[i-1].fr-v[k].fr));
	    
    int ret = 0;
    rep(i,n+1){
      rep(j,n){
	if(dp[i][j] <= T)ret = max(ret,i);
      }
    }	  

    return ret;
  }
};

Easyしばらく読み間違えていて、書き直したものの
一個前のデータがhogeって提出してEasy落とした。

medは読まずに終わってしまった。

時間配分と解釈が狂うと怖い。

本番に弱いタイプなので早くSRMに慣れたい。

次回にはmedまでPassしたい。