Go言語で挑む競プロ #14
前回はこちらから。
またまた、蟻本に載ってるアルゴリズムで解くことができるAtcoderの問題を解いていこうと思う。
前々回に引き続き、貪欲法で解くことができる問題を選択してみた。
さぁ解いていこうか。
ABC091Cの問題
問題文
二次元平面に,赤い点と青い点が N 個ずつあります。
i 個目の赤い点の座標は (ai,bi) で,i 個目の青い点の座標は (ci,di) です。
赤い点と青い点は,赤い点の x 座標が青い点の x 座標より小さく, また赤い点の y 座標も青い点の y 座標より小さいとき,仲良しペアになれます。
あなたは最大で何個の仲良しペアを作ることができますか?
ただし,1 つの点が複数のペアに所属することはできません。
制約
- 入力は全て整数
- 1≤N≤100
- 0≤ai,bi,ci,di<2N
- a1,a2,...,aN,c1,c2,...,cN はすべて異なる
- b1,b2,...,bN,d1,d2,...,dN はすべて異なる
アルゴリズム
明らかに貪欲法を用いることでうまく解くことができそうな問題だね。
青い点とその点に対してギリギリ条件を満たす赤い点を組にしていけば最も数多くの組が作れるかな。
というわけで、ざっくりとしたアルゴリズムはこんな感じ。
1. もっとも外側に存在する青い点を選択する
2. 選択した青い点に対してギリギリ条件を満たす赤い点を選択する
3. その二つの点を組にする
4. 組にすることが可能な点が残ってる限り、手順1に戻る
5. 作成できた組の数を解答とする
手順2の赤い点を選択する基準は、どうしようか。
方法としては、ある青い点の内側に存在する最もx座標またはy座標が大きい点を選択し続ければよい。この際に、手順1で選択する青い点の選択基準をx座標にするならば赤い点はy座標を、y座標とするならば、赤い点はx座標を選択基準にする必要がある。
組にする点の選択基準
青い点:x座標が最も大きい ⇒ 赤い点:y座標が最も大きい
青い点:y座標が最も大きい ⇒ 赤い点:x座標が最も大きい
なので、実際にコードに落とすためのアルゴリズムをまとめると以下の手順になるかな。
1. 青い点をx座標の降順にソートする
2. 先頭の青い点(x座標が最も大きい点)を選択する
3. 選択した青い点の内側に存在し、最もy座標が大きい赤い点を選択する
4. 選択した点を組として数をカウントし、使用した赤い点を削除する
5. 次の青い点が存在するならば、青い点の先頭を次の点に変更し、手順2へ
6. 組の数を解答とする
まぁこんなところかな。あとは、入出力の処理を追加したら完成~。
解答
最終的には、以下のようなコードに。
package main
import (
"bufio"
"fmt"
"os"
"sort"
"strconv"
)
type Point struct {
x int
y int
}
type Points []Point
func (l Points) Len() int {
return len(l)
}
func (l Points) Less(i, j int) bool {
return l[i].x < l[j].x
}
func (l Points) Swap(i, j int) {
l[i], l[j] = l[j], l[i]
}
func main() {
s := wordScanner()
var n int
scanInts(s, &n)
reds := make(Points, n)
for i := range reds {
scanInts(s, &reds[i].x, &reds[i].y)
}
blues := make(Points, n)
for i := range blues {
scanInts(s, &blues[i].x, &blues[i].y)
}
sort.Sort(reds)
sort.Sort(blues)
c := 0
for _, b := range blues {
i := -1
for j, r := range reds {
if isInner(r, b) {
if i == -1 || reds[i].y < reds[j].y {
i = j
}
}
}
if i != -1 {
c++
reds = append(reds[:i], reds[i+1:]...)
}
}
fmt.Println(c)
}
func isInner(inner, outer Point) bool {
return outer.x > inner.x && outer.y > inner.y
}
func wordScanner() *bufio.Scanner {
s := bufio.NewScanner(os.Stdin)
s.Split(bufio.ScanWords)
return s
}
func scanInts(s *bufio.Scanner, vals ...*int) {
for i := range vals {
s.Scan()
n, _ := strconv.Atoi(s.Text())
*vals[i] = n
}
}
実は最初、原点に近い順に青い点と赤い点を組にしていこうとして、うまく解答を作れずに苦戦してしまった...
何とか、今回も解くことができて一安心。
貪欲法は、考え方は単純だけどもどういった方面から最も条件に厳しいものを選択していくと効率的かに気づくのが難しいなぁって印象。
まだまだ、練習不足感が否めないね。
まぁ、うまくいかないのにめげずに、次回も頑張っていこう。
この記事が気に入ったらサポートをしてみませんか?