AtCoder ABC140 C - Maximal Value (Go) - あるエンジニアのAtCoder奮闘記

irisruneです。台風の影響により、今週は火・水・金の投稿となります。

問題

https://atcoder.jp/contests/abc140/tasks/abc140_c

$B_i$ から $A_i$ を逆算するにはどうすればいいかという問題です。

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

    ans := 0
    bPrev := -1
    for i := 0; i < n-1; i++ {
        b := nextInt()
        switch {
        case i == 0:
            ans += b
        default:
            ans += minInt(b, bPrev)
        }
        bPrev = b
    }

    fmt.Println(ans + bPrev)
}

$A_i$ から $B_i$ を求める方法として、問題文で $B_i\geq\max(A_i,A_{i+1})$ が示されています。逆に $B_i$ から $A_i$ を求める方法を考えると、 $A_i\leq\min(B_{i-1},B_i)$ となることがわかります。

ここから不等号を等号に置き換えるだけで $A_i$ の最大値を求められますが、 $A_i(1\leq i\leq N)$ に対して $B_i(1\leq i\leq N-1)$ であるため、 $A_0,A_N$ については求め方が異なることに注意が必要です。具体的には $A_0\leq B_1,A_N\leq B_n$ と置き換える必要があります。