Стрічка#73

Стрічка (Editorial)

Вирізана стрічка — це два сусідні сантиметри різних кольорів, тобто підрядок RB або BR. Вирізані шматки не можуть перекриватися, тому задача зводиться до пошуку найбільшої кількості неперетинних сусідніх пар різного кольору.

Тут працює жадібний прохід зліва направо. Стоячи на позиції , дивимось на пару :

  • якщо кольори різні — вирізаємо цю пару, збільшуємо відповідь і переходимо на позицію i + 2;

  • якщо однакові — вирізати нічого, переходимо на i + 1.

Чому жадібність коректна? Якщо пара (i, i+1) різнокольорова, то брати її ніколи не гірше: будь-який інший розв'язок, що використовує позицію або i+1, задіює щонайбільше одну пару з цих двох позицій, тож обмінявши її на нашу, ми не погіршимо відповідь.

Складність — , чого достатньо при |s| \le 10^5.