結果

問題 No.5008 [Cherry Alpha] Discrete Pendulum with Air Resistance
ユーザー EvbCFfp1XBEvbCFfp1XB
提出日時 2022-10-14 23:55:56
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,945 ms / 2,000 ms
コード長 12,787 bytes
コンパイル時間 3,282 ms
実行使用メモリ 54,360 KB
スコア 387,125,189,424,599
最終ジャッジ日時 2022-10-14 23:57:48
合計ジャッジ時間 110,324 ms
ジャッジサーバーID
(参考情報)
judge8 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Calendar;
import java.util.Scanner;
import java.util.TimeZone;
import java.util.stream.IntStream;
public class Main {
final int maxB = 1000000;
private int N;
private int K;
private int[] T;
private int[] U;
private int[] B;
private int[] M;
private int[] E;
private double score = (int) -1e18;
private double bestScore = -1e18;
private SAState sa = new SAState();
public static void main(String[] args) throws Exception {
// Utils.debug(CalendarUtils.toStringTimeLeft(new Calendar.Builder().setTimeZone(TimeZone.getTimeZone("GMT+9:00")).setInstant(Calendar
    .getInstance().getTime()).build(), Constants.endTime));
new Main().run();
}
private void run() {
read();
solve();
write();
}
private void read() {
try (final Scanner in = new Scanner(System.in)) {
N = in.nextInt();
Constants.watch.init();
K = in.nextInt();
T = IntStream.range(0, K).map(i -> in.nextInt()).toArray();
U = IntStream.range(0, K).map(i -> in.nextInt()).toArray();
} catch (Exception e) {
e.printStackTrace();
}
}
private void solve() {
B = new int[N];
M = new int[N];
E = new int[N];
for (int i = 0; i < N; i++) {
B[i] = 1 + Constants.RNG.nextInt(maxB);
M[i] = B[i];
E[i] = 1;
}
score = calculateScore();
multiSA();
// Utils.debug("time", Constants.watch.getSecondString());
}
private void saveBest() {
if (score > bestScore) {
bestScore = score;
}
}
private void restoreBest() {
}
private void multiSA() {
int numRestart = 1;
double startTime = Constants.watch.getSecond();
double endTime = 1.75;
double remainTime = endTime - startTime;
double startStartTemperature = 1e1;
double endStartTemperature = 1e-9;
for (double restart = 0; restart < numRestart; restart++) {
sa.startTime = startTime + remainTime * restart / numRestart;
sa.endTime = startTime + remainTime * (restart + 1) / numRestart;
sa.startTemperature = endStartTemperature + (startStartTemperature - endStartTemperature) * ((numRestart - restart) / numRestart);
sa.endTemperature = 1e-9;
SA();
}
// Utils.debug("multiSA", "score", score, "time", Constants.watch.getSecondString());
}
private void SA() {
// final double deltaSecond = (sa.endTime - sa.startTime) * 0.999 / 10;
// double thresholdSecond = sa.startTime + deltaSecond;
sa.init();
for (;; ++sa.numIterations) {
if ((sa.numIterations & ((1 << 5) - 1)) == 0) {
sa.update();
// if (sa.time > thresholdSecond) {
// thresholdSecond += deltaSecond;
// Utils.debug(sa.numIterations, String.format("%6.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%6.2f%%",
    100.0 * sa.acceptIterations / sa.validIterations), String.format("%5.0f", score), String.format("%5.0f", bestScore), String.format("%8.6f", 1.0 /
    sa.inverseTemperature), String.format("%8.6f", 1.0 / sa.lastAcceptTemperature), sa.time);
// }
if (sa.isTLE()) {
break;
}
}
mutate();
}
}
private void mutate() {
change();
}
private void change() {
int i = sa.numIterations % N;
int current = B[i];
B[i] = 1 + Constants.RNG.nextInt(maxB);
double deltaScore = calculateScore() - score;
if (sa.accept(deltaScore)) {
score += deltaScore;
M[i] = B[i];
saveBest();
} else {
B[i] = current;
}
}
private double calculateScore() {
int[] x = new int[N];
double scoreT = 0;
for (int k = 0; k < K; k++) {
for (int n = 0; n < N; n++) {
x[n] = T[k] % (4 * B[n]);
if (x[n] <= B[n]) {
x[n] = 0 + (x[n] - 0);
} else if (x[n] <= 2 * B[n]) {
x[n] = (B[n] - 1) - (x[n] - B[n]);
} else if (x[n] <= 3 * B[n]) {
x[n] = 0 - (x[n] - 2 * B[n]);
} else if (x[n] < 4 * B[n]) {
x[n] = -(B[n] - 1) + (x[n] - 3 * B[n]);
}
}
double sum = 0;
for (int i = 0; i < x.length; i++) {
for (int j = i + 1; j < x.length; j++) {
sum += Math.abs(x[i] - x[j]) / (double) (B[i] + B[j]);
}
}
scoreT += 2e7 / (N * (N - 1)) * sum;
}
double scoreU = 0;
for (int k = 0; k < K; k++) {
for (int n = 0; n < N; n++) {
x[n] = U[k] % (4 * B[n]);
if (x[n] <= B[n]) {
x[n] = 0 + (x[n] - 0);
} else if (x[n] <= 2 * B[n]) {
x[n] = (B[n] - 1) - (x[n] - B[n]);
} else if (x[n] <= 3 * B[n]) {
x[n] = 0 - (x[n] - 2 * B[n]);
} else if (x[n] < 4 * B[n]) {
x[n] = -(B[n] - 1) + (x[n] - 3 * B[n]);
}
}
double max = 0;
for (int i = 0; i < x.length; i++) {
for (int j = i + 1; j < x.length; j++) {
max += Math.abs(x[i] - x[j]);
}
}
scoreU += 1e7 / Math.sqrt(1 + max / 20.0);
}
scoreT /= K;
scoreU /= K;
return scoreU * scoreT * 1e-9;
}
private void write() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
sb.append(B[i]).append(' ');
sb.append(M[i]).append(' ');
sb.append(E[i]).append('\n');
}
System.out.print(sb.toString());
System.out.flush();
}
}
class SAState {
public static final boolean useTime = true;
public double startTime;
public double endTime;
public double time;
public double startTemperature;
public double endTemperature;
public double inverseTemperature;
public double lastAcceptTemperature;
public double startRange;
public double endRange;
public double range;
public int numIterations;
public int validIterations;
public int acceptIterations;
private double[] log = new double[32768];
public SAState() {
for (int i = 0; i < log.length; i++) {
log[i] = Math.log((i + 0.5) / log.length);
}
}
public void init() {
numIterations = 0;
validIterations = 0;
acceptIterations = 0;
startTime = useTime ? Constants.watch.getSecond() : numIterations;
update();
lastAcceptTemperature = inverseTemperature;
}
public void update() {
updateTime();
updateTemperature();
}
public boolean useExp = !true;
public void updateTemperature() {
if (useExp) {
double time0to1 = elapsedPercentage(startTime, endTime, time);
double startY = startTemperature;
double endY = endTemperature;
double startX = Math.log(startY);
double endX = Math.log(endY);
double xStartToEnd = interpolate(startX, endX, time0to1);
double temperature = Math.exp(xStartToEnd);
inverseTemperature = 1.0 / temperature;
} else {
double time0to1 = elapsedPercentage(startTime, endTime, time);
double startY = startTemperature;
double endY = endTemperature;
double temperature = interpolate(startY, endY, time0to1);
inverseTemperature = 1.0 / temperature;
}
}
private double elapsedPercentage(double min, double max, double v) {
return (v - min) / (max - min);
}
private double interpolate(double v0, double v1, double d0to1) {
return v0 + (v1 - v0) * d0to1;
}
public void updateRange() {
range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
}
public void updateTime() {
time = useTime ? Constants.watch.getSecond() : numIterations;
}
public boolean isTLE() {
return time >= endTime;
}
public boolean accept(double deltaScore) {
return acceptB(deltaScore);
}
public boolean acceptB(double deltaScore) {
validIterations++;
if (deltaScore > -1e-9) {
acceptIterations++;
return true;
}
double d = deltaScore * inverseTemperature;
if (d < -10) {
return false;
}
if (log[Constants.RNG.nextInt() & 32767] < d) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
return true;
}
return false;
}
public boolean acceptS(double deltaScore) {
validIterations++;
if (deltaScore < 1e-9) {
acceptIterations++;
return true;
}
double d = -deltaScore * inverseTemperature;
if (d < -10) {
return false;
}
if (log[Constants.RNG.nextInt() & 32767] < d) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
return true;
}
return false;
}
}
final class Utils {
private Utils() {
}
public static final void debug(Object... o) {
System.err.println(toString(o));
System.err.flush();
}
public static final String toString(Object... o) {
return Arrays.deepToString(o);
}
public static boolean isValid(int v, int min, int minUpper) {
return v >= min && v < minUpper;
}
public static final int manhattanDistance(final int r1, final int c1, final int r2, final int c2) {
final int deltaR = r2 - r1;
final int deltaC = c2 - c1;
return Math.abs(deltaR) + Math.abs(deltaC);
}
public static final <T> void reverseInPlace(final ArrayList<T> list) {
for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
list.set(r, list.set(l, list.get(r)));
}
}
}
class Watch {
private long start;
public Watch() {
init();
}
public double getSecond() {
return (System.nanoTime() - start) * 1e-9;
}
public void init() {
init(System.nanoTime());
}
private void init(long start) {
this.start = start;
}
public String getSecondString() {
return toString(getSecond());
}
public static final String toString(double second) {
if (second < 60) {
return String.format("%5.2fs", second);
} else if (second < 60 * 60) {
int minute = (int) (second / 60);
return String.format("%2dm%2ds", minute, (int) (second % 60));
} else {
int hour = (int) (second / (60 * 60));
int minute = (int) (second / 60);
return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
}
}
}
interface Constants {
Calendar startTime = new Calendar.Builder().setTimeZone(TimeZone.getTimeZone("GMT+9:00")).set(Calendar.YEAR, 2022).set(Calendar.MONTH, 8 - 1).set
        (Calendar.DAY_OF_MONTH, 6).set(Calendar.HOUR_OF_DAY, 1).set(Calendar.MINUTE, 35).set(Calendar.SECOND, 0).build();
Calendar endTime = new Calendar.Builder().setTimeZone(TimeZone.getTimeZone("GMT+9:00")).set(Calendar.YEAR, 2022).set(Calendar.MONTH, 8 - 1).set
        (Calendar.DAY_OF_MONTH, 9).set(Calendar.HOUR_OF_DAY, 1).set(Calendar.MINUTE, 35).set(Calendar.SECOND, 0).build();
Watch watch = new Watch();
PCG_XSH_RR RNG = new PCG_XSH_RR(System.nanoTime());
int[] dr = { -1, 0, 0, 1, };
int[] dc = { 0, -1, 1, 0, };
}
final class PCG_XSH_RR {
private long state = 5342;
public PCG_XSH_RR(final long state) {
this.state = state;
}
public int nextInt() {
final long oldstate = state;
state = oldstate * 6364136223846793005L + 521L;
final int xorshift = (int) (((oldstate >>> 18) ^ oldstate) >>> 27);
final int rotation = (int) (oldstate >>> 59);
return (xorshift >>> rotation) | (xorshift << (-rotation & 31));
}
public int nextInt(int n) {
return (int) (n * nextDouble());
}
public double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0