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

提出ソース

結果

問題	No.5003 物理好きクリッカー
ユーザー	risujiroh
提出日時	2018-12-09 19:51:09
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	336 ms / 10,000 ms
コード長	12,126 bytes
コンパイル時間	2,076 ms
実行使用メモリ	21,984 KB
スコア	316,337,790,757
平均クエリ数	10000.00
最終ジャッジ日時	2021-07-19 09:16:06
合計ジャッジ時間	16,158 ms
ジャッジサーバーID （参考情報）	judge15 / judge11
	純コード判定しない問題か言語

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	332 ms 21,504 KB
testcase_01	AC	320 ms 21,360 KB
testcase_02	AC	321 ms 21,372 KB
testcase_03	AC	330 ms 21,852 KB
testcase_04	AC	336 ms 21,336 KB
testcase_05	AC	335 ms 21,492 KB
testcase_06	AC	321 ms 21,876 KB
testcase_07	AC	319 ms 21,504 KB
testcase_08	AC	320 ms 21,864 KB
testcase_09	AC	323 ms 21,912 KB
testcase_10	AC	317 ms 21,852 KB
testcase_11	AC	315 ms 21,696 KB
testcase_12	AC	319 ms 21,876 KB
testcase_13	AC	309 ms 21,360 KB
testcase_14	AC	314 ms 21,384 KB
testcase_15	AC	312 ms 21,552 KB
testcase_16	AC	325 ms 21,828 KB
testcase_17	AC	316 ms 21,372 KB
testcase_18	AC	315 ms 21,864 KB
testcase_19	AC	326 ms 21,708 KB
testcase_20	AC	327 ms 21,660 KB
testcase_21	AC	314 ms 21,372 KB
testcase_22	AC	313 ms 21,552 KB
testcase_23	AC	315 ms 21,348 KB
testcase_24	AC	319 ms 21,492 KB
testcase_25	AC	317 ms 21,504 KB
testcase_26	AC	318 ms 21,528 KB
testcase_27	AC	335 ms 21,876 KB
testcase_28	AC	333 ms 21,336 KB
testcase_29	AC	321 ms 21,888 KB
testcase_30	AC	318 ms 21,348 KB
testcase_31	AC	314 ms 21,336 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...); }


lint ceilll(lint a, lint b) {
  assert(a >= 0 and b > 0);
  return (a + b - 1) / b;
}

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

// input
constexpr int T = 10'000;
string S;
V<> rest; // fever を考慮した実質の残りターン数

// outoput
const V<string> name{"hand", "lily", "factory", "casino", "grimoire"};
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;
V<> cnt;
V<lint> power, price, cost;
bool fever, sale;

void convert_input() {
  for (int t = 0; t < T; ++t) {
    if (S[t] == 'F') {
      S[t] = 'N';
      for (int i = 1; i <= 20 and t + i < T; ++i) {
        S[t + i] = 'F';
      }
      t += 20;
    } else if (S[t] == 'S') {
      S[t] = 'N';
      if (t + 1 < T) {
        S[t + 1] = 'S';
      }
      ++t;
    }
  }
  rest.assign(T + 1, 0);
  for (int t = T - 1; t >= 0; --t) {
    rest[t] = rest[t + 1] + (S[t] == 'F' ? 7 : 1);
  }
}

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

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

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 s;
    cin >> s;
    assert(s == "ok");
  }
}

void init_status() {
  score = 0;
  click_power = 1, click_cost = 15;
  cnt.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;
}

