Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-07-15

TopCoder Single Round Match 512 Div.1 23:48 はてなブックマーク - TopCoder Single Round Match 512 Div.1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン

2500:26:57.423Passed System Test154.99
5000:47:49.875Opened0.00
10000:35:50.090Opented0.00
Challenge..0.00

部屋(Room 37) 8位,全体 458位

Rating : 1505 → 1513 (+8)

 下がらなかったから良し.

250 MysteriousRestaurant

問題文

 問題文

方針

 まず日にちNを固定します.N日までの食事を選んだ場合の合計金額をそれぞれで計算し,各曜日でその合計金額が最も小さいものを選ぶ.最後にそれぞれの曜日で選ばれた食事の金額を合計し,budgetより小さいかを判定します.

 日にちが増えるほど合計金額は単調に増えるので,日にちについての2分探索も出来ますが,今回の場合条件が小さいので,Nが大きい方から1ずつ減らしながら貪欲に調べても間に合います.

コード例
#include <string>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
 
using namespace std;
 
int toP(char c){
  if(c >= '0' && c <='9'){
    return c-'0';
  }else if(c >= 'A' && c<='Z'){
    return c-'A'+10;
  }else{
    return c-'a'+36;
  }
}
 
int n;
int m;
int cost[51][51];
int cost7[7][51];
 
int inf = 10000000;
 
bool ispossble(int day, int b){
  memset(cost7, 0, sizeof(cost7));

  for(int i = 0;i < day;i++){
    for(int j = 0;j < m;j++){
      cost7[i%7][j] += cost[i][j];
    }
  }

  int sum = 0;
  for(int i = 0; i < 7; i++){
    int mn = inf;
    for(int j = 0; j < m; j++){
      mn = min(mn, cost7[i][j]);
    }
    sum += mn;
  }
  return sum <= b;
}
  
class MysteriousRestaurant {
public:
int maxDays(vector <string> prices, int budget) {
  memset(cost, 0, sizeof(cost));
  n = prices.size();
  m = prices[0].size();

  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cost[i][j] = toP(prices[i][j]);
    }
  }
  
  for(int i = n;i>=0;i--){
    if(ispossble(i, budget)){
      return i;
    }
  }
}

};