Topcoder Marathon Match 97 最終結果
作成日：2018.02.01
カテゴリー：競プロ 参戦記録
▼更新履歴
- 2018.02.08
最終結果、反省を追加
目次
最終結果
$904106.82$点で順位はシステムテスト前から$3$つ上げて$6$位。
解法
遷移が2点swapだけの焼きなまし+山登りで、$2.5$秒行った後さらに$15$回行う。
焼きなましの温度変化は線形である。
2点swapは、初めの$3/4$の時間では$1 + N/16$以下の距離(円弧上で隣り合うものの距離を$1$とする)にある点対のみを見て、残り$1/4$では徐々にその距離を小さくしていく。
主な高速化は以下の2つである。
1つ目は、2点間の距離は初めに計算しておき、$10^5$倍した値を整数に丸めて扱うことである。
2つ目は、2点swapの際に確認するべき頂点、すなわちswapする2点のうち片方とのみ辺がつながっているものを事前に列挙しておくことである。
ソースコード
#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
typedef int_fast64_t LL;
const LL PER_SEC = 2800000000;
inline LL get_time(){
uint_fast32_t low,high;
__asm__ volatile("rdtsc" : "=a"(low) , "=d"(high));
return (LL)low | ((LL)high<<32);
}
inline unsigned int xor128(){
static unsigned int x=987654301,y=362436069,z=521288629,w=88675123;
unsigned int t = (x^(x<<11));
x=y;y=z;z=w;
return w=(w^(w>>19))^(t^(t>>8));
}
inline double rnd(){
return xor128() / 4294967296.0;
}
typedef int score_type;
typedef uint_fast8_t data_type;
const int REPEAT = 20;
const int FIRST_BONUS = 5;
const LL MAX_TIME = 9.95 * PER_SEC / REPEAT;
const int MC = 256;
const int SCORE_SCALE = 100000;
const double PI = 3.14159265358979;
class PointsOnTheCircle {
int N;
bool be_edge[MC][MC];
score_type length[MC][MC];
vector<data_type> V[MC][MC]; //V[i][j] : iとの間には辺があり、jとの間には辺がない頂点の集合
data_type best[MC];
data_type ans[MC];
data_type pos[MC]; //pos[ans[i]] = i
score_type now_score,best_score;
LL end_time;
void SA(){ //焼きなまし
LL now_time = get_time();
constexpr double const_temp = 2.0/SCORE_SCALE*MAX_TIME;
double temp;
int d_max;
while(now_time < end_time){
temp = const_temp / (end_time - now_time);
d_max = 1 + N/4 * min(0.25,1.*(end_time - now_time)/MAX_TIME);
for(data_type i = 0 ; i < N ; ++i) for(data_type di = 1 ; di <= d_max ; ++di){
data_type j = i + di;
if(j>=N) j -= N;
score_type dif_score = 0;
for(auto k : V[ans[i]][ans[j]]) dif_score += length[i][pos[k]] - length[j][pos[k]];
for(auto k : V[ans[j]][ans[i]]) dif_score += length[j][pos[k]] - length[i][pos[k]];
if(dif_score > 0 || exp(dif_score*temp) > rnd()){
now_score -= dif_score;
pos[ans[i]] = j; pos[ans[j]] = i;
swap(ans[i],ans[j]);
if(now_score < best_score){
memcpy(best,ans,N*sizeof(data_type));
best_score = now_score;
}
}
}
now_time = get_time();
}
//以下、山登り
bool b = 1;
while(b){
b = 0;
for(data_type i = 0 ; i < N ; ++i) for(data_type di = 1 ; di <= d_max ; ++di){
data_type j = i + di;
if(j>=N) j -= N;
score_type dif_score = 0;
for(auto k : V[ans[i]][ans[j]]) dif_score += length[i][pos[k]] - length[j][pos[k]];
for(auto k : V[ans[j]][ans[i]]) dif_score += length[j][pos[k]] - length[i][pos[k]];
if(dif_score > 0){
now_score -= dif_score;
pos[ans[i]] = j; pos[ans[j]] = i;
swap(ans[i],ans[j]);
b = 1;
}
}
}
if(now_score < best_score){
memcpy(best,ans,N*sizeof(data_type));
best_score = now_score;
}
}
public:
vector<int> permute(vector<int> matrix) {
//prepare
end_time = get_time() + MAX_TIME * FIRST_BONUS;
N = sqrt(matrix.size());
for(int j = 0 ; j < N ; ++j) length[0][j] = 2.0 * sin(j*PI/N) * SCORE_SCALE + 0.5;
for(int i = 1 ; i < N ; ++i) for(int j = 0 ; j < N ; ++j) length[i][j] = length[0][abs(i-j)];
now_score = 0;
for(int i = 0 ; i < N ; ++i) for(int j = 0 ; j < N ; ++j){
be_edge[i][j] = matrix[i*N+j];
if(be_edge[i][j] && i < j) now_score += length[i][j];
}
for(int i = 0 ; i < N ; ++i) best[i] = ans[i] = pos[i] = i;
best_score = now_score;
for(int i = 0 ; i < N ; ++i) for(int j = i+1 ; j < N ; ++j){
for(data_type k = 0 ; k < N ; ++k) if(k != i && k != j){
if(be_edge[i][k]&&!be_edge[j][k]) V[i][j].push_back(k);
if(be_edge[j][k]&&!be_edge[i][k]) V[j][i].push_back(k);
}
}
//solve
for(int i = FIRST_BONUS-1 ; i < REPEAT ; ++i){
SA();
end_time += MAX_TIME;
}
//output
vector<int> ret(N);
for(int i = 0 ; i < N ; ++i) ret[i] = best[i];
return ret;
}
};反省
スコアの整数化が逆効果である可能性があるようなので調べてみた。
するとint型よりdouble型を用いた方が若干スコアが良く、意外にもdouble型の方が高速であることが分かった。
ちなみに最大ケースにおける整数化による誤差はおおよそ$5 \times 10^{-4}$であった。
double型よりもint型の方が絶対良いという思い込みがあったが、今回はそれに反していた。
また序盤に比較したことが終盤で覆る可能性があることも分かった。
今後のマラソンマッチで終盤に打つ手がなくなってきた時は、序盤に確かめたことをもう一回確かめることにしたい。
＜(古い記事) Topcoder Marathon Match 97
関連
(新しい記事)＞
＜(古い記事) Topcoder Marathon Match 97