paizaの練習問題を解く最短の区間 Go編

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

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

今回の問題は以下です。

累積和の計算 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】

実装

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

package main
import "fmt"
func main(){
    var n, m int
    fmt.Scan(&n, &m)
    x := 0
    a := make([]int, n)
    s := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scan(&a[i])
        x += a[i]
        s[i] = x
    }
    if x < m {
        fmt.Println(-1)
        return
    }
    z := 100000
    for l := 0; l < n; l++ {
        for r := n - 1; r >= 0; r-- {
            sum := s[r] - s[l] + a[l]
            if sum >= m && z > r - l + 1 {
                z = r - l + 1
            }
        }
    }
    fmt.Println(z)
}

ですが、これだと計算量が多く実行時間エラーになってしまいました。

ということで、AIと壁打ちして「しゃくとり法」で実装しました。

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])
    }
    
    z := n + 1
    sum := 0
    l := 0
    for r := 0; r < n; r++ {
        sum += a[r]
        
        for sum >= m {
            c := r - l + 1
            if z > c {
                z = c
            }
            sum -= a[l]
            l++
        }
    }
    if z > n {
        fmt.Println(-1)
    } else {
        fmt.Println(z)
    }
}

これで計算量もぐっと減ってきれいに実装できました。

ただ、完全にしゃくとり法を理解できたというわけじゃないので、そこだけが少し心残りです。。

ではまた👍

実装#

実装