AtCoder ARC001 B - リモコン を解きました。
簡単なんだけど、面白い問題だと思いました。
問題
高橋君は、エアコンの設定温度を変更しようとしています。現在の設定温度は A 度ですが、これを B 度に設定したいと思っています。
エアコンのリモコンは 1 回ボタンを押すことで、
* 1 度設定温度を下げる、もしくは上げる
* 5 度設定温度を下げる、もしくは上げる
* 10 度設定温度を下げる、もしくは上げる
の、 6 種類の操作のいずれか 1 つを実行することが出来ます。
高橋君が設定温度を A 度から B 度に変更するために押すボタンの最小回数を求めなさい。
( https://atcoder.jp/contests/arc001/tasks/arc001_2 より引用)
制約
$0 \le A \le 40$
$0 \le B \le 40$
考え方
10度 → 5度 → 1度 の順に貪欲に押していけばいいだろ〜と思って実装したら、サンプルケース2で無事死亡。
DPかな？という考えが一瞬頭をよぎったけど、各温度の値が上下1度、5度、10度ずつの値と結ばれたグラフと考えれば、制約も小さいし幅優先探索でいけそうだな、と思って実装したら AC でした。
提出コード
次のようなコードを書きました（抜粋）。全体はこちら
注意すべき点としては、A=9, B=0 のように、温度を一旦負の数にしてから戻すのが最適、というパターンも考えられるので、探索中に多少負の温度になっても大丈夫なように、全体を+10ほどシフトして計算しています。（差分の絶対値にしてから計算すれば、そのような工夫は不要）
func main() {
defer stdout.Flush()
a := readInt() + 10
b := readInt() + 10
d := make([]int, 100)
for i := range d {
d[i] = 1000000
}
q := make([]int, 0)
push := func(v int) {
q = append(q, v)
}
pop := func() int {
v := q[0]
q = q[1:]
return v
}
d[a] = 0
push(a)
for len(q) != 0 {
t := pop()
if t == b {
println(d[b])
return
}
for _, dt := range []int{-10, -5, -1, 1, 5, 10} {
nt := t + dt
if nt < 0 || len(d) <= nt {
continue
}
if d[nt] <= d[t]+1 {
continue
}
d[nt] = d[t] + 1
push(nt)
}
}
}
追記
10未満の距離について予め表を持っておくことで計算を簡略化する方法を教えていただきました。これなら制約が大きくても大丈夫そう。
func main() {
defer stdout.Flush()
a := readInt()
b := readInt()
d := b - a
if d < 0 {
d = -d
}
println(d/10 + []int{0, 1, 2, 3, 2, 1, 2, 3, 3, 2}[d%10])
}
まず絶対誤差 d を 10 で割って、何回10を押せばよいかをまずカウントします。
次に、残りの差分を飛ぶためにあと何回押せばよいかを、予め作っておいた表から取り出して足します。
$0,1,3,2,1,2,3,3,2$ という数字の並びは、10未満の差分へ飛ぶときに何回ボタンを押すか、という表です。
差分が0度なら0回ボタンを押せばいい、差分が1度なら1回ボタンをおせばいい、... というふうに考えて生成します。1回のボタン操作で飛ぶことができる差分である1度と5度と10度の値は1になり、その他の差分の値はそれらからの距離で最も小さい値になります。
10度差分のための1は d/10 の側でカウントされるので、この表には不要であり、↑には登場していない、というのが少しわかりにくいポイントでしょうか。