Go言語で挑む競プロ #12

前回はこちらから。

noteには書き切れていないけども、少しづついろんな問題を解いている。その中で、いろんなアルゴリズムや考え方に触れているけども、ちゃんと吸収できているのかな？
解いていて楽しかったりするので、あまり考えなくてもよいのかもしれないけど、力がついていってくれているとうれしいな。

まぁ考えていても仕方ない気もするし、とにかく今日も解いていこうか。

ABC005Cの問題

問題文
高橋君は、たこ焼きをどの順番で売るか悩んでいました。
というのも、作り置きされたたこ焼きは美味しくないとわかっているので、高橋君はそのようなたこ焼きを売りたくないのですが、できたてばかり売ってしまうと売れるたこ焼きの数が減ってしまいます。
また、お客さんを待たせてばかりだと、次第にお客さんが離れてしまうだろうと高橋君は考えています。
そこで、彼は T 秒以内に作成されたたこ焼きを売り続けることで、お客さんを捌ききれるかどうかを調べることにしました。
たこ焼きは A1、A2、…、AN 秒後に焼きあがります。
お客さんは B1、B2、…、BM 秒後にやってきます。
1 人のお客さんに対して、たこ焼きを 1 つ売るとします。
すべてのお客さんにたこ焼きを売れるならyes、売れないならnoを出力して下さい。

アルゴリズム

まずは、ざっくりとしたアルゴリズムを考えてみよう。実際に売るか売れないかを判定する場合、以下の手順に従えば判定できるはず。

1. お客さんの人数よりたこ焼きが少なければその時点で「売れない」とする
2. お客さんが来る
3. お客さんが来た時刻かそれ以前に完成した最も古いたこ焼きを売る
4. 条件に合致したたこ焼きがない場合、「売れない」とする
5. お客さんがまだいるなら手順2へ戻る
6. すべてのお客さんに売れたら「売れる」とする

今回の問題は貪欲法を用いて、お客さんに提供できるギリギリのたこ焼き、すなわち、お客さんが来店したタイミングからT秒以内にできた最も古いたこ焼きを売り続ければよいことになる。
この手順に従って売った場合、すべてのお客さんに売れたら「売れた」と判定することができる。

このざっくりとしたアルゴリズムをコードに落とせるレベルまで詳細化。こんな感じになる。添字を変更する処理ばっかりで分かりづらい...

1. N < Mで「no」を解答とする
2. i = 1、k = 0とする
3. j = 1とする
4. j番目のたこ焼きの焼き上がり時刻が、i番目のお客さんの来店時刻のT秒前以内の場合、手順7へ
5. j が Nと等しい場合、「no」を解答とする
6. j = j + 1とする
7. i がMと等しい場合、「yes」を解答とする
8. k = k + j、i = i + 1とし、手順3へ

よくわからなくなっているけども、最初のアルゴリズムをそのまま実装した形になっている。
これを実際にコードに落とすとこんな感じ。

if n < m {
    fmt.Println("no")
    return
}

for _, b := range bl { // お客さんが来店
    for j, a := range al { // たこ焼きの焼き上がり時刻を取り出す
        if b-t <= a && a <= b { // 来店時刻-T秒前 以内にできたたこ焼きか
	    al = al[j+1:]
	    break
	}
        // 全たこ焼きを検証したか
        if j == len(al)-1 {
	    fmt.Println("no")
	    return
        }
    }
}
fmt.Println("yes")

あとは、入力処理をつけたら完成！

解答

最終的には以下のコードに。

package main

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

func main() {
    s := bufio.NewScanner(os.Stdin)
    s.Split(bufio.ScanWords)

    var t, n, m int

    scanInts(s, &t, &n)
    al := make([]int, n)
    for i := 0; i < n; i++ {
    	scanInts(s, &al[i])
    }

    scanInts(s, &m)
    bl := make([]int, m)
    for i := 0; i < m; i++ {
    	scanInts(s, &bl[i])
    }

    if n < m {
	fmt.Println("no")
	return
    }

    for _, b := range bl {
	for j, a := range al {
	    if b-t <= a && a <= b {
		al = al[j+1:]
		break
	    }
	    if j == len(al)-1 {
		fmt.Println("no")
		return
            }
    	}
    }
    fmt.Println("yes")
}

func scanInts(s *bufio.Scanner, vals ...*int) {
    for i := range vals {
	s.Scan()
        n, _ := strconv.Atoi(s.Text())
        *vals[i] = n
    }
}

今回は、貪欲法を用いて解く問題だった。選択可能なギリギリを攻めるという単純な戦略にのっとって選択し続けるだけなので、とてもシンプルなアルゴリズムになり考えやすく割とあっさりと解くことができた。
貪欲法は、よく出てくるのでもう少しいろいろな問題で経験したいかな。

さぁ次回も頑張ろうっと。