Submission #63939320

---

Source Code Expand

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <algorithm>
#include <cmath>
#include <iostream>
#include <random>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>

#define rep(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)((x).size())
#define fo(x) cout<<x<<endl
#define vi vector<int>
#define vvi vector<vi>
#define vp vector<P>
template <typename T> bool chmin(T &a, const T& b){if(a>b){a=b; return true;}return false;}
template <typename T> bool chmax(T &a, const T& b){if(a<b){a=b; return true;}return false;}
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
//const long long INF=1e18;
const int INF=1000000000;

const int64_t CYCLES_PER_SEC = 3000000000;
const double TIMELIMIT = 0.19;
// const double TIMELIMIT = 1.0;
constexpr int RANDOM_SEED = 42; // 乱数のシード値

// 定数==============================
const int FIRST_HALF_TURN=3; // 前半の行動をするターン数
const double K_START=5.0; // Kの初期値
const double K_END=6.0; // Kの最終値
const int ANS_BENCH1=45; // ans+ベンチの個数
const int ANS_BENCH2=60; // ans+ベンチの個数

const vi plant_order_moto={
  32, 16, 17, 18, 19, 33,
  31, 12,  4,  5, 13, 20,
  30, 11,  0,  1,  6, 21,
  29, 10,  3,  2,  7, 22,
  28, 15,  9,  8, 14, 23,
  35, 27, 26, 25, 24, 34
};
vi plant_order;

struct Timer {
  int64_t start;
  Timer() { reset(); }
  void reset() { start = getCycle(); }
  void plus(double a) { start -= (a * CYCLES_PER_SEC); }
  inline double get() { return (double)(getCycle() - start) / CYCLES_PER_SEC; }
  inline int64_t getCycle() {
    uint32_t low, high;
    __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
    return ((int64_t)low) | ((int64_t)high << 32);
  }
};

mt19937 mt(RANDOM_SEED);
uniform_int_distribution<> rand36(0,35);
uniform_int_distribution<> rand36_BENCH1(0,ANS_BENCH1-1);
uniform_int_distribution<> rand36_BENCH2(0,ANS_BENCH2-1);

void out_vec2_with_space(vector<vector<auto>> &v){
  for(int i = 0; i < v.size(); i++){
    for(int j = 0; j < v[0].size(); j++){
      cout << ( j ? " " : "" ) << v[i][j];
    }
    cout << endl;    
  }
}

struct Solver {
  Timer timer;
  
  // グローバル変数==============================
  const int N=6,M=15,T=10;
  const int N2=60;
  int turn;
  vvi x;
  vi best_ans;
  double best_score;
  vector<double> tar_vec;
  const double beta=0.9;
  const double delta=0.1;
  vector<double> gs;
  double K; // logsumexpで使用する定数
  vector<vector<double>> g_all_pair; // すべての種のペアについて前計算したg

