TopCoder Marathon Match 103
おれやっぱこういう問題苦手や
provisional score: 968664.35
provisional rank: 12th / 52
Problem: ProductInventory
概要
- 在庫管理の問題
- 一応商品は野菜ということらしく expiration(廃棄までの日数) が設定されている
- 商品のストックが無いと客が確率でキレて二度と来ない
- 100 日間のうち最初の N 日間(N ∈ [10, 100]) だけがスコアに計上される
観測変数
- 商品数(itemCount ∈ [10, 100])
- 各商品の購入コスト(buy: buy[i] ∈ [1, 10])
- 各商品の販売価格(sell: sell[i] ∈ [buy[i]/2, buy[i]*3])
- 各商品の廃棄までの日数(expiration: expiration[i] ∈ [0, 15])
- 過去 10 日間の売上(1 日目の recentPurchases)
潜在変数
- スコア計算に用いられる日数 (scoreDays ∈ [10, 100])
- 各顧客が各商品を購入する確率 (purchase: purchase[custID][itemID] ∈ [0, 0.1])
- 各顧客が購入失敗時にキレる確率 (annoyance: annoyance[custID] ∈ [0, 0.1])
やったこと
- ローカルスコアを oracle score (需要ピッタリに在庫補充) との比で計算する
- ポアソン分布を思い出します
- パラメータをいじくります
- 累積分布関数が thresh を超えるような個数購入する
- thresh は expiraion[i] < 5 くらいの時に傾斜をつけると良いっぽい (コードの PARAMS[0] ~ PARAMS[15])
- 50 日を超えてから thresh にマイナス補正をかける (コードの PARAMS[16], PARAMS[17])
- lambda[i] に profit[i] (= sell[i] - buy[i]) と経過日数に応じた補正をかける (コードの PARAMS[18], PARAMS[19])
- 85 日を過ぎたら在庫補充数にマイナス補正をかける (コードの PARAMS[20], PARAMS[21])
- lambda[i] = max(2.425, lambda[i]) (コードの PARAMS[22])
雑感
oracle score と比べて最終的に 86% くらいのスコアが出た．
フルサブ 50 ケースは不安だったので c++ にテスターを移植して 3000 ケースくらいでスコアの山を登ってた．(VC++ だと ppl.h が使えて便利)
確率マジでわからん
//#define _CRT_SECURE_NO_WARNINGS #include "bits/stdc++.h" #include <random> #include <unordered_map> #include <unordered_set> #ifdef _MSC_VER #include <ppl.h> #endif using namespace std; //呪文 #define DUMPOUT cerr #define DUMP(...) DUMPOUT<<" ";DUMPOUT<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl;DUMPOUT<<" ";dump_func(__VA_ARGS__) typedef unsigned uint; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; typedef pair<string, string> pss; template <typename _KTy, typename _Ty> ostream& operator << (ostream& o, const pair<_KTy, _Ty>& m) { o << "{" << m.first << ", " << m.second << "}"; return o; } template <typename _KTy, typename _Ty> ostream& operator << (ostream& o, const map<_KTy, _Ty>& m) { if (m.empty()) { o << "{ }"; return o; } o << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { o << ", " << *itr; } o << "}"; return o; } template <typename _KTy, typename _Ty> ostream& operator << (ostream& o, const unordered_map<_KTy, _Ty>& m) { if (m.empty()) { o << "{ }"; return o; } o << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { o << ", " << *itr; } o << "}"; return o; } template <typename _Ty> ostream& operator << (ostream& o, const vector<_Ty>& v) { if (v.empty()) { o << "{ }"; return o; } o << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { o << ", " << *itr; } o << "}"; return o; } template <typename _Ty> ostream& operator << (ostream& o, const set<_Ty>& s) { if (s.empty()) { o << "{ }"; return o; } o << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { o << ", " << *itr; } o << "}"; return o; } template <typename _Ty> ostream& operator << (ostream& o, const unordered_set<_Ty>& s) { if (s.empty()) { o << "{ }"; return o; } o << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { o << ", " << *itr; } o << "}"; return o; } template <typename _Ty> ostream& operator << (ostream& o, const stack<_Ty>& s) { if (s.empty()) { o << "{ }"; return o; } stack<_Ty> t(s); o << "{" << t.top(); t.pop(); while (!t.empty()) { o << ", " << t.top(); t.pop(); } o << "}"; return o; } template <typename _Ty> ostream& operator << (ostream& o, const list<_Ty>& l) { if (l.empty()) { o << "{ }"; return o; } o << "{" << l.front(); for (auto itr = ++l.begin(); itr != l.end(); ++itr) { o << ", " << *itr; } o << "}"; return o; } template <typename _KTy, typename _Ty> istream& operator >> (istream& is, pair<_KTy, _Ty>& m) { is >> m.first >> m.second; return is; } template <typename _Ty> istream& operator >> (istream& is, vector<_Ty>& v) { for (size_t i = 0; i < v.size(); i++) is >> v[i]; return is; } namespace aux { // print tuple template<typename Ty, unsigned N, unsigned L> struct tp { static void print(ostream& os, const Ty& v) { os << get<N>(v) << ", "; tp<Ty, N + 1, L>::print(os, v); } }; template<typename Ty, unsigned N> struct tp<Ty, N, N> { static void print(ostream& os, const Ty& v) { os << get<N>(v); } }; } template<typename... Tys> ostream& operator<<(ostream& os, const tuple<Tys...>& t) { os << "{"; aux::tp<tuple<Tys...>, 0, sizeof...(Tys) - 1>::print(os, t); os << "}"; return os; } template<typename A, size_t N, typename T> inline void Fill(A(&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); } void dump_func() { DUMPOUT << endl; } template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) { DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...); } struct SXor128 { unsigned x, y, z, w; SXor128() { x = 123456789; y = 362436069; z = 521288629; w = 88675123; } SXor128(int _w) { x = 123456789; y = 362436069; z = 521288629; w = _w; } void setSeed() { x = 123456789; y = 362436069; z = 521288629; w = 88675123; } void setSeed(int _w) { x = 123456789; y = 362436069; z = 521288629; w = _w; } unsigned nextUInt() { unsigned t = (x ^ (x << 11)); x = y; y = z; z = w; return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } unsigned nextUInt(unsigned mod) { unsigned t = (x ^ (x << 11)); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); return w % mod; } unsigned nextUInt(unsigned l, unsigned r) { unsigned t = (x ^ (x << 11)); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); return w % (r - l + 1) + l; } double nextDouble() { return double(nextUInt()) / UINT_MAX; } }; #define OFFICIAL #ifdef OFFICIAL vector<double> PARAMS({ 0.76, 0.92, 0.965, 0.975, 0.9875, 0.99, 0.99, 0.99, 0.99, 0.99, 0.99, 0.99, 0.99, 0.99, 0.99, 0.99, 50, 0.002, 0.013, 0.0006, 85, 0.09, 2.425 }); #else #include "json.hpp" vector<double> PARAMS; class ProductInventoryVis{ public: int score; int day; SXor128 rnd; int scoreDays; vector<int> buy; vector<int> sell; vector<int> expiration; vector<bool> dead; vector<vector<double>> purchase; vector<double> annoyance; vector<int> purchases; vector<int> sellToCustomer; vector<vector<int>> inventory; vector<bool> unsatisfiedCustomer; vector<int> unsatisfiedProduct; int itemCount; int custCount; void generateTestCase(unsigned x){ rnd.setSeed(x); for(int i = 0; i < 100; i++) rnd.nextUInt(); score = 0; day = 0; itemCount = rnd.nextUInt(91) + 10; custCount = rnd.nextUInt(51) + 50; scoreDays = rnd.nextUInt(91) + 10; buy = vector<int>(itemCount, 0); sell = vector<int>(itemCount, 0); expiration = vector<int>(itemCount, 0); purchases = vector<int>(itemCount, 0); sellToCustomer = vector<int>(itemCount, 0); inventory = vector<vector<int>>(16, vector<int>(itemCount, 0)); annoyance = vector<double>(custCount, 0); purchase = vector<vector<double>>(custCount, vector<double>(itemCount, 0)); unsatisfiedCustomer = vector<bool>(custCount, false); dead = vector<bool>(custCount, false); unsatisfiedProduct = vector<int>(itemCount); for(int i = 0; i < itemCount; i++){ buy[i] = rnd.nextUInt(10) + 1; sell[i] = buy[i] / 2 + rnd.nextUInt(1 + 3 * buy[i] - buy[i] / 2); expiration[i] = rnd.nextUInt(16); } for(int i = 0; i < custCount; i++){ annoyance[i] = rnd.nextDouble() * 0.1; for(int j = 0; j < itemCount; j++){ purchase[i][j] = rnd.nextDouble() * 0.1; for(int k = 0; k < 10; k++){ if(rnd.nextDouble() < purchase[i][j]){ purchases[j]++; } } } } } bool tryBuy(int itemNumber){ for(int i = 0; i < 16; i++){ if(inventory[i][itemNumber] > 0){ inventory[i][itemNumber]--; return true; } } return false; } int processDay(const vector<int>& order){ int ret = 0; for(int i = 0; i < itemCount; i++){ purchases[i] = 0; } for(int i = 0; i < itemCount; i++){ ret -= buy[i] * order[i]; inventory[expiration[i]][i] = order[i]; } unsatisfiedCustomer = vector<bool>(custCount, false); sellToCustomer = vector<int>(itemCount, 0); unsatisfiedProduct = vector<int>(itemCount, 0); for(int i = 0; i < custCount; i++){ for(int j = 0; j < purchase[i].size(); j++){ double r1 = rnd.nextDouble(); double r2 = rnd.nextDouble(); if(dead[i]) continue; if(r1 < purchase[i][j]){ if(tryBuy(j)){ sellToCustomer[j]++; ret += sell[j]; purchases[j]++; } else{ unsatisfiedProduct[j]++; if(r2 < annoyance[i]){ dead[i] = true; unsatisfiedCustomer[i] = true; } } } } } for(int i = 0; i < 15; i++){ inventory[i] = inventory[i + 1]; } inventory[15] = vector<int>(itemCount, 0); day++; return ret; } }; class ProductInventoryOracle { vector<int> buy; vector<int> sell; vector<int> expiration; int oracleDay; public: ProductInventoryVis vis; int itemCount; ProductInventoryOracle(ProductInventoryVis _vis) : vis(_vis) {} int init(vector<int> _buy, vector<int> _sell, vector<int> _expiration){ buy = _buy; sell = _sell; expiration = _expiration; oracleDay = vis.scoreDays; itemCount = _buy.size(); return 0; } vector<int> order(vector<int> yesterday){ vis.processDay(vector<int>(itemCount, 100)); return vis.purchases; } }; #endif class ProductInventory { int day; int itemCount; vector<int> buy; vector<int> sell; vector<int> expiration; vector<int> purchases; vector<vector<int>> inventory; vector<int> itemPurchases; vector<double> lambda; int totalDay; vector<int> profit; vector<double> fact; double factorial(int n) { double ret = 1; for (int k = 1; k <= n; k++) ret *= k; return ret; } double poissonDist(int k, double lambda) { return pow(lambda, k) * exp(-lambda) / fact[k]; } public: int init(vector<int> _buy, vector<int> _sell, vector<int> _expiration) { day = 0; totalDay = 9; buy = _buy; sell = _sell; expiration = _expiration; itemCount = buy.size(); purchases = vector<int>(itemCount, 0); inventory = vector<vector<int>>(16, vector<int>(itemCount, 0)); lambda = vector<double>(itemCount, 0.0); itemPurchases = vector<int>(itemCount, 0); profit = vector<int>(itemCount); for (int i = 0; i < itemCount; i++) profit[i] = sell[i] - buy[i]; fact = vector<double>(256, 1.0); { double x = 1.0; for (int i = 1; i < 256; i++) { x *= i; fact[i] = x; } } return 0; } vector<int> order(vector<int> yesterday) { day++; totalDay++; if (day == 1) { for (int i = 0; i < itemCount; i++) { itemPurchases[i] += yesterday[i]; lambda[i] = max(PARAMS[22], (double)yesterday[i] / totalDay); } } else { for (int i = 0; i < itemCount; i++) { itemPurchases[i] += yesterday[i]; lambda[i] = max(PARAMS[22], (double)itemPurchases[i] / totalDay); } for (int j = 0; j < itemCount; j++) { for (int i = 0; i < 16; i++) { if (yesterday[j]) { int x = min(yesterday[j], inventory[i][j]); inventory[i][j] -= x; yesterday[j] -= x; } else break; } } for (int i = 0; i < 15; i++) inventory[i] = inventory[i + 1]; inventory[15] = vector<int>(itemCount, 0); } for (int i = 0; i < itemCount; i++) { lambda[i] += profit[i] * PARAMS[18] + (100 - day) * PARAMS[19]; } vector<int> storeInventory(itemCount, 0); for (int i = 0; i < itemCount; i++) { int l; double cum = 0.0; double thresh = PARAMS[expiration[i]]; if (day >= PARAMS[16]) thresh -= (day - PARAMS[16]) * PARAMS[17]; for (l = 0; cum < thresh; l++) cum += poissonDist(l, lambda[i]); l--; int s = 0; for (int j = 0; j < 16; j++) s += inventory[j][i]; int t = max(0, l - s); if (day >= PARAMS[20]) { t -= (day - PARAMS[20]) * PARAMS[21]; t = max(t, 0); } storeInventory[i] = t; inventory[expiration[i]][i] += t; } return storeInventory; } }; #ifdef OFFICIAL // Do not submit the main. int main() { int n; vector<int> buy; vector<int> sell; vector<int> expiration; vector<int> yesterday; vector<int> res; cin >> n; buy.resize(n); for (int i = 0; i < n; i++) { cin >> buy[i]; } cin >> n; sell.resize(n); for (int i = 0; i < n; i++) { cin >> sell[i]; } cin >> n; expiration.resize(n); for (int i = 0; i < n; i++) { cin >> expiration[i]; } ProductInventory *sol = new ProductInventory; cout << sol->init(buy, sell, expiration) << "\n"; cout << flush; for (int k = 0; k < 100; k++) { cin >> n; yesterday.resize(n); for (int i = 0; i < n; i++) { cin >> yesterday[i]; } res = sol->order(yesterday); cout << res.size() << "\n"; for (int i = 0; i < (int)res.size(); i++) { cout << res[i] << "\n"; } cout << flush; } delete sol; return 0; } #else int solve_oracle(int seed){ ProductInventoryVis vis; vis.generateTestCase(seed); ProductInventoryOracle sol(vis); sol.init(vis.buy, vis.sell, vis.expiration); vector<int> res; for(int k = 0; k < 100; k++){ res = sol.order(vis.purchases); int thisProfit = vis.processDay(res); if(k < vis.scoreDays){ vis.score += thisProfit; } } return std::max(0, vis.score); } int solve(int seed){ ProductInventoryVis vis; vis.generateTestCase(seed); //vis.vis(); ProductInventory *sol = new ProductInventory; sol->init(vis.buy, vis.sell, vis.expiration); vector<int> res; for(int k = 0; k < 100; k++){ res = sol->order(vis.purchases); int thisProfit = vis.processDay(res); if(k < vis.scoreDays){ vis.score += thisProfit; } } delete sol; return std::max(0, vis.score); } int _main(int argc, char** argv) { PARAMS = vector<double>(100); for (int i = 1; i < argc; i++) { PARAMS[i - 1] = atof(argv[i]); } int seed = PARAMS[0]; int score = solve(seed); int score_oracle = solve_oracle(seed); cerr << "Score: " << score << "/" << score_oracle << endl; return 0; } int main(int argc, char** argv){ PARAMS = vector<double>(100); for(int i = 1; i < argc; i++){ PARAMS[i - 1] = atof(argv[i]); } nlohmann::json oracle; ifstream ifs("score_oracle/score_oracle.json"); ifs >> oracle; int numTest = 1000; vector<int> scores_oracle(numTest + 1); for (int i = 1; i <= numTest; i++) { string s = to_string(i); string sc = oracle[s]; scores_oracle[i] = stoi(sc); } ifs.close(); double ratio = 0; #ifdef _MSC_VER concurrency::parallel_for(1, numTest + 1, [&](int seed) { #else for (int seed = 1; seed <= numTest; seed++) { #endif int score = solve(seed); int score_oracle = scores_oracle[seed]; if (score_oracle > 0) { ratio += (double)score / score_oracle; } if (score > score_oracle) { cerr << "beyond oracle: " << seed << ", " << score << ", " << score_oracle << endl; } #ifdef _MSC_VER }); #else } #endif ratio /= numTest; ratio *= 1000000; cerr << "Ratio: " << ratio << endl; return 0; } #endif
