結果

問題 No.5007 Steiner Space Travel
ユーザー hangryhangry
提出日時 2022-07-30 16:03:42
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 954 ms / 1,000 ms
コード長 7,351 bytes
コンパイル時間 2,186 ms
実行使用メモリ 4,304 KB
スコア 6,714,640
最終ジャッジ日時 2022-07-30 16:04:17
合計ジャッジ時間 32,806 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 953 ms
4,064 KB
testcase_01 AC 954 ms
3,984 KB
testcase_02 AC 953 ms
4,304 KB
testcase_03 AC 954 ms
4,096 KB
testcase_04 AC 953 ms
3,996 KB
testcase_05 AC 953 ms
4,152 KB
testcase_06 AC 953 ms
4,104 KB
testcase_07 AC 953 ms
4,296 KB
testcase_08 AC 952 ms
4,060 KB
testcase_09 AC 954 ms
4,296 KB
testcase_10 AC 954 ms
3,988 KB
testcase_11 AC 952 ms
4,004 KB
testcase_12 AC 953 ms
4,156 KB
testcase_13 AC 954 ms
4,068 KB
testcase_14 AC 953 ms
4,148 KB
testcase_15 AC 954 ms
4,064 KB
testcase_16 AC 952 ms
4,084 KB
testcase_17 AC 953 ms
4,116 KB
testcase_18 AC 953 ms
4,300 KB
testcase_19 AC 953 ms
4,064 KB
testcase_20 AC 952 ms
4,052 KB
testcase_21 AC 953 ms
4,060 KB
testcase_22 AC 953 ms
4,184 KB
testcase_23 AC 953 ms
4,180 KB
testcase_24 AC 954 ms
4,060 KB
testcase_25 AC 954 ms
4,008 KB
testcase_26 AC 954 ms
4,104 KB
testcase_27 AC 953 ms
4,148 KB
testcase_28 AC 953 ms
4,060 KB
testcase_29 AC 954 ms
3,980 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 = 150;
  double end_tmp = 1;
  int sa_end_time = 950;
  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 % 100 == 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() % 5;
    //int opt = 3;
    if (opt == 0) {
      int posi = randxor() % 8;
      nxt.robo[posi][0] += -min(50, nxt.robo[posi][0]) + (randxor() % max(1, min(50, nxt.robo[posi][0])+min(50, 1000-nxt.robo[posi][0])));
      nxt.robo[posi][1] += -min(50, nxt.robo[posi][1]) + (randxor() % max(1, min(50, nxt.robo[posi][1])+min(50, 1000-nxt.robo[posi][1])));
      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;
      }
    }
    else if (opt == 1) {
      int posi = 1 + randxor() % (max(1, (int)nxt.move.size()-2));
      int tp = randxor() % 10;
      if (tp < 3) {
        int ad = randxor() % 8;
        nxt.move.insert(nxt.move.begin() + posi, {2, ad});
      }
      else {
        int ad = randxor() % 100;
        nxt.move.insert(nxt.move.begin() + posi, {1, ad});
        nxt.cnt[ad] += 1;
      }
      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;
      }
    }
    else if ( opt == 2) {
      int posi = 1 + (randxor() % (max(1, (int)nxt.move.size() - 2)));
      
      if (nxt.move[posi][0] == 1) {
        if (nxt.cnt[nxt.move[posi][1]] > 1) {
          nxt.cnt[nxt.move[posi][1]] -= 1;
          nxt.move.erase(nxt.move.begin() + posi);
        }
      } 
      else nxt.move.erase(nxt.move.begin() + posi);
      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;
      }
    }
    else if (opt == 3) {
      int posi = 1 + (randxor() % max(1, (int)nxt.move.size() - 3));
      swap(nxt.move[posi], nxt.move[posi+1]);
      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;
      }
    }
    else if (opt == 4) {
      int p1 = 1 + (randxor() % max(1, (int)nxt.move.size() - 3));
      int p2 = 1 + (randxor() % max(1, (int)nxt.move.size() - 2));
      swap(nxt.move[p1], nxt.move[p2]);
      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