  // 便利関数==============================
  // logsumexp
  double logsumexp(vector<double> A){
    double ret = 0;//,K = 1;
    fore(a,A) ret += exp(a/K);
    ret = log(ret)*K;
    return ret;
  }
  // スコア計算補助2
  double h(int val0, int val1, int tar){
    int a=min(tar-val0,tar-val1);
    int b=max(tar-val0,tar-val1);
    vector<double> A={1.0/(delta+a),1.0/(delta+b)};
    return logsumexp(A);
  }
  // スコア計算補助1
  double g(int u, int v){
    double res=0;
    rep(i,0,M) res+=h(x[u][i],x[v][i],tar_vec[i]);
    return res;
  }
  // スコア差分計算==============================
  // logsumexp(初回)
  double logsumexp_first(vector<double> A, double &sumexp){
    double ret = 0;//,K = 1;
    fore(a,A) ret += exp(a/K);
    sumexp=ret; // 参照渡しで戻す
    ret = log(ret)*K;
    return ret;
  }
  // 差分スコア計算(初回)
  double calc_score_first(vi &ans, vector<double> &gs, double &sumexp){
    int id=0;
    // 右30個
    rep(i,0,35){
      if(i%N==5) continue;
      // gs[id]=g(ans[i],ans[i+1]); // 右との比較
      gs[id]=g_all_pair[ans[i]][ans[i+1]]; // 右との比較
      id++;
    }
    // 下30個
    rep(i,0,30){
      // gs[id]=g(ans[i],ans[i+N]); // 下との比較
      gs[id]=g_all_pair[ans[i]][ans[i+N]]; // 下との比較
      id++;
    }
    return logsumexp_first(gs,sumexp);
  }
  // logsumexp
  double logsumexp_dif(vector<double> &pre_gs, vector<double> &new_gs, double &pre_sumexp, double &new_sumexp){
    new_sumexp=pre_sumexp;
    //double K = 1;
    rep(i,0,sz(pre_gs)){
      if(new_gs[i]==pre_gs[i]) continue; // 同一スキップ
      new_sumexp -= exp(pre_gs[i]/K);
      new_sumexp += exp(new_gs[i]/K);
    }

    return log(new_sumexp)*K;
  }
  // 差分スコア計算
  double calc_score_dif(vi &pre_ans, vi &new_ans, vector<double> &pre_gs, vector<double> &new_gs, double &pre_sumexp, double &new_sumexp){
    new_gs=pre_gs;
    int id=0;
    // 右30個
    rep(i,0,35){
      if(i%N==5) continue;
      if(!(pre_ans[i]==new_ans[i] and pre_ans[i+1]==new_ans[i+1])){
        // new_gs[id]=g(new_ans[i],new_ans[i+1]); // 右との比較
        new_gs[id]=g_all_pair[new_ans[i]][new_ans[i+1]]; // 右との比較
      }
      id++;
    }
    // 下30個
    rep(i,0,30){
      if(!(pre_ans[i]==new_ans[i] and pre_ans[i+N]==new_ans[i+N])){
        // new_gs[id]=g(new_ans[i],new_ans[i+N]); // 下との比較
        new_gs[id]=g_all_pair[new_ans[i]][new_ans[i+N]]; // 下との比較
      }
      id++;
    }
    return logsumexp_dif(pre_gs,new_gs,pre_sumexp,new_sumexp);
  }
  vector<vector<double>> pre_calc_gs(vi &ans){
    vector<vector<double>> res(60,vector<double>(60));
    rep(i,0,sz(ans)-1){
      rep(j,i+1,sz(ans)){
        double _g=g(ans[i],ans[j]);
        res[ans[i]][ans[j]]=_g;
        res[ans[j]][ans[i]]=_g;
      }
    }
    return res;
  }
  /*
  // スコア計算最終ターン(log0の扱い方が分からず保留)
  double calc_last_turn_prob(vi &ans){
    double res;
    
    vi dp(101); // 場合の数
    dp[0]=1;
    rep(j,0,M){
      rep(d,)
    }

    log(pe,v)

    // 未満が生まれる場合の数
    dp[0]=0;
    dp[1]=1;

    // 最大の価値がv以上となる確率は
    qv=1-dp[v]*dp[v]*dp[v]*..;

    // あるペアが決まったと考える
    // ここから生まれる種の価値vの期待値を求める
    rep(j,0,M){
      x[ans[0]][j]
      x[ans[1]][j]
    }
    
    vvi dp(M,vi(101)); // dp[j][v]:次元jまで見て、価値がvとなる場合の数

    return res;
  }
  */
  // スコア計算以外==============================
  // 植える種を求める
  vi get_cand(){
    vi res;
    
    if(turn<FIRST_HALF_TURN){
      res.resize(ANS_BENCH1);
      vector<bool> used(N2);
      rep(i,0,ANS_BENCH1){
        int tar_id=-1;
        int mx=0;
        int type=i%M;
        rep(j,0,N2){
          if(used[j]) continue;
          if(chmax(mx,x[j][type])) tar_id=j;
        }
        res[i]=tar_id;
        used[tar_id]=true;
      }

    }else{
      res.resize(ANS_BENCH2);
      vp sum_id(N2);
      rep(i,0,N2){
        int sum=0;
        rep(j,0,M) sum+=x[i][j];
        sum_id[i]=P(sum,i);
      }
      sort(rall(sum_id));
      rep(i,0,ANS_BENCH2) res[i]=sum_id[i].second;
    }

    return res;
  }
  // 初期解を生成する
  vi get_initial_solution(){
    int ans_bench=ANS_BENCH1;
    if(turn>=FIRST_HALF_TURN) ans_bench=ANS_BENCH2;
    vi res(ans_bench);
    vi cand=get_cand();
    rep(i,0,36) res[plant_order[i]]=cand[i];
    rep(i,36,ans_bench) res[i]=cand[i];
    return res;
  }
  // pre_ansからnew_ansを作る
  vi make_new_ans(vi &pre_ans){
    // コピー
    vi new_ans=pre_ans;

    // 隣接を求める
    int u=rand36(mt);
    int v;
    if(turn<FIRST_HALF_TURN) v=rand36_BENCH1(mt);
    else v=rand36_BENCH2(mt);
    while(v==u){
      if(turn<FIRST_HALF_TURN) v=rand36_BENCH1(mt);
      else v=rand36_BENCH2(mt);
    }
    swap(new_ans[u],new_ans[v]);

    return new_ans;
  }
  // 目標ベクトルを計算
  void calc_tar_vec(){
    rep(j,0,M){
      vector<double> A;
      rep(i,0,N2) A.emplace_back(x[i][j]);
      tar_vec[j]=logsumexp(A);
    }
  }

