mayoko’s diary

プロコンとかいろいろ。

SRM 512 div1 easy:MysteriousRestaurant

SRM512の練習会に参加しました。

結果はeasyをそこそこ早解きしてmedはいつも通り落としてそこそこでした。SRM509くらいから急にmedの難易度が上がってる気がする。今回はeasyもまぁまぁ難しかった。

解法

x日通うと決めた時にコストを最小にしようとすることは簡単に出来ます。

x日通う場合,各曜日にどの種類の商品を選ぶかは,x日の合計でどれが最小コストになるかを選ぶだけで済むからです。

これを用いて,「x日通えるかどうか」を判定することが出来ます。

僕は無駄に二分探索しましたが,練習会で二分探索を使ってる人は他にいないように見えました(普通に大きい方から線形探索してた)。

int parse(char c) {
    if ('0' <= c && c <= '9') return c-'0';
    if ('A' <= c && c <= 'Z') return c-'A' + 10;
    return c-'a' + 36;
}

vector<string> price;
int cost[55][7];

bool ok(int x, int budget) {
    int m = price[0].size();
    int n = price.size();
    memset(cost, 0, sizeof(cost));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < 7; j++) {
            for (int y = j; y < x; y += 7) {
                cost[i][j] += parse(price[y][i]);
            }
        }
    }
    int need = 0;
    for (int i = 0; i < 7; i++) {
        int mincost = 100000000;
        for (int j = 0; j < m; j++) {
            mincost = min(mincost, cost[j][i]);
        }
        need += mincost;
    }
    return budget >= need;
}

class MysteriousRestaurant {
public:
    int maxDays(vector <string> prices, int budget) {
        price = prices;
        int low = 0, high = prices.size()+1;
        while (high - low > 1) {
            int med = (high + low) / 2;
            if (ok(med, budget)) low = med;
            else high = med;
        }
        return low;
    }
};