#1046094 (Kotlin) No.5021 Addition Pyramid

• 問題: No.5021 Addition Pyramid
• ユーザー: MulticolorWorld
• 提出日時: 2025-02-25 21:04:33
• 言語: Kotlin (2.1.0)
• 結果: RE
• 実行時間: -
• コード長: 18,281 bytes
• コンパイル時間: 20,274 ms
• コンパイル使用メモリ: 565,156 KB
• 実行使用メモリ: 58,024 KB
• スコア: 0
• 最終ジャッジ日時: 2025-02-25 21:05:20
• 合計ジャッジ時間: 39,872 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

ファイルパターン	結果
other	RE * 50

ソースコード

import java.io.*
import java.nio.file.Paths
import java.util.ArrayDeque
import kotlin.math.abs
import kotlin.math.max

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() }

data class Coord(val x: Int, val y: Int)

data class CommuteInfo(val from: Coord, val to: Coord)

// 方向
val delta = arrayOf(Coord(1, 0), Coord(-1, 0), Coord(0, 1), Coord(0, -1))

enum class Env {
    Local,
    Prod
}

data class CalcResult(
    // インデックス
    val index: Int = 0,
    // 最短経路
    val path: List<Coord> = emptyList(),
    // 建築に必要なターン
    val buildTurn: Int = 0,
    // 1ターンあたりの利益
    val benefitPerTurn: Int = 0,
    // この経路の建設を開始するために必要な最小金額
    val buildableMinMoney: Int = 0,
    // この経路の建設を開始するために必要な最小ターン
    val buildableMinTurn: Int = 0,
    // 建てられるようになったら建てる、をした場合の最終ターンまでに出る利益、建てられない場合は0
    val benefitToLastTurn: Int = 0,
    // この経路を立てた場合に、新たに駅の範囲に入るインデックス
    val newConnected: List<BuildableOtherInfo> = emptyList()
)

// 既に建築されている駅の範囲に入っている端と、もう片方の端の情報
data class BuildableOtherInfo(
    val index: Int,
    val other: Coord,
)

// 建築された駅の情報
data class StationInfo(
    // 座標
    val coord: Coord,
    // 残っている建築可能な方向
    val directions: MutableList<Coord>,
)

