SRM 512 Div2 Medium MysteriousRestaurant

問題

ミステリアスなレストランに可能な限り通い続けたい.そのレストランには次のようなミステリアスなルールが幾つか存在する.
1.一日につき一つの皿しか食べられない.
2.i日目にj番目の皿を食べたら(i+7)日目にはj番目の皿しか買うことが出来ない.
3.一日に一つのお皿も買わなかったら二度とそのレストランで皿を買うことが出来ない.
皿は料理と訳せばよかった・・・
料理の価格は毎日変動する.予算が与えられた時レストランに通い続ける事ができる最大の日数を求めよ.

解答

まず,x日通い続けることが出来るかどうか判定する方法を考えよう.
曜日をy, 料理をjとすると,x日全体に曜日yに料理jを選んだ時にかかるコストを計算することが出来る.これをすべての曜日と料理の組み合わせについて計算する.最適な手法は各曜日に対して最小のコストとなる料理を選ぶことだ.その最適なコストが予算を超えなければx日通い続けることが出来る.最大のxを求めるために日数を2分探索して求めれば良い.

class MysteriousRestaurant
{ 
public: 
  int maxDays(vector <string> prices, int budget) 
    {
      int n = prices.size();
      int m = prices[0].size();
      vector<vector<int> > p(n, vector<int>(m, 0));
      int i, j;
      for(i = 0; i < n; i++){
        for(j = 0; j < m; j++){
          if ('0' <= prices[i][j] && prices[i][j] <= '9') p[i][j] = prices[i][j]-'0';
          else if ('A' <= prices[i][j] && prices[i][j] <= 'Z') p[i][j] = 10 + prices[i][j]-'A';
          else if ('a' <= prices[i][j] && prices[i][j] <= 'z') p[i][j] = 36 + prices[i][j]-'a';
        }
      }
      int low = 0;
      int high = n+1;
      while(low + 1 < high){
        int mid = (high + low) / 2;
        vector<vector<int> > M(7, vector<int>(m, 0));
        for(i = 0; i < mid; i++){
          for(j = 0; j < m; j++){
            M[i%7][j] += p[i][j];
          }
        }
        int count = 0;
        for (i = 0; i < 7; i++){
          int min_count = 5000;
          for(j = 0; j < m; j++){
            min_count = min(min_count, M[i][j]);
          }
          count += min_count;
        }
        if (count <= budget){
          low = mid;
        }else{
          high = mid;
        }
      }
      return (high + low) /2;
    }
};