AtCoder ABC139 D - ModSum (Go) - あるエンジニアのAtCoder奮闘記

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)
}

結論から記すと、 $i\lt N$ のとき $P_i=i+1$ 、 $P_N=1$ とおくことで $\sum^N_1M_i=1+2+\ldots+(N-1)+0=N(N-1)/2$ となり、これが最大値です。

各 $M_i$ を最大化することを考えると、 $M_i=i$ とおくのが直感的によさそうに思えます。ただし $M_N$ に限っては $M_N\lt N$ であることが推察できるのでとりあえず $P_N=1,M_N=0$ とおきます。実はこれだけで上記の解になるわけですが、この道筋では最大値であることを証明するのは困難だと思います。