AtCoder ABC 127 D - Integer Cards - あるエンジニアのAtCoder奮闘記

irisruneです。今日は試しに2記事公開してみました。

アルゴリズムの発想と計算量の抑え方の両面が重要となる問題だと思いました。半分嘘解法です。

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 operation struct {
    b int
    c int
}

type ope []operation

func (o ope) Len() int {
    return len(o)
}

func (o ope) Swap(i, j int) {
    o[i], o[j] = o[j], o[i]
}

func (o ope) Less(i, j int) bool {
    return o[i].c < o[j].c
}

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

    aArray := make([]int, n)
    for i := 0; i < n; i++ {
        aArray[i] = nextInt()
    }

    var o ope = make([]operation, m)
    for j := 0; j < m; j++ {
        o[j].b, o[j].c = nextInt(), nextInt()
    }
    sort.Sort(sort.Reverse(o))

    cnt := 0
    for j := 0; j < m && cnt < n; j++ {
        for k := 0; k < o[j].b && cnt < n; k++ {
            aArray = append(aArray, o[j].c)
            cnt++
        }
    }
    sort.Sort(sort.Reverse(sort.IntSlice(aArray)))

    ans := 0
    for i := 0; i < n; i++ {
        ans += aArray[i]
    }

    fmt.Println(ans)
}

ベースとなる考え方は、元々ある $N$ 枚のカードと $j=1,2,\dots,M$ に対応する整数 $C_j$ の書かれた $B_j$ 枚のカードを合わせた中から、大きい順に $N$ 枚取り出した整数の合計を求めるというものです。ただし制約条件が $1\leq M\leq 10^5,1\leq B_j\leq N\leq 10^5$ であるため、最終的なカードの枚数は最大で $10^{10}$ 枚を上回ります。つまり安直にカードの集合を足し合わせてソートするとTLEしてしまいます。