C - Slot Strategy 2 (Easy)

[hxrxchang]

https://atcoder.jp/contests/abc320/tasks/abc320_c

問題概要

3個のリールからなるスロットがある。
どの順番でボタンを押してもいいので、3個のリールの文字を揃えるのに最短の時間を求めよ。

解き方

実装が面倒くさいただの全探索。

1. どの順番でボタンを押すかを順列全探索で決める
2. 最初に止めるリールの中で、どの文字に止めるかを全探索で決め、何秒で止められるか求める。
3. 2番目に止めるリールの中で、2で決めた文字を何秒で止められるか求める
4. 3番目に止めるリールの中で、2で決めた文字を何秒で止められるか求める

というのをやればいい。
秒数が経過後のリールの状態を求めるのに、スライスを指定したidxで区切って反転させる splitAndReverse を作ったら便利だった。

func solve() {
	m := getInt()
	ss := [][]string{strToSlice(getStr(), ""), strToSlice(getStr(), ""), strToSlice(getStr(), "")}

	perm := rangeSlice(3)
	ans := BIGGEST
	for {
		for i := 0; i < m; i++ {
			cnt := i
			first := splitAndReverse(ss[perm[0]], i)
			target := first[0]

			second := splitAndReverse(ss[perm[1]], (cnt + 1) % m)
			foundSecond := false
			var j int
			for j = 0; j < m; j++ {
				if second[j] == target {
					cnt += j + 1
					foundSecond = true
					break
				}
			}
			if !foundSecond {
				continue
			}

			third := splitAndReverse(ss[perm[2]], (cnt + 1) % m)
			foundThird := false
			var k int
			for k = 0; k < m; k++ {
				if third[k] == target {
					cnt += k + 1
					foundThird = true
					break
				}
			}
			if !foundThird {
				continue
			}

			ans = min(ans, cnt)
		}
		if !nextPermutation(sort.IntSlice(perm)) {
			break
		}
	}

	if ans == BIGGEST {
		fmt.Println(-1)
	} else {
		fmt.Println(ans)
	}
}

func splitAndReverse[T any](slice []T, index int) []T {
    if index < 0 || index >= len(slice) {
        panic("index out of range")
    }
    front := slice[:index]
    back := slice[index:]

    return append(back, front...)
}

https://atcoder.jp/contests/abc320/submissions/60927898