結果
| 問題 |
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()
}
}