あるエンジニアのAtCoder奮闘記

東京都港区にあるアミフィアブル株式会社のエンジニアが、AtCoderで解いた問題について振り返ったりしていく会社公認のブログです。

AtCoder E - Gluttony 解説AC (Go)

irisruneです。AtCoderの数学問題は注目を集めやすい印象です。

問題

atcoder.jp

大きなポイントが2つあり、どちらが欠けても上手くいかない問題です。

package main

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

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

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.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n, k := nextInt(), nextInt()
    aArray, fArray := make([]int, n), make([]int, n)
    for i := range aArray {
        aArray[i] = nextInt()
    }
    sort.Sort(sort.IntSlice(aArray))
    for i := range fArray {
        fArray[i] = nextInt()
    }
    sort.Sort(sort.Reverse(sort.IntSlice(fArray)))

    min, max := 0, fArray[0]*aArray[n-1]
    for min < max {
        x := (min + max) / 2
        kRemain := k
        for i := range aArray {
            require := aArray[i] - (x / fArray[i])
            if require > 0 {
                kRemain -= require
            }
        }
        switch {
        case kRemain >= 0:
            max = x
        case kRemain < 0:
            min = x + 1
        }
    }
    fmt.Println(min)
}

まずは、どのようにメンバーを割り当てるかについて考える必要があります。直感的にはメンバーの消化コストを昇順に、料理の食べにくさを降順に並べてそれぞれの順番通りに対応させればよさそうで、実際そのような割り当てが最適となります。詳しい証明は公式解説にありますが、任意の割り当て方から損のないように最適な割り当て方に変換することが可能なためです。

しかし、最適な修行の割り振り方を求めることは簡単ではありません。直感的には最も完食に時間のかかるメンバーについて修行を行うことを繰り返せばコンテストの成績を最適にすることができそうですが、この方法は少なく見積もっても修行回数分の計算量がかかってしまいます。これは例えヒープを用いたとしても覆らないため、最適解を直接求めることはできなさそうです。

そこで、成績をx秒以内にするために必要な修行回数を求めることを考えてみます。すると、修行回数は計算量O(N)で求めることができ、Kと比較することで成績をx秒以内にすることができるか判定することができます。つまり、下限値を0、上限値を適当な値(A_i,F_iそれぞれの最大値の積がよさそうです)とおいて二分探索を行うことで、達成できる成績の最適値が求められます。このとき全体の計算量はO(N\log(\max A_iF_i))となり十分間に合います。

雑記

  • コンテスト本番では成績から修行回数を求め二分探索をするという発想に至らず、解くことができませんでした。
    • Difficultyはそれほど高くなかったので精進不足なのだと思います。
    • 解説PDFではメンバーの割り当て9割、二分探索1割といった配分だったので驚きました。