あるエンジニアのAtCoder奮闘記

東京都港区にあるアミフィアブル株式会社のエンジニアが、AtCoderで解いた問題について振り返ったりしていく会社公認のブログです。

AtCoder ABC 143 D - Triangles (Go)

irisruneです。コンテストは当日になってうっかり存在を忘れてしまいました。

問題

atcoder.jp

3重ループは通りませんが2重ループなら通る制約設定が重要です。

package main

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

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

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

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n := nextInt()
    lArray := make([]int, n)
    for i := range lArray {
        lArray[i] = nextInt()
    }
    sort.Sort(sort.IntSlice(lArray))

    ans := 0
    for i := 0; i < n-2; i++ {
        for j := i + 1; j < n-1; j++ {
            kLeft := sort.SearchInts(lArray[j+1:], lArray[j]-lArray[i])
            kRight := sort.SearchInts(lArray[j+1:], lArray[j]+lArray[i])
            ans += kRight - kLeft
        }
    }
    fmt.Println(ans)
}

2辺を選んだときに残り1辺の候補数がいくらか確認すればよいですが、愚直に解くと3重ループになってしまい間に合いません。そこで残り1辺の候補数を2分探索で求めるようにすれば、全体の計算量がO(N^2\log N)となり間に合います。

雑記

  • 今週のE問題はグラフ問題なのでできれば解いておきたいと思います。