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

提出ソース

結果

問題	No.5003 物理好きクリッカー
ユーザー	risujiroh
提出日時	2018-12-06 19:07:16
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	319 ms / 10,000 ms
コード長	7,817 bytes
コンパイル時間	1,767 ms
実行使用メモリ	21,948 KB
スコア	52,822,871,228
平均クエリ数	10000.00
最終ジャッジ日時	2021-07-19 08:57:19
合計ジャッジ時間	14,767 ms
ジャッジサーバーID （参考情報）	judge15 / judge14
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	293 ms 21,888 KB
testcase_01	AC	298 ms 21,528 KB
testcase_02	AC	292 ms 21,924 KB
testcase_03	AC	286 ms 21,684 KB
testcase_04	AC	286 ms 21,888 KB
testcase_05	AC	300 ms 21,876 KB
testcase_06	AC	304 ms 21,372 KB
testcase_07	AC	297 ms 21,360 KB
testcase_08	AC	293 ms 21,384 KB
testcase_09	AC	297 ms 21,672 KB
testcase_10	AC	315 ms 21,516 KB
testcase_11	AC	318 ms 21,888 KB
testcase_12	AC	300 ms 21,528 KB
testcase_13	AC	299 ms 21,540 KB
testcase_14	AC	298 ms 21,876 KB
testcase_15	AC	295 ms 21,936 KB
testcase_16	AC	296 ms 21,360 KB
testcase_17	AC	293 ms 21,360 KB
testcase_18	AC	290 ms 21,384 KB
testcase_19	AC	291 ms 21,696 KB
testcase_20	AC	316 ms 21,516 KB
testcase_21	AC	316 ms 21,408 KB
testcase_22	AC	318 ms 21,552 KB
testcase_23	AC	293 ms 21,528 KB
testcase_24	AC	295 ms 21,516 KB
testcase_25	AC	317 ms 21,696 KB
testcase_26	AC	317 ms 21,516 KB
testcase_27	AC	314 ms 21,384 KB
testcase_28	AC	314 ms 21,876 KB
testcase_29	AC	292 ms 21,840 KB
testcase_30	AC	319 ms 21,360 KB
testcase_31	AC	315 ms 21,516 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...); }


// 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) {
  if (sale) {
    return score >= (9 * price[id] + 9) / 10;
  } else {
    return score >= price[id];
  }
}

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

bool can_reinforce(int id) {
  if (sale) {
    return score >= (9 * cost[id] + 9) / 10;
  } else {
    return score >= cost[id];
  }
}

bool can_enhclick() {
  if (sale) {
    return score >= (9 * click_cost + 9) / 10;
  } else {
    return score >= click_cost;
  }
}

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

void buy(int id) {
  if (sale) {
    score -= (9 * price[id] + 9) / 10;
  } else {
    score -= price[id];
  }
  ++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) {
  if (sale) {
    score -= (9 * cost[id] + 9) / 10;
  } else {
    score -= cost[id];
  }
  power[id] <<= 1;
  cost[id] *= 10;
}

void enhclick() {
  if (sale) {
    score -= (9 * click_cost + 9) / 10;
  } else {
    score -= click_cost;
  }
  click_power <<= 1;
  click_cost *= 10;
}

void act(const Action& action) {
  switch(action.type) {
    case ActionType::CLICK:
      click();
      break;
    case ActionType::BUY:
      assert(can_buy(action.id));
      buy(action.id);
      break;
    case ActionType::SELL:
      assert(can_sell(action.id));
      sell(action.id);
      break;
    case ActionType::REINFORCE:
      assert(can_reinforce(action.id));
      reinforce(action.id);
      break;
    case ActionType::ENHCLICK:
      assert(can_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 eval_click() {
  return click_power;
}

lint eval_buy(int id, int t) {
  // return 0;
  return power[id] * rest[t] - (sale ? (9 * price[id] + 9) / 10 : price[id]);
}

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

lint eval_reinforce(int id, int t) {
  // return 0;
  return power[id] * cnt[id] * rest[t] - (sale ? (9 * cost[id] + 9) / 10 : cost[id]);
}

lint eval_enhclick(int t) {
  // return 0;
  return click_power * (T - t) - (sale ? (9 * click_cost + 9) / 10 : click_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) {
      if (can_buy(id)) {
        curr = eval_buy(id, t);
        if (curr > best) {
          best = curr;
          best_action = {ActionType::BUY, id};
        }
      }
      if (can_sell(id)) {
        curr = eval_sell(id, t);
        if (curr > best) {
          best = curr;
          best_action = {ActionType::SELL, id};
        }
      }
      if (can_reinforce(id)) {
        curr = eval_reinforce(id, t);
        if (curr > best) {
          best = curr;
          best_action = {ActionType::REINFORCE, id};
        }
      }
    }
    // enhclick
    if (can_enhclick()) {
      curr = eval_enhclick(t);
      if (curr > best) {
        best = curr;
        best_action = {ActionType::ENHCLICK, -1};
      }
    }
    act(actions[t] = best_action);
    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];
        break;
      case ActionType::SELL:
        ++sell_cnt[actions[t].id];
        break;
      case ActionType::REINFORCE:
        ++reinforce_cnt[actions[t].id];
        break;
      case ActionType::ENHCLICK:
        ++enhclick_cnt;
        break;
    }
    act(actions[t]);
    produce();
    affect(t);
  }
  cerr << "score: " << (double) 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] << '\n';
  }
  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);
    lint total_score = 0;
    for (int _ = 0; _ < stoi(argv[1]); ++_) {
      generate_input();
      init();
      solve();
      print_data();
      total_score += score;
    }
    cerr << "Score: " << total_score << endl;
  }
}

yukicoder

結果

テストケース

ソースコード