競技プログラミング用 知識集積所
ABC423C - Lock All Doors
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
ドアを開いたり閉じたりするという問題だが、実は閉じる作業の後に開く作業をする必要はない。
というのは、ドアAを閉めた次にドアBを開くとすれば、先にドアBを開いてからドアAを閉めてもよい。
ドアAを閉めた次にドアAを開くとすれば、その2つは省略してよい。
したがって、最短手順として「必要なだけ開いてから、全てを閉める」の形限定で探してよい貪欲法※が成立する。
というのは、ドアAを閉めた次にドアBを開くとすれば、先にドアBを開いてからドアAを閉めてもよい。
ドアAを閉めた次にドアAを開くとすれば、その2つは省略してよい。
したがって、最短手順として「必要なだけ開いてから、全てを閉める」の形限定で探してよい貪欲法※が成立する。
さて、必要なだけ開くというのは、以下の条件を両方満たす連続区間を全て開くことである。
- もともと空いていたドアを全て区間に含む
- 高橋君の初期位置がその区間内にある
よって、開くドアの最小番号は、「もともと開いていた全てのドアと、高橋君の右にあるドアの中の最小値」である。
また、最大番号は「もともと開いていた全てのドアと、高橋君の左にあるドアの中の最大値」である。
また、最大番号は「もともと開いていた全てのドアと、高橋君の左にあるドアの中の最大値」である。
これらの番号を求め、その区間内の閉まっているドアを全て開け、その後区間内を全部閉めればよい。
