mini notes

競技プログラミングの解法メモを残していきます。

ARC041 C - ウサギ跳び

問題:C - ウサギ跳び

解答:Submission #10535617 - AtCoder Regular Contest 041

解法:左の壁から連続するLと右の壁まで連続するRについては、壁(もしくは先にいるウサギ)に突き当たるまで進ませる。

R...RL...Lになっている並びのウサギを考える。まずはRLの境界のウサギまで、Rのウサギを右に、Lのウサギを左に動かす。そこからどのようにウサギを動かすかだが、RのウサギとLのウサギのいずれか多い向きのウサギをそれ以外のウサギに当たるまで動かすのがよい。例えばRが2匹Lが3匹いれば、Lのウサギを左に動かした方が総移動距離が大きくなる。

なお、実装としては最も左のウサギがLなら位置0にRのウサギを追加し、最も右のウサギがRなら位置L+1にLのウサギを追加することで、全てR...RL...Lの形として処理できる。