AtCoderBeginnerContest423 C問題300点 「Lock All Doors」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
気持ち
解法
ドアをすべて閉めるために、最小の開閉回数を求めます。
性質を列挙することで問題の解き方が見えてきそうであるため、小さなサンプルケースを色々と作ってみます。 高橋くんの座標を $ R とします。
$ R より左側のドアについて、もっとも左側にある空いているドアを $ sとする
このとき、 $ s より左にある最初から閉まっているドアは閉めているままでいい
空ける必要がないため
$ sに移動するまでに存在する「しまっているドア」については、一度開けてから締める必要がある
https://gyazo.com/39b51c0c7ead88b4f732b7f83a0f0586
開始時点で開いているドアは絶対に閉める必要があり、かつ１度閉めるだけでよい（開けしめを繰り返さない）
ドアについて、移動しないといけない範囲のドアをすべて開けてから、その後左もしくは右から一気に閉める、が最適解になる
https://gyazo.com/4f2ae35afbd9008d03ac568148c68719
よって、これをシミュレートするようなコードを書けばいいです。
計算量
$ O(N)
新たな学び
反省点
競プロ久しぶりなので、インデックスの取り回しがむずかしい...
コード
主人公をまずは左に向かわせる。その後、右に向かわせる。 というコードを書いています
念の為、ドアとプレイヤー座標を Reverse して、「先に右に向かわせる」というチェックもしていますが、多分いらないです
code: cpp
func reverse(a []int) []int {
n := len(a)
b := make([]int, n)
for i := 0; i < n; i++ {
}
return b
}
func reverseDoor(a int, N int) int {
return N - a
}
func solve() {
N, R := mio.NextInt(), mio.NextInt()
// ドア (0 = open)
L := make([]int, N)
for i := 0; i < N; i++ {
}
L2 := reverse(L)
R2 := reverseDoor(R, N)
f := func(keys []int, pr int) int {
cost := 0
// 空いている最も左のドア
ld := -1
for i := pr - 1; i >= 0; i-- {
ld = i
}
}
if ld != -1 {
for i := pr - 1; i >= ld; i-- {
cost++
cost++
}
}
}
rd := -1
for i := pr; i < N; i++ {
rd = i
}
}
if rd != -1 {
for i := pr; i <= rd; i++ {
cost++
cost++
}
}
}
return cost
}
ans := f(L, R)
ans2 := f(L2, R2)
if ans2 < ans {
ans = ans2
}
mio.PrintLn(ans)
}