AtCoder ABC 131 B - Bite Eating (Go) - あるエンジニアのAtCoder奮闘記

irisruneです。ここ最近競技プログラミングに使う言語についてまた悩んでいるところです。

問題

実はD問題より解く時間がかかったので取り上げることにしました。絶対値の差ではなく差の絶対値なので誤読しないようにしましょう。

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
}

const INF = 1000000000

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n, l := nextInt(), nextInt()
    dWhole := 0
    for i := 1; i <= n; i++ {
        dWhole += l + i - 1
    }
    switch {
    case 0 <= -l && -l <= n-1:
        fmt.Println(dWhole)
    case -l < 0:
        fmt.Println(dWhole - l)
    default:
        fmt.Println(dWhole - (l + (n - 1)))
    }
}

$N\leq200$ という条件なので、公式解説のように全部のリンゴの「味」の絶対値を求め、絶対値が最小となるリンゴを除いたものの「味」の総和を求めればよいです。計算量は $O(N)$ なので余裕で間に合います。

ではなぜそうせずに計算量 $O(1)$ となる解き方をしたのかというと、

当初「味」の絶対値の差と誤読していたので、先に「味」の総和を求める必要があると思い込んでいました。
誤読に気付く前後辺りでGoのAbs関数がInt型を引数にも返り値にも取れないことに気付きました。
- 今まで何回かやってるようにInt型のAbs関数を自作すればいいのですが、今回はAbs関数を実装するメリットもあまりなさそうです。
- 別にキャストしてもいいのですが、3回キャストをするのでちょっと記述がごちゃごちゃしてあまり気に入らなかったです。
既に「味」の総和を求めていたので、それを用いて解く手法を考えた結果として計算量 $O(1)$ となりました。

という流れでした。B問題だからこれでも10分くらいで済みましたが踏んだり蹴ったりですね…

ちなみに公式解説で触れられていない事柄として

なお、この値は一意に定まることが証明できます。

と問題文にありますが、

「味」がすべて正の場合あるいはすべて負の場合は、食べるリンゴが異なるなら「味」の総和は異なるため求める値は一意に定まる。
「味」が0となるリンゴがある場合はそのリンゴを食べるのが最適であるため求める値は一意に定まる。

といった風に証明することができます。

雑記

始めに少し触れましたが、競技プログラミングに使う言語の選定に改めて難しさを感じています。
- 例えばC++は、速度とライブラリについては申し分ないものの、記述量や他用途での使用機会に難があるイメージです。
- 一方でPythonは、記述量やライブラリ、他用途での使用機会は申し分ないものの、速度に難がある上にスクリプト言語なのでCE（ペナルティ無し）ではなくRE（ペナルティ有り）を起こすリスクも考えています。
  - CEでなくREになるのはバージョンの差異が原因になることがほとんどですが、それ以外においてもPythonでは再帰などREになるケースが比較的多く感じます。
- 速度と記述の簡易さを両立できる言語としてNimなども考えているのですが、開発中の言語ということでやや難があるという話も聞きます。
言語アップデートで使用感の変わる言語もあると思いますが、いずれにせよ今何の言語を使うかという悩みは尽きませんね…