bool can_buy(int id) {
  lint curr_price = sale ? ceilll(9 * price[id], 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 ? ceilll(9 * cost[id], 10) : cost[id];
  return score >= curr_cost;
}

bool can_enhclick() {
  lint curr_cost = sale ? ceilll(9 * click_cost, 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 ? ceilll(9 * price[id], 10) : price[id];
  score -= curr_price;
  ++cnt[id];
  price[id] = ceilll(6 * price[id], 5);
}

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

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

void enhclick() {
  lint curr_cost = sale ? ceilll(9 * click_cost, 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) {
  if (S[t] == 'B') {
    score += ceilll(score, 100);
  }
  if (t + 1 < T) {
    fever = S[t + 1] == 'F';
    sale = S[t + 1] == 'S';
  }
}

void next_turn(const Action& action, int t) {
  fever = S[t] == 'F';
  sale = S[t] == 'S';
  if (can_act(action)) {
    act(action);
  } else {
    act({ActionType::CLICK, -1});
  }
  produce();
  affect(t);
}

void print_data() {
  init_status();
  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) {
    _score = score;
    fever = S[t] == 'F';
    sale = S[t] == 'S';
    if (can_act(actions[t])) {
      act(actions[t]);
    } else {
      act(actions[t] = {ActionType::CLICK, -1});
    }
    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;
    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;
    }
  }
  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;
}

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

int eval_act(const Action& action, int t) {
  auto f = [&](lint c, lint p) -> lint {
    return t + ceilll(c, p) + ceilll(max(c - score, 0LL), calc_power());
  };
  switch (action.type) {
    case ActionType::BUY:
      return f(price[action.id], power[action.id]);
    case ActionType::REINFORCE:
      return f(cost[action.id], power[action.id] * cnt[action.id]);
    case ActionType::ENHCLICK:
      return f(click_cost, click_power);
    default:
      return rest[0];
  }
}

void first_solve() {
  // buy, reinforce, enhclick
  init_status();
  for (int t = 0; t < T; ++t) {
    lint curr = t + rest[t], best = curr;
    Action curr_action = {ActionType::CLICK, -1}, best_action = curr_action;
    auto update = [&]() -> void {
      curr = eval_act(curr_action, t);
      if (curr < best) {
        best = curr;
        best_action = curr_action;
      }
    };
    for (int id = 0; id < 5; ++id) {
      curr_action = {ActionType::BUY, id};
      update();
      if (cnt[id]) {
        curr_action = {ActionType::REINFORCE, id};
        update();
      }
    }
    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);
  }
  // sell
  struct Status {
    lint score;
    lint click_power, click_cost;
    V<> cnt;
    V<lint> power, price, cost;
    bool fever, sale;
  };
  auto copy_status = []() -> Status {
    return {score, click_power, click_cost, cnt, power, price, cost, fever, sale};
  };
  auto update_status = [](const Status& status) -> void {
    score = status.score;
    click_power = status.click_power, click_cost = status.click_cost;
    cnt = status.cnt;
    power = status.power, price = status.price, cost = status.cost;
    fever = status.fever, sale = status.sale;
  };
  int Tf = T - accumulate(begin(cnt), end(cnt), 0);
  init_status();
  for (int t = 0; t < Tf; ++t) {
    next_turn(actions[t], t);
  }
  auto status = copy_status();
  for (int t = T - 1; t >= Tf; --t) {
    lint curr = 0, best = curr;
    Action curr_action = {ActionType::NOTHING, -1}, best_action = curr_action;
    auto update = [&]() -> void {
      update_status(status);
      for (int _t = Tf; _t < T; ++_t) {
        if (_t == t) {
          next_turn(curr_action, _t);
        } else {
          next_turn(actions[_t], _t);
        }
      }
      curr = score;
      if (curr > best) {
        best = curr;
        best_action = curr_action;
      }
    };
    curr_action = {ActionType::CLICK, -1};
    update();
    for (int id = 0; id < 5; ++id) {
      curr_action = {ActionType::SELL, id};
      update();
    }
    actions[t] = best_action;
  }
}

void optimize(bool rev = false) {
  auto simulate = []() -> void {
    init_status();
    for (int t = 0; t < T; ++t) {
      if (!can_act(actions[t])) {
        score = 0;
        return;
      }
      act(actions[t]);
      produce();
      affect(t);
    }
  };
  simulate();
  int Tf = T - accumulate(begin(cnt), end(cnt), 0);
  bitset<T> chance;
  for (int t = 1; t < T; ++t) {
    auto s = S.substr(t - 1, 2);
    if (s == "BN" or s == "FN" or s == "NS") {
      chance[t] = true;
    }
  }
  lint best = score;
  for (int t = Tf - 1; t >= 0; --t) if (actions[t].type != ActionType::CLICK) {
    int tb = -1;
    for (int _t = t + 1; _t < T and actions[_t].type == ActionType::CLICK; ++_t) {
      if (!chance[_t]) continue;
      swap(actions[t], actions[_t]);
      simulate();
      if (score > best) {
        best = score;
        tb = _t;
      }
      swap(actions[t], actions[_t]);
    }
    if (tb != -1) {
      swap(actions[t], actions[tb]);
    }
  }
  simulate();
}

int main(int argc, char* argv[]) {
  if (argc == 1) {
    read_input();
    first_solve();
    optimize();
    write_output();
  } else if (string(argv[1]) == "expt") {
    auto start_t = steady_clock::now();
    lint total_score = 0, _total_score = 0;
    for (int _ = 0; _ < 32; ++_) {
      generate_input();
      first_solve();
      _total_score += score;
      optimize();
      if (_ == 31) print_data();
      total_score += score;
    }
    cerr << "Score: " << _total_score << '\n';
    cerr << "Score: " << total_score << '\n';
    cerr << "Time: " << duration_cast<milliseconds>(steady_clock::now() - start_t).count() << " ms\n";
  }
}

yukicoder

結果

テストケース

ソースコード