#302510 (C++14) No.5003 物理好きクリッカー

提出ソース

結果

問題	No.5003 物理好きクリッカー
ユーザー	risujiroh
提出日時	2018-12-08 00:29:03
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	495 ms / 10,000 ms
コード長	13,315 bytes
コンパイル時間	1,911 ms
実行使用メモリ	22,008 KB
スコア	263,801,359,267
平均クエリ数	10000.00
最終ジャッジ日時	2021-07-19 09:07:25
合計ジャッジ時間	21,383 ms
ジャッジサーバーID （参考情報）	judge15 / judge12
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	476 ms 21,528 KB
testcase_01	AC	482 ms 21,876 KB
testcase_02	AC	468 ms 21,504 KB
testcase_03	AC	454 ms 21,528 KB
testcase_04	AC	440 ms 21,516 KB
testcase_05	AC	444 ms 21,888 KB
testcase_06	AC	464 ms 21,528 KB
testcase_07	AC	465 ms 21,504 KB
testcase_08	AC	447 ms 21,852 KB
testcase_09	AC	457 ms 21,900 KB
testcase_10	AC	450 ms 21,348 KB
testcase_11	AC	488 ms 21,696 KB
testcase_12	AC	455 ms 21,372 KB
testcase_13	AC	490 ms 21,864 KB
testcase_14	AC	464 ms 21,672 KB
testcase_15	AC	437 ms 21,852 KB
testcase_16	AC	456 ms 21,804 KB
testcase_17	AC	453 ms 21,864 KB
testcase_18	AC	459 ms 21,348 KB
testcase_19	AC	495 ms 21,864 KB
testcase_20	AC	465 ms 21,876 KB
testcase_21	AC	460 ms 21,864 KB
testcase_22	AC	447 ms 21,864 KB
testcase_23	AC	444 ms 21,852 KB
testcase_24	AC	449 ms 21,372 KB
testcase_25	AC	453 ms 21,804 KB
testcase_26	AC	448 ms 21,852 KB
testcase_27	AC	440 ms 21,324 KB
testcase_28	AC	456 ms 21,924 KB
testcase_29	AC	456 ms 21,372 KB
testcase_30	AC	483 ms 21,876 KB
testcase_31	AC	450 ms 21,504 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


constexpr lint inf = 1e18;

// input
constexpr int T = 10'000;
string S;

// outoput
enum struct ActionType { CLICK, BUY, SELL, REINFORCE, ENHCLICK, NOTHING };
struct Action { ActionType type; int id; };
V<Action> actions(T);

// status
lint score;
int click_level;
lint click_power, click_cost;
const V<string> name{"hand", "lily", "factory", "casino", "grimoire"};
V<> cnt, level;
V<lint> power, price, cost;
bool fever, sale;
V<> rest;

mt19937 mt(steady_clock::now().time_since_epoch().count());
// [a, b)
int rng(int a, int b) {
  assert(a < b);
  return uniform_int_distribution<>(a, b - 1)(mt);
}
double rng(double a, double b) {
  assert(a < b);
  return uniform_real_distribution<>(a, b)(mt);
}

void read_input() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  int _;
  cin >> _;
  assert(_ == T);
  cin >> S;
}

void generate_input() {
  S.assign(T, 'N');
  string bfs = "BFS";
  for (int t = rng(0, 200); t < T; t += rng(100, 201)) {
    S[t] = bfs[rng(0, 3)];
  }
}

void write_output() {
  for (const Action& action : actions) {
    switch(action.type) {
      case ActionType::CLICK:
        cout << "click" << endl;
        break;
      case ActionType::BUY:
        cout << "buy " << name[action.id] << endl;
        break;
      case ActionType::SELL:
        cout << "sell " << name[action.id] << endl;
        break;
      case ActionType::REINFORCE:
        cout << "reinforce " << name[action.id] << endl;
        break;
      case ActionType::ENHCLICK:
        cout << "enhclick " << endl;
        break;
      case ActionType::NOTHING:
        cout << "nothing" << endl;
        break;
    }
    string str;
    cin >> str;
    assert(str == "ok");
  }
}

