AtCoder ABC 143 D - Triangles (Go)
irisruneです。コンテストは当日になってうっかり存在を忘れてしまいました。
問題
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分探索で求めるようにすれば、全体の計算量がとなり間に合います。
雑記
- 今週のE問題はグラフ問題なのでできれば解いておきたいと思います。