fun solve() {
    val (N, M, K, T) = nextIntList()
    val commuteInfoList = mutableListOf<CommuteInfo>()

    // 端ともう片方の端の情報
    val coordInfo = Array(N) { Array(N) { mutableListOf<Pair<Int, Coord>>() } }
    for (i in 0 until M) {
        val (si, sj, ti, tj) = nextIntList()
        commuteInfoList.add(CommuteInfo(Coord(si, sj), Coord(ti, tj)))
        coordInfo[si][sj].add(Pair(i, Coord(ti, tj)))
        coordInfo[ti][tj].add(Pair(i, Coord(si, sj)))
    }

    // #: 通れない
    val wall = Array(N) { Array(N) { "" } }
    // 残りターン数
    var remainingTurn = T
    // 所持金額
    var money = K
    // 1ターンに増減する金額
    var moneyDelta = 0
    // 片方が既に建築されている駅の範囲にあるもう片方の座標
    val buildableOther = mutableListOf<BuildableOtherInfo>()
    // 既に建築されている駅の情報
    val stationInfo = mutableListOf<StationInfo>()
    // 既につながっているindex
    val connected = mutableSetOf<Int>()

    // 初期解生成
    val pathAndBenefit = calculatePathAndBenefit(M, N, commuteInfoList, T, money, coordInfo)
    val p = pathAndBenefit.filter { it.benefitToLastTurn != 0 && it.newConnected.size >= 2 }.maxByOrNull { it.benefitPerTurn }
    if(p != null) {
        println("# build start: ${p.index}")
        val path = p.path
        val pathString = convertPathToString(path)
        for (i in 1 until pathString.size - 1) {
            println(pathString[i])
        }
        println(pathString.first())
        println(pathString.last())

        for (c in path) {
            wall[c.x][c.y] = "#"
        }

        connected.add(p.index)

        // 駅情報の更新
        val startDirection = Coord(path[1].x - path[0].x, path[1].y - path[0].y)
        stationInfo.add(StationInfo(path[0], delta.filter { it != startDirection }.toMutableList()))
        val endDirection = Coord(path[path.size - 2].x - path[path.size - 1].x, path[path.size - 2].y - path[path.size - 1].y)
        stationInfo.add(StationInfo(path[path.size - 1], delta.filter { it != endDirection }.toMutableList()))

        // 駅範囲に入っている座標情報の更新
        buildableOther.addAll(p.newConnected)

        money -= p.buildableMinMoney
        moneyDelta += p.benefitPerTurn
        remainingTurn -= p.buildTurn

        println("# build end index: ${p.index}")
        println("# connected: ${connected.sorted().joinToString(", ")}")
        println("# remain: ${buildableOther.map { it.index }.sorted().joinToString(" ")}")
    }

    var reCalcFlag = false
    var result = calcB(N, remainingTurn, money, commuteInfoList, moneyDelta, buildableOther, stationInfo, wall, connected)

    while (remainingTurn > 0) {
        if(reCalcFlag){
            result = calcB(N, remainingTurn, money, commuteInfoList, moneyDelta, buildableOther, stationInfo, wall, connected)
            reCalcFlag = false
        }

        val p2 = result.sortedBy { it.benefitToLastTurn }.lastOrNull { it.benefitToLastTurn > 0 }
        if(p2 != null){
            if(p2.path.size == 1){
                connected.add(p2.index)
                reCalcFlag = true
                continue
            }
            println("# build start: ${p2.index}")
            if (p2.buildableMinTurn != 0) {
                repeat(p2.buildableMinTurn) {
                    money += moneyDelta
                    remainingTurn--
                    println(-1)
                }
            }
            val path = p2.path
            val pathString = convertPathToString(path)
            for (i in 1 until pathString.size - 1) {
                println(pathString[i])
            }
            println(pathString.last())

            for (c in path) {
                wall[c.x][c.y] = "#"
            }

            connected.add(p2.index)
            buildableOther.removeAll{ it.index == p2.index }

            stationInfo.find { it.coord == path[0] }?.directions?.remove(Coord(path[1].x - path[0].x, path[1].y - path[0].y))
            val endDirection = Coord(path[path.size - 2].x - path[path.size - 1].x, path[path.size - 2].y - path[path.size - 1].y)
            stationInfo.add(StationInfo(path[path.size - 1], delta.filter { it != endDirection }.toMutableList()))

            val newStation = path[path.size - 1]
            // 新しい駅範囲に入っている座標情報の更新
            for(i in -2 until 3) {
                for (j in -2 until 3) {
                    if (abs(i) + abs(j) <= 2) {
                        val x = newStation.x + i
                        val y = newStation.y + j
                        if (x in 0 until N && y in 0 until N) {
                            for (c in coordInfo[x][y]) {
                                val (index, other) = c
                                if (buildableOther.map { it.index }.contains(index)) {
                                    continue
                                }
                                if (!connected.contains(index)) {
                                    buildableOther.add(BuildableOtherInfo(index, other))
                                }
                            }
                        }
                    }
                }
            }

            money -= p2.buildableMinMoney
            moneyDelta += p2.benefitPerTurn
            remainingTurn -= p2.buildTurn
            reCalcFlag = true
            println("# build end index: ${p2.index}")
            println("# connected: ${connected.sorted().joinToString(", ")}")
            println("# remain: ${buildableOther.map { it.index }.sorted().joinToString(" ")}")
        } else {
            remainingTurn--
            money += moneyDelta
            println(-1)
        }
    }
}

