SRM512 Div1 Easy - MysteriousRestaurant

問題

　日間営業するレストランで夕食を食べることを考える。レストランは常に種類のパターンを用意しているが、ある曜日にあるパターンの夕食を食べると、同じ曜日には同じパターンの夕食した食べられない。日目の番目のパターンに対するコストを与えるので、コスト内で日目から連続して最大何日食べることができるかを求めよ。

解法

　日目まで食べられるとして、曜日に食べるべきパターンはそれぞれ独立に計算することができる。その計算にはかかり全体としてとなるが、制約からせいぜいにしかならないのでこれでこの問題が解けた。

反省

　いろいろガチャガチャいじっていたらなんか解けた。あまり理屈っぽく解いている気がしない。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class MysteriousRestaurant {
public:
    int maxDays(vector<string> prices, int budget) {
        for (ll i = prices.size(); i >= 0; i--) {
            ll cost = 0;
            for (ll j = 0; j < min((ll)7, i); j++) {
                ll j_cost = INT_MAX;
                for (ll k = 0; k < prices[0].size(); k++) {
                    ll c = 0;
                    for (ll l = j; l < i; l += 7) {
                        c += char2value(prices[l][k]);
                    }
                    j_cost = min(j_cost, c);
                }
                cost += j_cost;
            }
            if (cost <= budget) {
                return (int)i;
            }
        }
        return 0;
    }
private:
    ll char2value(char c) {
        if ('0' <= c && c <= '9') {
            return c - '0';
        } else if ('A' <= c && c <= 'Z') {
            return c - 'A' + 10;
        } else {
            return c - 'a' + 36;
        }
    }
};