void init() {
  score = 0;
  click_level = 0;
  click_power = 1, click_cost = 15;
  cnt.assign(5, 0);
  level.assign(5, 0);
  power = {1, 10, 120, 2'000, 25'000};
  price = {150, 2'000, 30'000, 600'000, 10'000'000};
  cost.resize(5);
  for (int id = 0; id < 5; ++id) cost[id] = 10 * price[id];
  fever = sale = false;
  rest.assign(T + 1, 0);
  auto is_fever = [](int t) -> bool {
    for (int i = 1; i <= 20; ++i) {
      if (t - i < 0) break;
      if (S[t - i] == 'F') return true;
    }
    return false;
  };
  for (int t = T - 1; t >= 0; --t) {
    rest[t] = rest[t + 1] + (is_fever(t) ? 7 : 1);
  }
}

bool can_buy(int id) {
  lint curr_price = sale ? (9 * price[id] + 9) / 10 : price[id];
  return score >= curr_price;
}

bool can_sell(int id) {
  return cnt[id] > 0;
}

bool can_reinforce(int id) {
  lint curr_cost = sale ? (9 * cost[id] + 9) / 10 : cost[id];
  return score >= curr_cost;
}

bool can_enhclick() {
  lint curr_cost = sale ? (9 * click_cost + 9) / 10 : click_cost;
  return score >= curr_cost;
}

bool can_act(const Action& action) {
  switch(action.type) {
    case ActionType::BUY:
      return can_buy(action.id);
    case ActionType::SELL:
      return can_sell(action.id);
    case ActionType::REINFORCE:
      return can_reinforce(action.id);
    case ActionType::ENHCLICK:
      return can_enhclick();
    default:
      return true;
  }
}

void click() {
  score += click_power * (fever ? 7 : 1);
}

void buy(int id) {
  lint curr_price = sale ? (9 * price[id] + 9) / 10 : price[id];
  score -= curr_price;
  ++cnt[id];
  price[id] = (6 * price[id] + 4) / 5;
}

void sell(int id) {
  price[id] = price[id] * 5 / 6;
  --cnt[id];
  score += (price[id] + 3) / 4;
}

void reinforce(int id) {
  lint curr_cost = sale ? (9 * cost[id] + 9) / 10 : cost[id];
  score -= curr_cost;
  ++level[id];
  power[id] <<= 1;
  cost[id] *= 10;
}

void enhclick() {
  lint curr_cost = sale ? (9 * click_cost + 9) / 10 : click_cost;
  score -= curr_cost;
  ++click_level;
  click_power <<= 1;
  click_cost *= 10;
}

void act(const Action& action) {
  assert(can_act(action));
  switch(action.type) {
    case ActionType::CLICK:
      click();
      break;
    case ActionType::BUY:
      buy(action.id);
      break;
    case ActionType::SELL:
      sell(action.id);
      break;
    case ActionType::REINFORCE:
      reinforce(action.id);
      break;
    case ActionType::ENHCLICK:
      enhclick();
      break;
    case ActionType::NOTHING:
      break;
  }
}

void produce() {
  for (int id = 0; id < 5; ++id) {
    score += power[id] * cnt[id] * (fever ? 7 : 1);
  }
}

void affect(int t) {
  switch(S[t]) {
    case 'B':
      score += (score + 99) / 100;
      break;
    case 'F':
      fever = true;
      break;
    case 'S':
      sale = true;
      break;
  }
  if (t - 20 >= 0 and S[t - 20] == 'F') fever = false;
  if (t - 1 >= 0 and S[t - 1] == 'S') sale = false;
}

void undo_click() {
  score -= click_power * (fever ? 7 : 1);
}

void undo_buy(int id) {
  price[id] = price[id] * 5 / 6;
  --cnt[id];
  lint curr_price = sale ? (9 * price[id] + 9) / 10 : price[id];
  score += curr_price;
}

void undo_sell(int id) {
  score -= (price[id] + 3) / 4;
  ++cnt[id];
  price[id] = (6 * price[id] + 4) / 5;
}

void undo_reinforce(int id) {
  cost[id] /= 10;
  power[id] >>= 1;
  --level[id];
  lint curr_cost = sale ? (9 * cost[id] + 9) / 10 : cost[id];
  score += curr_cost;
}

void undo_enhclick() {
  click_cost /= 10;
  click_power >>= 1;
  --click_level;
  lint curr_cost = sale ? (9 * click_cost + 9) / 10 : click_cost;
  score += curr_cost;
}

void undo_act(const Action& action) {
  switch(action.type) {
    case ActionType::CLICK:
      undo_click();
      break;
    case ActionType::BUY:
      undo_buy(action.id);
      break;
    case ActionType::SELL:
      undo_sell(action.id);
      break;
    case ActionType::REINFORCE:
      undo_reinforce(action.id);
      break;
    case ActionType::ENHCLICK:
      undo_enhclick();
      break;
    case ActionType::NOTHING:
      break;
  }
}

void undo_produce() {
  for (int id = 0; id < 5; ++id) {
    score -= power[id] * cnt[id] * (fever ? 7 : 1);
  }
}

void undo_affect(int t) {
  switch(S[t]) {
    case 'B':
      score = score * 100 / 101;
      break;
    case 'F':
      fever = false;
      break;
    case 'S':
      sale = false;
      break;
  }
  if (t - 20 >= 0 and S[t - 20] == 'F') fever = true;
  if (t - 1 >= 0 and S[t - 1] == 'S') sale = true;
}

void next_turn(const Action& action, int t) {
  act(action);
  produce();
  affect(t);
}

void prev_turn(const Action& action, int t) {
  undo_affect(t);
  undo_produce();
  undo_act(action);
}

lint calc_power() {
  lint res = click_power;
  for (int id = 0; id < 5; ++id) {
    res += power[id] * cnt[id];
  }
  return res;
}

double eval_click(int t) {
  return click_power;
}

// 待つターン数（調整の余地あり？）
double a = 0.07, b = 0;
int th(int t) {
  return a * t + b;
}

bool should_wait(int t) {
  return false;
  if (t < 4800) return false;
  for (int i = 1; i <= 5 and t + i < T; ++i) {
    if (S[t + i] == 'B') return true;
  }
  for (int i = 1; i <= 14 and t + i < T; ++i) {
    if (S[t + i] == 'S') return true;
  }
  return false;
}

double eval_buy(int id, int t) {
  // if (id < 4 and cnt[id + 1]) return 0;
  if (price[id] > score + calc_power() * (rest[t] - rest[min(t + th(t), T)])) return 0;
  if (should_wait(t)) return 0;
  lint curr_price = sale ? (9 * price[id] + 9) / 10 : price[id];
  return power[id] * rest[t] - curr_price + (price[id] + 3) / 4;
}

double eval_sell(int id, int t) {
  if (!can_sell(id)) return 0;
  int total_cnt = accumulate(next(begin(cnt), id), end(cnt), 0);
  if (total_cnt < T - t) return 0;
  return inf;
  // return (price[id] * 5 / 6 + 3) / 4 - power[id] * rest[t];
}

double eval_reinforce(int id, int t) {
  if (cost[id] > score + calc_power() * (rest[t] - rest[min(t + th(t), T)])) return 0;
  if (should_wait(t)) return 0;
  lint curr_cost = sale ? (9 * cost[id] + 9) / 10 : cost[id];
  return power[id] * cnt[id] * rest[t] - curr_cost;
}

double eval_enhclick(int t) {
  if (click_cost > score + calc_power() * (rest[t] - rest[min(t + th(t), T)])) return 0;
  if (should_wait(t)) return 0;
  lint curr_cost = sale ? (9 * click_cost + 9) / 10 : click_cost;
  return click_power * (T - t) - curr_cost;
}

lint eval_act(const Action& action, int t) {
  int _t = t;
  while (!can_act(action)) {
    next_turn({ActionType::CLICK, -1}, _t++);
    if (_t == T or _t == t + (int) (0.07 * t)) {
      while (--_t >= t) {
        prev_turn({ActionType::CLICK, -1}, _t);
      }
      return 0;
    }
  }
  next_turn(action, _t);
  lint res = score;
  res += click_power * (T - _t);
  for (int id = 0; id < 5; ++id) {
    res += power[id] * cnt[id] * rest[_t];
  }
  prev_turn(action, _t--);
  while (_t >= t) {
    prev_turn({ActionType::CLICK, -1}, _t--);
  }
  return res;
}

void solve() {
  int Tf = 8000;
  for (int t = 0; t < Tf; ++t) {
    lint curr = 0, best = curr;
    Action curr_action = {ActionType::NOTHING, -1}, best_action = curr_action;
    auto update = [&]() -> void {
      curr = eval_act(curr_action, t);
      if (curr > best) {
        best = curr;
        best_action = curr_action;
      }
    };
    // click
    curr_action = {ActionType::CLICK, -1};
    update();
    // facilities
    for (int id = 0; id < 5; ++id) {
      curr_action = {ActionType::BUY, id};
      update();
      // curr_action = {ActionType::SELL, id};
      // update();
      curr_action = {ActionType::REINFORCE, id};
      update();
    }
    // enhclick
    curr_action = {ActionType::ENHCLICK, -1};
    update();
    if (can_act(best_action)) {
      actions[t] = best_action;
    } else {
      actions[t] = {ActionType::CLICK, -1};
    }
    next_turn(actions[t], t);
  }
  {
    int t = T - 1;
    for (int id = 4; id >= 0; --id) {
      for (int _ = 0; _ < cnt[id]; ++_)  {
        actions[t--] = {ActionType::SELL, id};
      }
    }
    while (t >= Tf) {
      actions[t--] = {ActionType::CLICK, -1};
    }
  }
  for (int t = Tf; t < T; ++t) {
    next_turn(actions[t], t);
  }
}

void print_data() {
  init();
  int click_cnt = 0;
  V<> buy_cnt(5), sell_cnt(5), reinforce_cnt(5);
  int enhclick_cnt = 0;
  lint _score, bonus_score = 0, sell_score = 0, click_score = 0;
  V<lint> prod_score(5);
  for (int t = 0; t < T; ++t) {
    switch(actions[t].type) {
      case ActionType::CLICK:
        ++click_cnt;
        break;
      case ActionType::BUY:
        ++buy_cnt[actions[t].id];
        cerr << "turn: " << setw(4) << t << '\t' << "buy " << name[actions[t].id] << endl;
        break;
      case ActionType::SELL:
        ++sell_cnt[actions[t].id];
        cerr << "turn: " << setw(4) << t << '\t' << "sell " << name[actions[t].id] << endl;
        break;
      case ActionType::REINFORCE:
        ++reinforce_cnt[actions[t].id];
        cerr << "turn: " << setw(4) << t << '\t' << "reinforce " << name[actions[t].id] << endl;
        break;
      case ActionType::ENHCLICK:
        ++enhclick_cnt;
        cerr << "turn: " << setw(4) << t << '\t' << "enhclick" << endl;
        break;
    }
    _score = score;
    act(actions[t]);
    if (actions[t].type == ActionType::CLICK) click_score += score - _score;
    if (actions[t].type == ActionType::SELL) sell_score += score - _score;
    produce();
    for (int id = 0; id < 5; ++id) {
      prod_score[id] += power[id] * cnt[id] * (fever ? 7 : 1);
    }
    _score = score;
    affect(t);
    bonus_score += score - _score;
  }
  cerr << "total_score: " << setw(11) << score << endl;
  cerr << "bonus_score: " << setw(11) << bonus_score << endl;
  cerr << "click_score: " << setw(11) << click_score << endl;
  cerr << " sell_score: " << setw(11) << sell_score << endl;
  for (int id = 0; id < 5; ++id) {
    cerr << "pr_score[" << id << "]: " << setw(11) << prod_score[id] << endl;
  }
  cerr << "click_cnt: " << click_cnt << endl;
  for (int id = 0; id < 5; ++id) {
    cerr << "buy_cnt[" << id << "]: " << buy_cnt[id] << '\t';
    cerr << "sell_cnt[" << id << "]: " << sell_cnt[id] << '\t';
    cerr << "reinforce_cnt[" << id << "]: " << reinforce_cnt[id] << endl;
  }
  cerr << "enhclick_cnt: " << enhclick_cnt << endl;
}

int main(int argc, char* argv[]) {
  if (argc == 1) {
    read_input();
    init();
    solve();
    write_output();
  } else {
    int n = stoi(argv[1]);
    V<double> scores(n);
    for (int i = 0; i < n; ++i) {
      lint total_score = 0;
      for (int _ = 0; _ < 32; ++_) {
        generate_input();
        init();
        solve();
        cerr << score << '\n';
        if (_ == 31) print_data();
        total_score += score;
      }
      cerr << total_score << '\n';
      scores[i] = total_score;
    }
    double avg_score = accumulate(begin(scores), end(scores), 0.0) / n;
    cerr << fixed << setprecision(2);
    cerr << "avg_score: " << setw(15) << avg_score << endl;
    double sd_score = 0;
    for (int i = 0; i < n; ++i) sd_score += pow(scores[i] - avg_score, 2);
    sd_score = sqrt(sd_score / n);
    cerr << " sd_score: " << setw(15) << sd_score << endl;
    cout << -(avg_score - sd_score) << endl;
  }
}

yukicoder

結果

テストケース

ソースコード