// 駅の範囲に入っている座標のペアへの経路を探索し、最短経路や利益などの情報を計算する
fun calcB(
    N: Int,
    remainingTurn: Int, money: Int,
    commuteInfoList: List<CommuteInfo>,
    moneyDelta: Int, buildableOther: List<BuildableOtherInfo>,
    stationInfo: List<StationInfo>, wall: Array<Array<String>>,
    connected: MutableSet<Int>
): List<CalcResult>{
    val dist = Array(N) { IntArray(N) { -1 } }
    val before = Array(N) { Array(N) { Coord(-1, -1) } }
    val queue = ArrayDeque<Coord>()
    val endPoint = buildableOther.filter { !connected.contains(it.index) }.map { it.other }.toMutableList()
    for(s in stationInfo){
        dist[s.coord.x][s.coord.y] = 0
        for(d in s.directions){
            val dx = s.coord.x + d.x
            val dy = s.coord.y + d.y
            if (dx in 0 until N && dy in 0 until N) {
                if (dist[dx][dy] == -1) {
                    if (wall[dx][dy] == "") {
                        dist[dx][dy] = dist[s.coord.x][s.coord.y] + 1
                        before[dx][dy] = s.coord
                        queue.add(Coord(dx, dy))
                    }
                }
            }
        }
    }

    while (queue.isNotEmpty()) {
        val v = queue.removeFirst()
        if(endPoint.contains(v)){
            endPoint.remove(v)
            if(endPoint.isEmpty()){
                break
            }
            continue
        }

        for (d in delta) {
            val dx = v.x + d.x
            val dy = v.y + d.y
            if (dx in 0 until N && dy in 0 until N) {
                if (dist[dx][dy] == -1) {
                    if (wall[dx][dy] == "") {
                        dist[dx][dy] = dist[v.x][v.y] + 1
                        before[dx][dy] = v
                        queue.add(Coord(dx, dy))
                    }
                }
            }
        }
    }

    val result = mutableListOf<CalcResult>()
    for(e in buildableOther.filter { !connected.contains(it.index) }){
        if (dist[e.other.x][e.other.y] == -1) {
            continue
        }
        // 経路復元
        val path = mutableListOf<Coord>()
        var c = e.other
        while (dist[c.x][c.y] > 0) {
            path.add(c)
            c = before[c.x][c.y]
        }
        path.add(c)
        path.reverse()

        // 1ターンあたりの利益
        val benefitPerTurn = abs(commuteInfoList[e.index].from.x - commuteInfoList[e.index].to.x) +
                abs(commuteInfoList[e.index].from.y - commuteInfoList[e.index].to.y)
        // 建築に必要なターン
        val buildTurn = path.size - 1
        // この経路の建設を開始するために必要な最小金額
        val buildableMinMoney = (100 - moneyDelta) * (buildTurn - 1) + (5000 - moneyDelta) * 1 + moneyDelta
        // この経路の建設を開始するために必要な最小ターン
        val buildableMinTurn =
            if (buildableMinMoney <= money) {
                0
            } else if (moneyDelta == 0) {
                -1
            } else {
                (buildableMinMoney - money + moneyDelta - 1) / moneyDelta
            }
        // 建てられるようになったら建てる、をした場合の最終ターンまでに出る利益、建てられない場合は0
        val benefitToLastTurn =
            if (remainingTurn <= (buildTurn + buildableMinTurn)) {
                0
            } else if (buildableMinTurn == -1) {
                0
            } else {
                max(0, (remainingTurn - buildTurn - buildableMinTurn) * benefitPerTurn - (100 * (buildTurn - 2) + 5000))
            }

        result.add(CalcResult(e.index, path, buildTurn, benefitPerTurn, buildableMinMoney, buildableMinTurn, benefitToLastTurn))
    }
    return result
}

// 初期解を生成する
fun calculatePathAndBenefit(
    M: Int, N: Int,
    commuteInfoList: List<CommuteInfo>,
    T: Int, money: Int,
    coordInfo: Array<Array<MutableList<Pair<Int, Coord>>>>,
): Array<CalcResult> {

    val result = Array(M) { CalcResult() }

    for (i in 0 until M) {
        // 幅優先探索で最短経路を計算
        val dist = Array(N) { IntArray(N) { -1 } }
        val before = Array(N) { Array(N) { Coord(-1, -1) } }
        val queue = ArrayDeque<Coord>()

        val start = commuteInfoList[i].from
        val end = commuteInfoList[i].to

        queue.add(start)
        dist[start.x][start.y] = 0
        while (queue.isNotEmpty()) {
            val v = queue.removeFirst()
            if (v.equals(end)) {
                break
            }
            for (d in delta) {
                val dx = v.x + d.x
                val dy = v.y + d.y
                if (dx in 0 until N && dy in 0 until N) {
                    if (dist[dx][dy] == -1) {
                        dist[dx][dy] = dist[v.x][v.y] + 1
                        before[dx][dy] = v
                        queue.add(Coord(dx, dy))
                    }
                }
            }
        }

        // 経路復元
        val path = mutableListOf<Coord>()
        var c = end
        while (c != start) {
            path.add(c)
            c = before[c.x][c.y]
        }
        path.add(start)
        path.reverse()

        // 1ターンあたりの利益
        val benefitPerTurn = abs(start.x - end.x) + abs(start.y - end.y)
        // 建築に必要なターン
        val buildTurn = path.size
        // この経路の建設コスト
        val buildableMinMoney = 100 * (buildTurn - 2) + 10000
        // 最終ターンまでに出る利益、建てられない場合は0
        val benefitToLastTurn =
            if(money < buildableMinMoney){
                0
            }else{
                (T - buildTurn) * benefitPerTurn - buildableMinMoney
            }
        // 新たに範囲に入るindex
        val buildableOther = mutableListOf<BuildableOtherInfo>()

        for(s in listOf(path.first(), path.last())){
            for(j in -2 until 3) {
                for (k in -2 until 3) {
                    if (abs(j) + abs(k) <= 2) {
                        val x = s.x + j
                        val y = s.y + k
                        if (x in 0 until N && y in 0 until N) {
                            for (cc in coordInfo[x][y]) {
                                val (index, other) = cc
                                if (i != index) {
                                    buildableOther.add(BuildableOtherInfo(index, other))
                                }
                            }
                        }
                    }
                }
            }
        }


        result[i] = CalcResult(i, path, buildTurn, benefitPerTurn, buildableMinMoney, 0, benefitToLastTurn, buildableOther)
    }
    return result
}

