paizaの練習問題を解く区間への足し算 Go編

こんにちは、ナナオです。

前回に引き続き競プロを実施していきたいと思います。

今回の問題は以下です。

最長の区間 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】

実装

まずは以下のように実装しました。

package main
import "fmt"
func main(){
    var n, m int
    fmt.Scan(&n, &m)
    a := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&a[i])
    }
    s := make([]int, n)
    for i := 0; i < m; i++ {
        var mn, mx, t int
        fmt.Scan(&mn, &mx, &t)
        for k := mn - 1; k < mx; k++ {
            s[k] += 
        }
    }
    for i := 0; i < n; i++ {
        fmt.Println(a[i] + s[i])
    }

この回答でもGoの場合解けるのですが、まぁ実行時間制限ギリギリなので、一応模範解答のように改修しておきましょう。

この実装、よく考えると累積和で解けるんですよね。

つまり、mnとmxは累積和の区間として考えることができるわけです。

実装としては以下の通りです。

package main
import "fmt"
func main(){
    var n, m int
    fmt.Scan(&n, &m)
    a := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&a[i])
    }
    s := make([]int, n)
    for i := 0; i < m; i++ {
        var mn, mx, t int
        fmt.Scan(&mn, &mx, &t)
        s[mn - 1] += t
        if mx < len(s) {
            s[mx] -= t
        }
    }
    x := 0
    for i := 0; i < n; i++ {
        x += s[i]
        fmt.Println(a[i] + x)
    }
}

あーすっきりした。

ではまた👍

実装#

実装