結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー MulticolorWorld
提出日時 2025-02-25 21:53:49
言語 Kotlin
(2.1.0)
結果
AC  
実行時間 1,457 ms / 2,000 ms
コード長 2,559 bytes
コンパイル時間 12,688 ms
コンパイル使用メモリ 487,368 KB
実行使用メモリ 89,552 KB
スコア 24,719,729
最終ジャッジ日時 2025-02-25 21:55:27
合計ジャッジ時間 83,220 ms
ジャッジサーバーID
（参考情報） 		judge7 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.lang.Math.pow
import kotlin.math.*

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ")
fun nextIntList() = next().split(" ").map { it.toInt() }
fun nextLongList() = next().split(" ").map { it.toLong() }
fun nextDoubleList() = next().split(" ").map { it.toDouble() }

val mod = 10.0.pow(8).toLong()

fun main(){
    val N = nextInt()
    val A = Array(N){ LongArray(N) }
    for(i in 0 until N){
        val a = nextLongList()
        for(j in 0..i){
            A[i][j] = a[j]
        }
    }
    val state = State(N, A, LongArray(N))

    var nowState = state
    var (bestScore, bestScoreAnswer) = state.getScore()
    var nowScore = bestScore
    val startTemp = 50000
    val endTemp = 100

    for(i in 0 until 20000){
        val nextState = nowState.copy()
        nextState.transition()
        val (nextScore, nextScoreAnswer) = nextState.getScore()

        val temp = startTemp + (endTemp - startTemp) * (i / 20000.0)
        val probability = exp((nextScore - nowScore) / temp)
        val isForceNext = probability > Math.random()

        if(nextScore > nowScore || isForceNext){
            nowState = nextState
            nowScore = nextScore
//            println("iteration: $i, score: $nowScore")
        }

        if(nextScore > bestScore){
            bestScore = nextScore
            bestScoreAnswer = nextScoreAnswer
        }
    }

    println(bestScoreAnswer.joinToString(" "))
}

class State(val N: Int, val A: Array<LongArray>, val b: LongArray){

    val delta = 10.0.pow(6).toLong()

    fun transition(){
        val i = (0 until N).random()

        val d = max(1, 25 - abs(25 - i))

        val bb = b[i]
        b[i] = (bb + (delta / d)) % mod
    }

    fun getScore(): Pair<Long, LongArray> {
        val B = Array(N){ LongArray(N) }
        B[N - 1] = b

        for(i in N - 2 downTo 0){
            for(j in 0..i){
                B[i][j] = (B[i + 1][j] + B[i + 1][j + 1]) % mod
            }
        }

        var maxE = -1L
        for(i in 0 until N){
            for(j in 0..i){
                val e = min(abs(B[i][j] - A[i][j]), (10.0.pow(8) - abs(B[i][j] - A[i][j])).toLong())
                maxE = max(maxE, e)
            }
        }

        val score = 5 * 10.0.pow(8).toLong() - maxE

        return Pair(score, b)
    }

    fun copy(): State {
        val b = LongArray(N)
        for(i in 0 until N){
            b[i] = this.b[i]
        }
        return State(N, A, b)
    }
}
0