結果

問題 No.5003 物理好きクリッカー
ユーザー risujirohrisujiroh
提出日時 2018-12-06 22:32:32
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 328 ms / 10,000 ms
コード長 9,033 bytes
コンパイル時間 2,082 ms
実行使用メモリ 22,020 KB
スコア 246,574,578,293
平均クエリ数 10000.00
最終ジャッジ日時 2021-07-19 09:00:21
合計ジャッジ時間 15,506 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 298 ms
21,864 KB
testcase_01 AC 293 ms
21,528 KB
testcase_02 AC 309 ms
21,936 KB
testcase_03 AC 316 ms
21,852 KB
testcase_04 AC 290 ms
21,528 KB
testcase_05 AC 292 ms
21,852 KB
testcase_06 AC 295 ms
21,516 KB
testcase_07 AC 290 ms
21,840 KB
testcase_08 AC 288 ms
21,372 KB
testcase_09 AC 315 ms
21,504 KB
testcase_10 AC 319 ms
21,516 KB
testcase_11 AC 292 ms
21,876 KB
testcase_12 AC 298 ms
21,876 KB
testcase_13 AC 300 ms
21,336 KB
testcase_14 AC 298 ms
21,528 KB
testcase_15 AC 300 ms
21,900 KB
testcase_16 AC 293 ms
21,312 KB
testcase_17 AC 328 ms
21,840 KB
testcase_18 AC 303 ms
21,936 KB
testcase_19 AC 297 ms
21,792 KB
testcase_20 AC 298 ms
21,528 KB
testcase_21 AC 301 ms
21,864 KB
testcase_22 AC 315 ms
21,852 KB
testcase_23 AC 324 ms
21,864 KB
testcase_24 AC 320 ms
21,492 KB
testcase_25 AC 316 ms
21,528 KB
testcase_26 AC 315 ms
21,516 KB
testcase_27 AC 298 ms
21,924 KB
testcase_28 AC 309 ms
21,516 KB
testcase_29 AC 301 ms
21,540 KB
testcase_30 AC 298 ms
21,852 KB
testcase_31 AC 298 ms
21,828 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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...); }


// 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;
lint click_power, click_cost;
const V<string> name{"hand", "lily", "factory", "casino", "grimoire"};
V<> cnt(5);
V<lint> power(5), price(5), cost(5);
bool fever, sale;
V<> rest(T + 1);

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_power = 1, click_cost = 15;
  fill(begin(cnt), end(cnt), 0);
  power = {1, 10, 120, 2'000, 25'000};
  price = {150, 2'000, 30'000, 600'000, 10'000'000};
  for (int id = 0; id < 5; ++id) cost[id] = 10 * price[id];
  fever = sale = false;
  rest[T] = 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;
  power[id] <<= 1;
  cost[id] *= 10;
}

void enhclick() {
  lint curr_cost = sale ? (9 * click_cost + 9) / 10 : click_cost;
  score -= curr_cost;
  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;
}

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

lint eval_click() {
  return click_power;
}

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

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

lint eval_sell(int id, int t) {
  return (price[id] * 5 / 6 + 3) / 4 - power[id] * rest[t];
}

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

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

void solve() {
  for (int t = 0; t < T; ++t) {
    lint best = 0, curr;
    Action best_action = {ActionType::NOTHING, -1};
    // click
    curr = eval_click();
    if (curr > best) {
      best = curr;
      best_action = {ActionType::CLICK, -1};
    }
    // facilities
    for (int id = 0; id < 5; ++id) {
      curr = eval_buy(id, t);
      if (curr > best) {
        best = curr;
        best_action = {ActionType::BUY, id};
      }
      curr = eval_sell(id, t);
      if (curr > best) {
        best = curr;
        best_action = {ActionType::SELL, id};
      }
      curr = eval_reinforce(id, t);
      if (curr > best) {
        best = curr;
        best_action = {ActionType::REINFORCE, id};
      }
    }
    // enhclick
    curr = eval_enhclick(t);
    if (curr > best) {
      best = curr;
      best_action = {ActionType::ENHCLICK, -1};
    }
    if (can_act(best_action)) {
      actions[t] = best_action;
    } else {
      actions[t] = {ActionType::CLICK, -1};
    }
    act(actions[t]);
    produce();
    affect(t);
  }
}

void print_data() {
  init();
  int click_cnt = 0;
  V<> buy_cnt(5), sell_cnt(5), reinforce_cnt(5);
  int enhclick_cnt = 0;
  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;
    }
    act(actions[t]);
    produce();
    affect(t);
  }
  cerr << "score: " << score << 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 {
    assert(argc == 2);
    // a = 0.07, b = 0;
    // for (b = 0; b < 100; b += 5) {
      lint total_score = 0;
      for (int _ = 0; _ < stoi(argv[1]); ++_) {
        generate_input();
        init();
        solve();
        // print_data();
        total_score += score;
      }
      cerr << "a: " << setw(5) << a << "\tb: " << b << '\t';
      cerr << "Score: " << setw(12) << total_score << endl;
      cout << b << '\t' << total_score << endl;
    // }
  }
}
0