結果

問題 No.3306 Life is Easy?
ユーザー takumi152
提出日時 2025-10-05 15:55:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 11,651 bytes
コンパイル時間 3,230 ms
コンパイル使用メモリ 366,948 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-10-05 15:56:05
合計ジャッジ時間 55,186 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other WA * 25 RE * 10
権限があれば一括ダウンロードができます

ソースコード

diff #

#ifdef __GNUC__
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
// #pragma GCC target ("avx2")
#endif

#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <random>
#include <functional>
#include <cmath>
#include <cassert>

#ifdef _MSC_VER
#include <intrin.h>
#else
#include <x86intrin.h>
#endif

struct xorshift64 {
  unsigned long long int x = 88172645463325252ULL;
  inline unsigned short nextUShort() {
    x = x ^ (x << 7);
    return x = x ^ (x >> 9);
  }
  inline unsigned int nextUShortMod(unsigned long long int mod) {
    x = x ^ (x << 7);
    x = x ^ (x >> 9);
    return ((x & 0x0000ffffffffffff) * mod) >> 48;
  }
  inline unsigned int nextUInt() {
    x = x ^ (x << 7);
    return x = x ^ (x >> 9);
  }
  inline unsigned int nextUIntMod(unsigned long long int mod) {
    x = x ^ (x << 7);
    x = x ^ (x >> 9);
    return ((x & 0x00000000ffffffff) * mod) >> 32;
  }
  inline unsigned long long int nextULL() {
    x = x ^ (x << 7);
    return x = x ^ (x >> 9);
  }
  inline double nextDouble() {
    x = x ^ (x << 7);
    x = x ^ (x >> 9);
    return (double)x * 5.42101086242752217e-20;
  }
};

struct timer {
  double t = 0.0;
  double lastStop = 0.0;
  bool stopped = false;
  timer() {
    restart();
  }
  inline void restart() {
    t = now();
    stopped = false;
  }
  inline void start() {
    if (stopped) {
      t += now() - lastStop;
      stopped = false;
    }
  }
  inline void stop() {
    if (!stopped) {
      lastStop = now();
      stopped = true;
    }
  }
  inline double time() {
    if (stopped) return lastStop - t;
    else return now() - t;
  }
  inline double now() {
    #ifdef _MSC_VER
      #ifdef LOCAL
        return __rdtsc() * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X)
      #else
        //return __rdtsc() * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2)
        //return __rdtsc() * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3)
        //return __rdtsc() * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL)
        return __rdtsc() * 4.3478260869565215e-10; // 1 / 2.3e9, for yukicoder judge
      #endif
    #else
      unsigned long long l, h;
        __asm__ ("rdtsc" : "=a"(l), "=d"(h));
      #ifdef LOCAL
        return (double)(l | h << 32) * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X)
      #else
        //return (double)(l | h << 32) * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2)
        //return (double)(l | h << 32) * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3)
        //return (double)(l | h << 32) * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL)
        return (double)(l | h << 32) * 4.3478260869565215e-10; // 1 / 2.3e9, for yukicoder judge
      #endif
    #endif
  }
};

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int, int> Pii;
typedef unsigned char uchar;

const ll mod = 1000000007;

timer theTimer;
xorshift64 theRandom;
mt19937 theMersenne(1);

// hyper parameters

// structs

// enums

// constants

// inputs
int day_num, stone_num;
vector<vector<ll>> stone_day_price;

// outputs
ll ans;

// environment

// state
vector<pair<int, bool>> action_of_day; // stone_id, is_buy
vector<vector<pair<int, bool>>> actions_for_stone; // day_idx, is_buy

// score
vector<ll> stone_score;
ll total_score;

void get_first_input() {
  cin >> day_num >> stone_num;
  stone_day_price = vector<vector<ll>>(day_num, vector<ll>(stone_num));
  for (int i = 0; i < day_num; i++) {
    for (int j = 0; j < stone_num; j++) {
      cin >> stone_day_price[i][j];
    }
  }
}

