irisruneです。暑さも多少和らいで雨も収まり過ごしやすくなったように思います。
問題
理論立てて考えないと、あまりに単純な解法すぎて戸惑うかもしれません。
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 main() { sc = bufio.NewScanner(os.Stdin) sc.Split(bufio.ScanWords) n := nextInt() fmt.Println((n * (n - 1)) / 2) }
結論から記すと、のとき
、
とおくことで
となり、これが最大値です。
各を最大化することを考えると、
とおくのが直感的によさそうに思えます。ただし
に限っては
であることが推察できるのでとりあえず
とおきます。実はこれだけで上記の解になるわけですが、この道筋では最大値であることを証明するのは困難だと思います。
証明は公式解説にもある通りですが、まずに対して
であることから解の上界が求められ、それが上記の解と一致するため最大値であることが示せます。
雑記
- 今週の予定は水曜にE問題、金曜に過去問(F問題が解けなければ)の予定です。