  // 初期解生成
  void init(){
    turn=0;
    // サイズ変更
    x.resize(N2,vi(M));
    tar_vec.resize(M);
    // 植える場所のマップを作成
    plant_order.resize(36);
    rep(i,0,36) plant_order[plant_order_moto[i]]=i;
  }

  void SA(){
    double ti = timer.get();
    double start_time=ti;

    vector<double> pre_gs(60); // 追加
    double pre_sumexp; // 追加

    vi pre_ans=best_ans;
    best_score = calc_score_first(pre_ans,pre_gs,pre_sumexp); // ここではpreに更新後の値を入れたいので順番が以降のものとは逆になっている
    double pre_score = best_score;
    //cerr << best_score << endl;
    //double kankaku = (TIMELIMIT - ti) / 10;
    double kankaku = TIMELIMIT / 10;
    double ne = ti;
    int cnt = 0;
    int cnt2 = 0;

    double start_temp = 10;
    double end_temp = 1;
    
    while(1){
      ti = timer.get();
      if(TIMELIMIT < ti-start_time) break;
      
      double temp = start_temp + (end_temp - start_temp) * (ti-start_time) / TIMELIMIT;

      if (ti > ne) {
        ne += kankaku;
        //cerr << temp << " " << pre_score << " " << best_score << endl;
      }

      // 新たな解の生成==============================
      vi new_ans=make_new_ans(pre_ans);

      // new_scoreを計算
      // double new_score=calc_score(new_ans); // スコア計算
      vector<double> new_gs;
      double new_sumexp;
      double new_score=calc_score_dif(pre_ans,new_ans,pre_gs,new_gs,pre_sumexp,new_sumexp); // スコア計算
      
      // 採用するか否かを決定
      double prob = exp((new_score-pre_score)*10000000/temp);
      // if(cnt<5) printf("%lf %lf %lf\n",pre_score,new_score,prob);
      if (prob*10000 > (rand() % 10000)) {
        pre_score=new_score;
        pre_ans=new_ans;
        pre_gs=new_gs;
        pre_sumexp=new_sumexp;

        if(chmax(best_score,new_score)){
          best_score=new_score;
          best_ans=new_ans;
        }
        cnt2++;
      }
      cnt++;
    }
    
    // dump(cnt);
    // dump(cnt2);
    //ti = timer.get();
    //cerr << ti << endl;
  }
  
  void input_func() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    rep(i,0,N2) rep(j,0,M) cin >> x[i][j];
  }

  int solve() {
    best_ans=get_initial_solution();
    calc_tar_vec(); // 目標ベクトルの計算
    g_all_pair=pre_calc_gs(best_ans);
    SA();
    return 0;
  }
  
  void output(){
    // cerr << best_score << endl;
    vvi res(N,vi(N));
    rep(i,0,36) res[i/N][i%N]=best_ans[i];
    out_vec2_with_space(res);
  }
};

Solver solver;
int main(int argc, char *argv[]) {
  int N,M,T;
  cin >> N >> M >> T;
  
  solver.init();
  solver.input_func();

  rep(t,0,T){
    solver.K=(K_START*(9-t)+K_END*t)/9;
    solver.solve();
    solver.output();
    solver.input_func();
    solver.turn++;
  }
  return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main(int, char**)’:
Main.cpp:396:14: warning: unused parameter ‘argc’ [-Wunused-parameter]
  396 | int main(int argc, char *argv[]) {
      |          ~~~~^~~~
Main.cpp:396:26: warning: unused parameter ‘argv’ [-Wunused-parameter]
  396 | int main(int argc, char *argv[]) {
      |                    ~~~~~~^~~~~~
Main.cpp: In instantiation of ‘void out_vec2_with_space(std::vector<std::vector<_RealType> >&) [with auto:16 = int]’:
Main.cpp:391:24:   required from here
Main.cpp:76:20: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   76 |   for(int i = 0; i < v.size(); i++){
      |                  ~~^~~~~~~~~~
Main.cpp:77:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   77 |     for(int j = 0; j < v[0].size(); j++){
      |                    ~~^~~~~~~~~~~~~

Judge Result