結果

問題 No.5007 Steiner Space Travel
ユーザー hangryhangry
提出日時 2022-07-30 17:50:20
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 978 ms / 1,000 ms
コード長 8,628 bytes
コンパイル時間 2,084 ms
実行使用メモリ 6,952 KB
スコア 7,610,351
最終ジャッジ日時 2022-07-30 17:50:55
合計ジャッジ時間 33,952 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge16
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 974 ms
6,952 KB
testcase_01 AC 975 ms
6,952 KB
testcase_02 AC 974 ms
4,904 KB
testcase_03 AC 974 ms
4,900 KB
testcase_04 AC 975 ms
4,904 KB
testcase_05 AC 974 ms
4,904 KB
testcase_06 AC 973 ms
4,904 KB
testcase_07 AC 975 ms
4,900 KB
testcase_08 AC 975 ms
4,904 KB
testcase_09 AC 977 ms
4,904 KB
testcase_10 AC 975 ms
4,904 KB
testcase_11 AC 977 ms
6,948 KB
testcase_12 AC 977 ms
4,904 KB
testcase_13 AC 974 ms
4,904 KB
testcase_14 AC 973 ms
4,904 KB
testcase_15 AC 973 ms
6,948 KB
testcase_16 AC 978 ms
4,900 KB
testcase_17 AC 973 ms
4,900 KB
testcase_18 AC 974 ms
4,900 KB
testcase_19 AC 977 ms
6,948 KB
testcase_20 AC 977 ms
6,952 KB
testcase_21 AC 976 ms
4,904 KB
testcase_22 AC 974 ms
6,952 KB
testcase_23 AC 976 ms
4,904 KB
testcase_24 AC 975 ms
6,948 KB
testcase_25 AC 973 ms
4,900 KB
testcase_26 AC 976 ms
4,904 KB
testcase_27 AC 976 ms
4,904 KB
testcase_28 AC 975 ms
4,900 KB
testcase_29 AC 974 ms
6,952 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder>
using namespace std;
//using namespace atcoder;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repab(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)
#define repabc(i, a, b, c) for (int i = (int)(a); i <= (int)(b); i += c)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define rrepab(i, a, b) for (int i = (int)(b); i >= (int)(a); i--)
#define rrepabc(i, a, b, c) for (int i = (int)(b); i >= (int)(a); i-=c)
#define printl(...) cerr << "LINE=" << __LINE__ << " "; print(__VA_ARGS__)

void in_print() {}
template <class Head, class... Tail>
void in_print(Head&& head, Tail&&... tail)
{
  cerr << "," << head;
  in_print(forward<Tail>(tail)...);
}
void print() {}
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail)
{
  cerr << head;
  in_print(forward<Tail>(tail)...);
  cerr << endl;
}

unsigned int randxor()
{
    static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
    unsigned int t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}



//char grid[8][8];
//static const int dx[] = {0,-1,0,1,1,-1,-1,1};
//static const int dy[] = {-1,0,1,0,1,1,-1,-1};
//static const char dir[] = {'L','U','R','D'};
auto start_time = chrono::system_clock::now();
auto end_time = chrono::system_clock::now();
//if (chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count() > 500)
int N = 100;
int M = 8;
int planet[100][2];
int station[8][2];
int alpha = 5;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;

void load_data()
{
  cin >> N >> M;
  rep(i, N) rep(j, 2) cin >> planet[i][j];
  rep(i, 8) rep(j, 2) station[i][j] = i*100;
}

double calc_score(vvi &st, vvi &ans)
{
  long long energy = 0;
  int x = planet[0][0];
  int y = planet[0][1];
  int nowt = 1;
  rep(i, (int)ans.size()) {
    if (ans[i][0] == 1) {
      if (nowt == 1) energy += 25 * ((x-planet[ans[i][1]][0])*(x-planet[ans[i][1]][0]) + (y-planet[ans[i][1]][1])*(y-planet[ans[i][1]][1]));
      else energy += 5 * ((x-planet[ans[i][1]][0])*(x-planet[ans[i][1]][0]) + (y-planet[ans[i][1]][1])*(y-planet[ans[i][1]][1]));
      x = planet[ans[i][1]][0];
      y = planet[ans[i][1]][1];
    }
    else {
      if (nowt == 2) energy += ((x-st[ans[i][1]][0])*(x-st[ans[i][1]][0]) + (y-st[ans[i][1]][1])*(y-st[ans[i][1]][1]));
      else energy += 5 * ((x-st[ans[i][1]][0])*(x-st[ans[i][1]][0]) + (y-st[ans[i][1]][1])*(y-st[ans[i][1]][1]));
      x = st[ans[i][1]][0];
      y = st[ans[i][1]][1];
    }
    nowt = ans[i][0];
  }
  return round(1000000000.0/(1000.0 + sqrt(energy)));
}


void make_first_ans(vvi &fans)
{
  vi dd = {1, 0};
  fans.push_back(dd);
  repab(i, 1, N-1) {
    vi dd = {1, i};
    fans.push_back(dd);
  }
  vi dc = {1, 0};
  fans.push_back(dc);
}

void print_ans(vvi &st, vvi &ans)
{
  rep(i, 8) cout << st[i][0] << " " << st[i][1] << endl;
  cout << ans.size() << endl;
  rep(i, (int)ans.size()) cout << ans[i][0] << " " << ans[i][1]+1 << endl;
}

struct STATE {
  double score;
  vvi robo;
  vvi move;
  vi cnt;

};



