🤖

ABC 362 C - Sum = 0 のメモ

2024/07/15に公開

仮に2つ目の条件がなければ、全部 $L_i$ を選ぶとかでいいんだけどなと思いました。実際にそうすると、その合計値がたまたま0になるならそれが答えになりますが、多くのケースだと合計値は負の数か正の数になるでしょう。そしたら、それを0にできるように調整していけばいいのではと気づきました。

この場合、各 $X_i$ について最小値を選んでいるので、合計値を増やす方向の調整しかできません。なので、この時点で合計値が正の数ならもう答えは存在しません。負の数であれば、答えとなる組み合わせが存在する可能性があります。各 $X_i$ について一旦 $R_i$ にしてみることを考えます。そうした時に合計値が0になったらそれが答えになります。正の数になれば増やしすぎということになりますが、増えすぎた分を減らせば0にできるので、そのように再調整した時の値が答えです。全ての $X_i$ を $R_i$ にしても合計値が負の数のままなら答えは存在しません。

import java.io.PrintWriter

fun main() {
    val n = readln().toInt()
    val lr = List(n) {
        val (l, r) = readln().split(" ").map { it.toLong() }
        l to r
    }

    val result = solve(lr)

    if(result.isEmpty()) {
        println("No")
        return
    }

    println("Yes")

    val out = PrintWriter(System.out)
    for(i in result.indices) {
        out.print(result[i])
        if(i == n - 1) {
            out.println()
        } else {
            out.print(' ')
        }
    }

    out.flush()
}

fun solve(lr: List<Pair<Long, Long>>): LongArray {
    val result = lr.map { it.first }.toLongArray()
    var current = result.sum()

    if(current > 0) {
        return LongArray(0)
    }

    val rests = lr.map { it.second - it.first }

    for(i in lr.indices) {
        val (l, r) = lr[i]
        val rest = rests[i]

        current += rest
        if(current == 0L) {
            result[i] = r
            return result
        }
        if(current > 0) {
            result[i] = r - current
            return result
        }

        result[i] = r
    }

    return LongArray(0)
}

Discussion