AtCoder ABC 131 D - Megalomania (Go)

irisruneです。新形式になって以降C,D問題が簡単になったとは思っていましたが、今回はかなり極端だった気がします。

問題

atcoder.jp

解答者にとってはどちらかと言えばMegalomaniaよりParanoiaみたいな問題です。

package main

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

var sc *bufio.Scanner

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

type task struct {
    a int
    b int
}

type tasks []task

func (t tasks) Len() int {
    return len(t)
}

func (t tasks) Swap(i, j int) {
    t[i], t[j] = t[j], t[i]
}

func (t tasks) Less(i, j int) bool {
    switch {
    case t[i].b != t[j].b:
        return t[i].b < t[j].b
    default:
        return t[i].a < t[j].a
    }
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    n := nextInt()

    var tasks tasks = make([]task, n)
    for i := 0; i < n; i++ {
        tasks[i].a, tasks[i].b = nextInt(), nextInt()
    }
    sort.Sort(tasks)

    time := 0
    for i := 0; i < n; i++ {
        time += tasks[i].a
        if time > tasks[i].b {
            fmt.Println("No")
            return
        }
    }
    fmt.Println("Yes")
}

方針は締め切りが早い仕事から順番に始めて、締め切りを過ぎる仕事が発生したら打ち切るだけです。

あまりにも安直すぎて裏がありそうに思えますがそんなことはないです。これを証明するのはやや難しいですが、証明しなくても正解できるのが競技プログラミングの特徴ですね。

そんなわけでアルゴリズム面ではあまりに解説することがないのですが、実装面についてはGo特有のソート実装の面倒さがネックになっていますね。Go1.8以降であればインタフェースの実装（Len,Swap,Lessメソッドの実装）を行わなくても構造体のソートが実装できるようになっているので、言語アップデートに期待したいところです。

雑記

• 改めて思うに、Go言語は高級言語とは言い難いけど低級言語と言うほどでもない微妙な立場という感じですね。
• 4完で茶パフォとはおそろしい時代になったものですね…
  • まだABCE（あるいはABDE）4完であれば水パフォが保証されていたようです。