結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 ks2m
|
| 提出日時 | 2022-07-30 17:47:03 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 991 ms / 1,000 ms |
| コード長 | 8,305 bytes |
| コンパイル時間 | 2,763 ms |
| 実行使用メモリ | 67,264 KB |
| スコア | 8,445,894 |
| 最終ジャッジ日時 | 2022-07-30 17:47:38 |
| 合計ジャッジ時間 | 34,544 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge10 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
public class Main {
static boolean batch = false;
static boolean readFile = false;
static int num = 2;
static long limitTime = 870;
static long startTime;
static double startTemp = 2000;
static double endTemp = 10;
static int baseTry = 70;
static int baseNum = 7;
static int startSeni = 300;
static int endSeni = 10;
static int mustMove = 3;
static int a = 5;
static int N, M;
static Obj[] arr, pln;
public static void main(String[] args) throws Exception {
if (batch) {
readFile = true;
}
if (readFile) {
if (batch) {
long tl = 1000;
long tw = (long) (tl * 0.9);
long total = 0;
int bidx = 0;
int best = 0;
int widx = 0;
int worst = 1000000000;
int re = 0;
int tle = 0;
for (int z = 0; z < 30; z++) {
try {
long st = System.currentTimeMillis();
int score = solve(z);
long time = System.currentTimeMillis() - st;
if (time > tw) {
System.out.println(z + ":\t" + score + "\t" + time + "ms");
if (time > tl) {
tle++;
}
} else {
System.out.println(z + ":\t" + score);
}
total += score;
if (score > best) {
best = score;
bidx = z;
}
if (score < worst) {
worst = score;
widx = z;
}
} catch (Exception e) {
System.out.println(z + ":\t" + e.getMessage());
re++;
}
}
System.out.println("total: " + total);
System.out.println("best: " + bidx + ": " + best);
System.out.println("worst: " + widx + ": " + worst);
System.out.println("RE: " + re);
System.out.println("TLE: " + tle);
} else {
int score = solve(num);
System.out.println(score);
}
} else {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
init(br);
solve();
}
}
static int solve(int z) throws Exception {
StringBuilder sb = new StringBuilder();
sb.append(z);
while (sb.length() < 4) {
sb.insert(0, '0');
}
File file = new File("G:\\input\\" + sb.toString() + ".txt");
BufferedReader br = new BufferedReader(new FileReader(file));
init(br);
return solve();
}
static void init(BufferedReader br) throws Exception {
startTime = System.currentTimeMillis();
String[] sa = br.readLine().split(" ");
N = Integer.parseInt(sa[0]);
M = Integer.parseInt(sa[1]);
arr = new Obj[N + M];
pln = new Obj[N];
for (int i = 0; i < N; i++) {
sa = br.readLine().split(" ");
Obj o = new Obj();
o.t = 1;
o.i = i;
o.x = Integer.parseInt(sa[0]);
o.y = Integer.parseInt(sa[1]);
pln[i] = o;
arr[i] = o;
}
}
static int solve() throws Exception {
Ans ans = new Ans();
PriorityQueue<Ans> que = new PriorityQueue<>((o1, o2) -> o1.score - o2.score);
for (int i = 0; i < baseTry; i++) {
Ans res = solve2(null, 0);
que.add(res);
if (que.size() > baseNum) {
que.poll();
}
if (res.score > ans.score) {
ans = res;
}
}
for (Ans o : que) {
if (o.score > ans.score) {
ans = o;
}
}
int ok = 0;
int ng = 0;
int upd = 0;
while (true) {
long time = System.currentTimeMillis() - startTime;
if (time > limitTime) {
break;
}
double ratio = (double) time / limitTime;
double temp = startTemp * (1 - ratio) + endTemp * ratio;
int seni = (int) (startSeni * (1 - ratio) + endSeni * ratio);
PriorityQueue<Ans> wk = new PriorityQueue<>((o1, o2) -> o1.score - o2.score);
for (Ans base : que) {
Ans res = solve2(base, seni);
double prob = Math.exp((res.score - base.score) / temp);
if (Math.random() < prob) {
wk.add(res);
ok++;
} else {
wk.add(base);
ng++;
}
if (res.score > ans.score) {
ans = res;
upd++;
}
}
boolean flg = false;
for (Ans o : wk) {
if (o.score == ans.score) {
flg = true;
break;
}
}
if (!flg) {
wk.add(ans);
wk.poll();
}
que = wk;
}
if (!batch) {
PrintWriter pw = new PrintWriter(System.out);
for (Obj o : ans.sta) {
pw.println(o.x + " " + o.y);
}
pw.println(ans.his.size());
for (int cur : ans.his) {
int ct = cur / N;
int ci = cur % N;
pw.println(ct + " " + (ci + 1));
}
if (readFile) {
pw.println("ok: " + ok);
pw.println("ng: " + ng);
pw.println("upd: " + upd);
}
pw.flush();
}
return ans.score;
}
static Ans solve2(Ans base, int seni) throws Exception {
// 宇宙ステーションの配置
Obj[] sta = new Obj[M];
if (base == null) {
for (int i = 0; i < M; i++) {
Obj o = new Obj();
o.t = 2;
o.i = i;
o.x = rand(100, 900);
o.y = rand(100, 900);
while (true) {
boolean flg = true;
for (int j = 0; j < i; j++) {
Obj o2 = sta[j];
if (dist(o, o2) < 200) {
flg = false;
break;
}
}
if (flg) {
break;
}
o.x = rand(100, 900);
o.y = rand(100, 900);
}
sta[i] = o;
arr[N + i] = o;
}
} else {
Obj[] src = base.sta;
for (int i = 0; i < M; i++) {
Obj o = new Obj();
o.t = 2;
o.i = i;
o.x = src[i].x;
o.y = src[i].y;
sta[i] = o;
arr[N + i] = o;
}
int[] cnt = new int[M];
for (int i : base.his) {
if (i / N == 2) {
cnt[i % N]++;
}
}
List<Integer> list = new ArrayList<>();
for (int i = 0; i < M; i++) {
if (cnt[i] <= mustMove) {
list.add(i);
}
}
list.add(rand(0, M - 1));
for (int idx : list) {
int dx = rand(-seni, seni);
int dy = rand(-seni, seni);
Obj o = sta[idx];
o.x = Math.min(Math.max(o.x + dx, 50), 950);
o.y = Math.min(Math.max(o.y + dy, 50), 950);
}
}
// 最も近い宇宙ステーションを設定
for (Obj o : pln) {
o.costs = Integer.MAX_VALUE;
for (Obj o2 : sta) {
int e = cost(o, o2);
if (e < o.costs) {
o.costs = e;
o.sta = o2;
}
}
}
Set<Integer> rem = new HashSet<>();
for (int i = 1; i < N; i++) {
rem.add(i);
}
List<Integer> his = new ArrayList<>();
his.add(toInt(pln[0]));
Obj now = pln[0];
while (!rem.isEmpty()) {
int min = Integer.MAX_VALUE;
List<Integer> nexts = new ArrayList<>(3);
for (int i : rem) {
min = minCost(now, pln[i], min, nexts);
}
his.addAll(nexts);
int next = his.get(his.size() - 1) % N;
now = pln[next];
rem.remove(next);
}
List<Integer> nexts = new ArrayList<>(3);
minCost(now, pln[0], Integer.MAX_VALUE, nexts);
his.addAll(nexts);
// 得点計算
int s = 0;
int v = his.size();
for (int i = 1; i < v; i++) {
int cur = his.get(i);
int pre = his.get(i - 1);
int e = cost(arr[pre - N], arr[cur - N]);
s += e;
}
int score = (int) Math.round(1000000000 / (1000 + Math.sqrt(s)));
Ans ans = new Ans();
ans.sta = sta;
ans.his = his;
ans.score = score;
return ans;
}
static int minCost(Obj now, Obj o, int min, List<Integer> nexts) {
int d = cost(now, o);
if (d < min) {
min = d;
nexts.clear();
nexts.add(toInt(o));
}
d = cost(now, now.sta) + cost(now.sta, o);
if (d < min) {
min = d;
nexts.clear();
nexts.add(toInt(now.sta));
nexts.add(toInt(o));
}
d = cost(now, o.sta) + cost(o.sta, o);
if (d < min) {
min = d;
nexts.clear();
nexts.add(toInt(o.sta));
nexts.add(toInt(o));
}
d = cost(now, now.sta) + cost(now.sta, o.sta) + cost(now.sta, o);
if (d < min) {
min = d;
nexts.clear();
nexts.add(toInt(now.sta));
nexts.add(toInt(o.sta));
nexts.add(toInt(o));
}
return min;
}
static int dist(Obj o1, Obj o2) {
int dx = o1.x - o2.x;
int dy = o1.y - o2.y;
return dx * dx + dy * dy;
}
static int cost(Obj o1, Obj o2) {
int e = dist(o1, o2);
if (o1.t == 1) e *= a;
if (o2.t == 1) e *= a;
return e;
}
static int toInt(Obj o) {
return o.t * N + o.i;
}
static int rand(int l, int u) {
int d = u - l + 1;
int x = (int) (Math.random() * d);
return x + l;
}
static class Obj {
int t, i, x, y;
Obj sta;
int costs;
}
static class Ans {
Obj[] sta;
List<Integer> his;
int score;
}
}