AtCoder ABC 135 C - City Savers (Go)

irisruneです。ABC135参加はしましたが…D問題以降が解けずNoSub撤退をすることになりました。

問題

atcoder.jp

逆から解く必要があるように見えましたが全くそんなことはなかった問題です。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func maxInt(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func minInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n := nextInt()

    aArray := make([]int, n+1)
    for i := 0; i < n+1; i++ {
        aArray[i] = nextInt()
    }
    bArray := make([]int, n+1)
    for i := 0; i < n; i++ {
        bArray[i] = nextInt()
    }
    // bArray[n] = 0

    ans := 0
    for i := n; i > 0; i-- {
        ans += minInt(aArray[i], bArray[i])
        aArray[i] = maxInt(0, aArray[i]-bArray[i])
        ans += minInt(aArray[i], bArray[i-1])
        // aArray[i] = maxInt(0, aArray[i] - bArray[i - 1])
        bArray[i-1] = maxInt(0, bArray[i-1]-aArray[i])
    }
    ans += minInt(aArray[0], bArray[0])
    // aArray[0] = maxInt(0, aArray[0] - bArray[0])
    fmt.Println(ans)
}

今回注目したポイントは、番目の街を襲っているモンスターを倒すことができるのは番目の勇者のみという点です。ここから番目の街の順に番目の勇者が全力でモンスターを倒す手順を考えるとこの問題を解くことができます。

以上の解法でも特に問題なく解くことができるのですが、問題の設定条件をよく見ると番目の街を襲っているモンスターを倒すことができるのも番目の勇者のみのため、実際には番目の街の順に考えるだけで解くことができます。

雑記

• 4完（1000点）以上の見込みがなければ撤退という方針で臨んだわけですが、D問題の解法が思いつかなかったのでE問題に取り組んだら更なる絶望に叩き落された気分でした。
  • サンプルケースが弱かったらE問題を提出してたかもしれないですね、それでも緑色まで落ちることはなかったでしょうが…
  • 3完（600点）で水パフォがあり得るのは久々だったのではないでしょうか。