void simulated_annealing()
{
  double start_tmp = 205;
  double end_tmp = 1;
  int sa_end_time = 970;
  double fsc = 0.0;
  vvi frobo;
  rep(i, 8) frobo.push_back({station[i][0], station[i][1]});
  vvi fmove;
  make_first_ans(fmove);
  vi fcnt;
  rep(i, N) {
    if (i == 0) fcnt.push_back(2);
    else fcnt.push_back(1);
  }
  STATE state = {fsc, frobo, fmove, fcnt};

  int cnt = 0;


  while (true) {
    if (cnt % 1000 == 0) {
      end_time = chrono::system_clock::now();
      if (chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count() > sa_end_time) break;
    }
    cnt += 1;

    //STATE nxt = state;

    int opt = randxor() % 6;
    //int opt = 3;
    if (opt == 0) {
      int posi = randxor() % 8;
      vvi robo = state.robo;
      robo[posi][0] += -min(50, robo[posi][0]) + (randxor() % max(1, min(50, robo[posi][0])+min(50, 1000-robo[posi][0])));
      robo[posi][1] += -min(50, robo[posi][1]) + (randxor() % max(1, min(50, robo[posi][1])+min(50, 1000-robo[posi][1])));
      double nextscore = calc_score(robo, state.move);
      //nxt.score = nextscore;
      double nowscore = state.score;
    
      double temp = start_tmp + (end_tmp - start_tmp) * (chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count()) / sa_end_time;

      double prob = exp((nextscore - nowscore)/temp);
      if (prob > (randxor() % 10000)/10000.0) {
        state.robo = robo;
        state.score = nextscore;
      }
    }
    else if (opt == 1) {
      vvi nxt = state.move;
      int posi = 1 + randxor() % (max(1, (int)state.move.size()-2));
      int tp = randxor() % 10;
      int ad;
      if (tp < 3) {
        ad = randxor() % 8;
        nxt.insert(nxt.begin() + posi, {2, ad});
      }
      else {
        ad = randxor() % 100;
        nxt.insert(nxt.begin() + posi, {1, ad});
        //kkkkkkkkkkkkkkkkkkkknxt.cnt[ad] += 1;
      }
      double nextscore = calc_score(state.robo, nxt);
      //nxt.score = nextscore;
      double nowscore = state.score;
    
      double temp = start_tmp + (end_tmp - start_tmp) * (chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count()) / sa_end_time;

      double prob = exp((nextscore - nowscore)/temp);
      if (prob > (randxor() % 10000)/10000.0) {
        state.move = nxt;
        if (tp >= 3) state.cnt[ad] += 1;
        state.score = nextscore;
      }
    }
    else if ( opt == 2) {
      vvi nxt = state.move;
      int posi = 1 + (randxor() % (max(1, (int)state.move.size() - 2)));
      
      if (state.move[posi][0] == 1) {
        if (state.cnt[state.move[posi][1]] > 1) {
          //kkkkkkkkkkkkkkkkkkkkkkkkkknxt.cnt[nxt.move[posi][1]] -= 1;
          nxt.erase(nxt.begin() + posi);
        }
        else continue;
      } 
      else nxt.erase(nxt.begin() + posi);
      double nextscore = calc_score(state.robo, nxt);
      //nxt.score = nextscore;
      double nowscore = state.score;
    
      double temp = start_tmp + (end_tmp - start_tmp) * (chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count()) / sa_end_time;

      double prob = exp((nextscore - nowscore)/temp);
      if (prob > (randxor() % 10000)/10000.0) {
        if (state.move[posi][0] == 1) state.cnt[state.move[posi][1]] -= 1;
        state.move = nxt;
        state.score = nextscore;

      }
    }
    else if (opt == 3) {
      int posi = 1 + (randxor() % max(1, (int)state.move.size() - 3));
      swap(state.move[posi], state.move[posi+1]);
      double nextscore = calc_score(state.robo, state.move);
      //nxt.score = nextscore;
      double nowscore = state.score;
    
      double temp = start_tmp + (end_tmp - start_tmp) * (chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count()) / sa_end_time;

      double prob = exp((nextscore - nowscore)/temp);
      if (prob > (randxor() % 10000)/10000.0) {
        state.score = nextscore;
      }
      else {
        swap(state.move[posi], state.move[posi+1]);  
      }
    }
    else if (opt == 4) {
      int p1 = 1 + (randxor() % max(1, (int)state.move.size() - 2));
      int p2 = 1 + (randxor() % max(1, (int)state.move.size() - 2));
      swap(state.move[p1], state.move[p2]);
      double nextscore = calc_score(state.robo, state.move);
      //nxt.score = nextscore;
      double nowscore = state.score;
    
      double temp = start_tmp + (end_tmp - start_tmp) * (chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count()) / sa_end_time;

      double prob = exp((nextscore - nowscore)/temp);
      if (prob > (randxor() % 10000)/10000.0) {
        state.score = nextscore;
      }
      else {
        swap(state.move[p1], state.move[p2]);  
      }
    }
    else if (opt == 5) {
      STATE nxt = state;
      int posi = 1 + (randxor() % (max(1, (int)state.move.size() - 2)));
      vi tmp = nxt.move[posi];
      nxt.move.erase(nxt.move.begin() + posi);
      int ad = 1 + (randxor() % (max(1, (int)state.move.size() - 2)));
      nxt.move.insert(nxt.move.begin() + ad, tmp);
      double nextscore = calc_score(nxt.robo, nxt.move);
      nxt.score = nextscore;
      double nowscore = state.score;
    
      double temp = start_tmp + (end_tmp - start_tmp) * (chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count()) / sa_end_time;

      double prob = exp((nextscore - nowscore)/temp);
      if (prob > (randxor() % 10000)/10000.0) {
        state = nxt;
      }
      
    }
    
  }
  
  print("cnt=", cnt);
  print(state.score);
  print_ans(state.robo, state.move);
  
}

int main()
{
  load_data();
  simulated_annealing();

}
0