結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー MulticolorWorld
提出日時 2025-02-25 20:56:48
言語 Kotlin
(2.1.0)
結果
AC  
実行時間 678 ms / 2,000 ms
コード長 2,727 bytes
コンパイル時間 17,353 ms
コンパイル使用メモリ 486,764 KB
実行使用メモリ 89,440 KB
スコア 27,209,984
最終ジャッジ日時 2025-02-25 20:57:42
合計ジャッジ時間 52,252 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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, A.last().clone())

    var nowState = state
    var (bestScore, bestScoreAnswer) = state.getScore()
    var nowScore = bestScore
    val startTemp = 500
    val endTemp = 10

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

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

        if(nextScore > nowScore || isForceNext){
            nowState = nextState
            nowScore = nextScore
        }

        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(7).toLong()

    fun transition(){
        val i = (0 until N).random()
        val bb = b[i]
        if(bb < delta) {
            b[i] = bb + delta
        }else if(bb > mod - delta) {
            b[i] = bb - delta
        }else{
            val r = (0..1).random()
            if(r == 0) {
                b[i] = bb + delta
            }else{
                b[i] = bb - delta
            }
        }
    }

    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