fun convertPathToString(path: List<Coord>): List<String> {
    val result = mutableListOf<String>()

    for (i in path.indices) {
        if (i == 0) {
            result.add("0 ${path[i].x} ${path[i].y}")
            continue
        }
        if (i == path.lastIndex) {
            result.add("0 ${path[i].x} ${path[i].y}")
            continue
        }

        val from = path[i - 1]
        val now = path[i]
        val to = path[i + 1]

        if (abs(now.y - from.y) == 1 && abs(to.y - now.y) == 1) {
            result.add("1 ${now.x} ${now.y}")
        } else if (abs(now.x - from.x) == 1 && abs(to.x - now.x) == 1) {
            result.add("2 ${now.x} ${now.y}")
        } else if (now.y - from.y == 1 && to.x - now.x == 1) {
            result.add("3 ${now.x} ${now.y}")
        } else if (now.x - from.x == -1 && to.y - now.y == -1) {
            result.add("3 ${now.x} ${now.y}")
        } else if (now.y - from.y == 1 && to.x - now.x == -1) {
            result.add("4 ${now.x} ${now.y}")
        } else if (now.x - from.x == 1 && to.y - now.y == -1) {
            result.add("4 ${now.x} ${now.y}")
        } else if (now.x - from.x == 1 && to.y - now.y == 1) {
            result.add("5 ${now.x} ${now.y}")
        } else if (now.y - from.y == -1 && to.x - now.x == -1) {
            result.add("5 ${now.x} ${now.y}")
        } else if (now.x - from.x == -1 && to.y - now.y == 1) {
            result.add("6 ${now.x} ${now.y}")
        } else if (now.y - from.y == -1 && to.x - now.x == 1) {
            result.add("6 ${now.x} ${now.y}")
        }
    }
    return result
}

fun solveLocal() {
    val resourcePath = Paths.get("ahc043", "src", "main", "resources")
    val inDir = Paths.get(resourcePath.toString(), "in").toFile()
    val outDir = Paths.get(resourcePath.toString(), "out").toFile()
    if (!outDir.exists()) {
        outDir.mkdirs()
    }

    val resultFile = Paths.get(resourcePath.toString(), "result.csv").toFile()
    val resultFileWriter = FileWriter(resultFile, false)

    resultFileWriter.write("File, Score\n")
    resultFileWriter.flush()

    if (inDir.listFiles() != null) {
        for (inFile in inDir.listFiles()!!.sortedBy { it.name }) {
            val fileName = inFile.name
            val outFile = File(Paths.get(outDir.toString(), fileName).toString())
            if (!outFile.exists()) {
                outFile.createNewFile()
            }
            System.setIn(FileInputStream(inFile))
            System.setOut(PrintStream(outFile))
            val startTime = System.currentTimeMillis()
            solve()
            val endTime = System.currentTimeMillis()
            PrintStream(FileOutputStream(FileDescriptor.out)).println("solve end $fileName ${endTime - startTime}ms")
        }

        for (inFile in inDir.listFiles()!!.sortedBy { it.name }) {
            val fileName = inFile.name
            val outFile = File(Paths.get(outDir.toString(), fileName).toString())

            val pb = ProcessBuilder("cmd", "/c", ".\\vis.exe", ".\\in\\${inFile.name}", ".\\out\\${outFile.name}")
            pb.directory(resourcePath.toFile())
            pb.redirectErrorStream(true)
            val process = pb.start()
            process.waitFor()

            val br = BufferedReader(InputStreamReader(process.inputStream))
            val scoreString = br.readLine()
            br.close()

            PrintStream(FileOutputStream(FileDescriptor.out)).println(scoreString)
            val score = scoreString.split(" ")[2].toInt()
            resultFileWriter.write("$fileName, $score\n")
            resultFileWriter.flush()
        }
    }
}

fun main(args: Array<String>) {
    val env = if (args.isNotEmpty() && args[0] == "local") {
        Env.Local
    } else {
        Env.Prod
    }

    if (env == Env.Local) {
        solveLocal()
    } else {
        solve()
    }
}