ABC174D
from ABC174
ABC174D
D - Alter Altar ]
WRが含まれないようにしたいということは要するにR*W*にしたいということ
右端と左端から見ていって、ルールを破ってる石を交換すれば、ルールを守ってる範囲が単調に増加する
色替えは必要ない
色替えが有効である場合、その対象石の交換でも同様に有効だから(雑)
少しまともな説明
与えられた列を条件を満たすように並び替えたものを考える
現在の列のその列との食い違いの個数をコストと呼ぶことにする
上記の交換操作はコストを常に2減らす
色変えはコストを1減らし、赤城の境界を1つ動かす
境界が動いたことによって所属の変わった石が正しい色であればコストがさらに1下がるが、正しくない場合逆に1増える
よって色変えはコストを最大値2減らす。これは交換と同程度または劣った効率である。
pythondef solve(N, CS):
left = 0
right = N - 1
R = ord("R")
W = ord("W")
ret = 0
while left < right:
if CS[left] == R:
left += 1
continue
if CS[right] == W:
right -= 1
continue
# swap
left += 1
right -= 1
ret += 1
return retRelated Pages
- →atcoder×abc168×abc169×abc170×abc171×abc172×abc173×ABC174×abc175×abc176×abc177×abc178×abc179×abc180×abc181×abc182×abc183→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]