AtCoder ABC085 D - Katana Thrower

AtCoderに取り組んだ際のメモです。
問題ページはこちらです。

Point: 400
Difficulty: 929

考えたこと

・刀を投げることでHを0にできるならそれが最小と思われるので、貪欲に投げてダメージを与えたい
・投げて削り切れないHについては、振った場合に最も大きなダメージを与えられる刀を使って攻撃すればよさそう

方針

・刀をHが0以下になるまで投げてみる（ソートしてダメージの大きいものから投げる）
・全部投げてもHが0以下にならない場合は、振って最強の刀で削る
・"投げた回数 + 振った回数" が解答になる

つまづいたこと 

上記の方針で実装したところ、サンプルは通るものの提出するとWAになりました。

問題点
・すべての刀について、振って与えるダメージ <= 投げて与えるダメージと考えてしまっていた

ある刀を(振って与えるダメージ, 投げて与えるダメージで示すとします。
刀1= (100, 120)、刀2=(1, 80)、刀3=(10, 150)だった場合を考えます。
このような場合は、"刀2を投げて与えるダメージ" < "刀1を振って与えるダメージ"になるため、刀2は投げてはいけないということになります。 

当初の方針を修正するとするならば、以下のようになると思います。
・刀をHが0以下になるまで投げてみる（ソートしてダメージの大きいものから投げる）。ただし、刀を投げて与えるダメージが"振って与えるダメージの最大値より大きい場合に限る。

提出したコード

提出ページ

package main

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

func main() {
	r := bufio.NewReader(os.Stdin)
	var n, h int
	fmt.Fscan(r, &n)
	fmt.Fscan(r, &h)

	as := make([]int, n)
	bs := make([]int, n)
	maxA := 0
	for i := 0; i < n; i++ {
		fmt.Fscan(r, &as[i])
		fmt.Fscan(r, &bs[i])

		// 振って最も大きいダメージを与えられる刀を保持
		maxA = max(maxA, as[i])
	}
	sort.Sort(sort.IntSlice(as))
	sort.Sort(sort.IntSlice(bs))

	ans := 0

	// まずは投げてみる
	for i := n - 1; i >= 0; i-- {
		if bs[i] <= maxA {
			break
		}

		h -= bs[i]
		ans++
		if h <= 0 {
			break
		}
	}

	// 投げて不足する場合は、振って攻撃する
	if h > 0 {
		swingCount := (h + maxA - 1) / maxA
		ans += swingCount
	}

	fmt.Println(ans)
}

// Utility

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

感想など

・制約をよく読んで理解する必要がある（同じ刀で与えるダメージの大小、異なる刀間での与えるダメージの大小）

・最終的に投げることになる刀は、先にすべて投げてしまってよい
当初、振った際に最強のダメージを与える刀については、投げずにとっておく必要があると思い、そのように実装していました。ですが、投げる必要がある場合は結局投げることになるので、全部投げた残りのHについて、振る回数を計算すればいいということに気づきました。
問題文から想像する動作の通りに書こうとすると、少し処理が複雑になります。正解が得るために、必要な処理を適切に書く必要があるということですね。

・刀は何回でも振ることができるので、振って与えるダメージは最大のもののみきにすればいい（刀を振ることができる回数に上限がある場合は、どうすればいいんだろうか）
・刀は1回しか投げることができないので、ダメージの大きい順に投げる必要がある

・解説では全探索しているので復習が必要