void init() {
  action_of_day = vector<pair<int, bool>>(day_num, make_pair(0, false));
  actions_for_stone = vector<vector<pair<int, bool>>>(day_num, vector<pair<int, bool>>());
  for (int i = 0; i < day_num; i++) {
    actions_for_stone[0].emplace_back(i, false);
  }

  stone_score = vector<ll>(stone_num);
  total_score = 0;
}

void update_score_partial(int stone_idx) {
  total_score -= stone_score[stone_idx];

  stone_score[stone_idx] = 0;
  priority_queue<int, vector<int>, greater<int>> que;
  for (auto &[day, is_buy]: actions_for_stone[stone_idx]) {
    if (is_buy) {
      que.emplace(stone_day_price[day][stone_idx]);
    }
    else if (!que.empty()) {
      auto buy_price = que.top();
      que.pop();
      stone_score[stone_idx] += stone_day_price[day][stone_idx] - buy_price;
    }
  }
  total_score += stone_score[stone_idx];
}

void update_score_full() {
  stone_score.assign(stone_num, 0);
  total_score = 0;
  for (int i = 0; i < stone_num; i++) {
    update_score_partial(i);
  }
}

ll get_score() {
  return total_score;
}

void solve() {
  update_score_full();

  ll score = get_score();
  ll last_score = score;
  ll best_score = score;

  const double base_temperature = 1e9;
  const double target_temperature = 1e-2;
  // const double decay_rate = 4e-5;
  double temperature = base_temperature;

  int iter_count = 0;
  double time_start = theTimer.time();
  const double time_limit = 1.900;

  while (theTimer.time() < time_limit) {
    double roll = theRandom.nextDouble();
    if (roll < 0.50) {
      int d = theRandom.nextUIntMod(day_num);
      bool b = theRandom.nextUIntMod(2) == 0;
      int s = theRandom.nextUIntMod(stone_num);
    
      auto act = action_of_day[d];
      action_of_day[d] = make_pair(s, b);
      actions_for_stone[act.first].erase(find(actions_for_stone[act.first].begin(), actions_for_stone[act.first].end(), make_pair(d, act.second)));
      actions_for_stone[s].insert(lower_bound(actions_for_stone[s].begin(), actions_for_stone[s].end(), make_pair(d, b)), make_pair(d, b));

      update_score_partial(act.first);
      update_score_partial(s);
      
      score = get_score();

      #ifdef DEBUG
      if (iter_count % 100000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " << theTimer.time() << endl;
      #endif

      if (score >= last_score) {
        // cerr << "Y " << iter_count << " " << d << " " << (int) b << " " << s << endl;
        last_score = score;
        if (score > best_score) {
          best_score = score;
        }
      }
      else if (theRandom.nextDouble() < exp(double(score - last_score) / temperature)) { // accept
        // cerr << "Y " << iter_count << " " << d << " " << (int) b << " " << s << endl;
        last_score = score;
      }
      else { // rollback
        // cerr << "N " << iter_count << " " << d << " " << (int) b << " " << s << endl;
        // for (int i = 0; i < day_num; i++) {
        //   cerr << "A " << i << " " << action_of_day[i].first << " " << (int) action_of_day[i].second << endl;
        // }
        // for (int i = 0; i < stone_num; i++) {
        //   cerr << "S " << i << " " << stone_score[i] << " ";
        //   for (auto &x: actions_for_stone[i]) {
        //     cerr << "(" << x.first << ", " << (int) x.second << ") ";
        //   }
        //   cerr << endl;
        // }
        action_of_day[d] = act;
        actions_for_stone[s].erase(find(actions_for_stone[s].begin(), actions_for_stone[s].end(), make_pair(d, b)));
        actions_for_stone[act.first].insert(lower_bound(actions_for_stone[act.first].begin(), actions_for_stone[act.first].end(), make_pair(d, act.second)), make_pair(d, act.second));

        update_score_partial(act.first);
        update_score_partial(s);

        // cerr << score << " " << last_score << " " << get_score() << endl;
      }
    }
    else if (roll < 1.00) {
      int d1 = theRandom.nextUIntMod(day_num);
      int d2 = theRandom.nextUIntMod(day_num);
      int s = theRandom.nextUIntMod(stone_num);
      if (d1 == d2) continue;
      if (d1 > d2) swap(d1, d2);

      auto act1 = action_of_day[d1];
      action_of_day[d1] = make_pair(s, true);
      actions_for_stone[act1.first].erase(find(actions_for_stone[act1.first].begin(), actions_for_stone[act1.first].end(), make_pair(d1, act1.second)));
      actions_for_stone[s].insert(lower_bound(actions_for_stone[s].begin(), actions_for_stone[s].end(), make_pair(d1, true)), make_pair(d1, true));

      auto act2 = action_of_day[d2];
      action_of_day[d2] = make_pair(s, false);
      actions_for_stone[act2.first].erase(find(actions_for_stone[act2.first].begin(), actions_for_stone[act2.first].end(), make_pair(d2, act2.second)));
      actions_for_stone[s].insert(lower_bound(actions_for_stone[s].begin(), actions_for_stone[s].end(), make_pair(d2, false)), make_pair(d2, false));

      update_score_partial(act1.first);
      update_score_partial(act2.first);
      update_score_partial(s);

      score = get_score();

      #ifdef DEBUG
      if (iter_count % 100000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " << theTimer.time() << endl;
      #endif

      if (score >= last_score) {
        last_score = score;
        if (score > best_score) {
          best_score = score;
        }
      }
      else if (theRandom.nextDouble() < exp(double(score - last_score) / temperature)) { // accept
        last_score = score;
      }
      else { // rollback
        action_of_day[d1] = act1;
        actions_for_stone[s].erase(find(actions_for_stone[s].begin(), actions_for_stone[s].end(), make_pair(d1, true)));
        actions_for_stone[act1.first].insert(lower_bound(actions_for_stone[act1.first].begin(), actions_for_stone[act1.first].end(), make_pair(d1, act1.second)), make_pair(d1, act1.second));

        action_of_day[d2] = act2;
        actions_for_stone[s].erase(find(actions_for_stone[s].begin(), actions_for_stone[s].end(), make_pair(d2, false)));
        actions_for_stone[act2.first].insert(lower_bound(actions_for_stone[act2.first].begin(), actions_for_stone[act2.first].end(), make_pair(d2, act2.second)), make_pair(d2, act2.second));

        update_score_partial(act1.first);
        update_score_partial(act2.first);
        update_score_partial(s);
      }
    }
    // auto ss = stone_score;
    // update_score_full();
    // if (last_score != get_score()) {
    //   cerr << "X " << last_score << " " << get_score() << endl;
    //   for (int i = 0; i < day_num; i++) {
    //     cerr << "A " << i << " " << action_of_day[i].first << " " << (int) action_of_day[i].second << endl;
    //   }
    //   for (int i = 0; i < stone_num; i++) {
    //     cerr << "S " << i << " " << ss[i] << " " << stone_score[i] << " ";
    //     for (auto &x: actions_for_stone[i]) {
    //       cerr << "(" << x.first << ", " << (int) x.second << ") ";
    //     }
    //     cerr << endl;
    //   }
    //   assert(false);
    // }

    // temperature *= 1.0 - decay_rate;
    temperature = exp(log(base_temperature) - ((log(base_temperature) - log(target_temperature)) * ((theTimer.time() - time_start) * (1.0 / (time_limit - time_start)))));
    iter_count++;
  }

  cerr << "iter_count   = " << iter_count << endl;
  cerr << "score        = " << score << endl;
  cerr << "best_score   = " << best_score << endl;
  cerr << "temperature  = " << temperature << endl;

  ans = best_score;
}

void output_ans() {
  cout << ans << endl;
}

int main(int argc, char *argv[]) {
  cin.tie(0);
  ios::sync_with_stdio(false);

  get_first_input();

  init();
  solve();

  output_ans();

  return 0;
}
0