Řešení (Zadání úlohy)
Než úlohu začneme řešit, nejdříve si ji trochu zjednodušíme. Zaprvé, o řetězcích budeme jako správní programátoři uvažovat nikoliv jako o posloupnosti znaků a a b, nýbrž jako o posloupnosti nul a jedniček (kde a odpovídá nule a b jedničce). Později uvidíme, proč je to pro nás takto výhodnější. Označme tyto nové řetězce nul a jedniček jako s a t. Během textu budeme běžně používat zavedené značení, že s[i] značí i-tý znak řetězce s.
Zadruhé se zbavíme nutnosti vyrábět z jednoho řetězce nějaký druhý a pořídíme si rozdílový řetězec r: ten bude mít na i-té pozici nulu, pokud se s[i] a t[i] rovnají, jinak tam bude mít jedničku. Určitě platí, že s je už stejné jako t, právě když jsou v r samé nuly. Podíváme se teď, jak naše dvě operace na s mění tento rozdílový řetězec:
- první operace – překlopení znaku (0 → 1, 1 → 0) na nějaké libovolné pozici i: v s se i-tý znak prohodí za opačný. To samé se ale stane v r: pokud se s[i] a t[i] rovnaly, teď už nebudou, a naopak.
- druhá operace – překlopení znaků (0 → 1, 1 → 0) na všech pozicích 1, 2, …, i pro nějaké libovolné i: Pro každé j = 1, 2, …, i bude na s[j] opačný znak než předtím. Stejně tak bude ale na každém r[j] opačný znak než předtím (ze stejného důvodu, jako minule).
Takže operace provedená na s se v r projeví stejně, jako kdybychom tu samou operaci provedli rovnou na r (a naopak, operace provedená na r se stejně tak projeví v s). My tedy vůbec nemusíme pracovat s s a snažit se ho převádět na t. Místo toho můžeme pracovat s r a převádět ho na samé nuly – tehdy už totiž víme, že když na s provedeme ty samé operace, s a t se bude rovnat.
Třetí, poměrně snadné pozorování je, že na pořadí provedených operací nezáleží: hodnota každého políčka záleží jen na tom, kolikrát máme jeho znak podle nějakých operací změnit na opačný (pokud sudě-krát, bude výsledný znak stejný jako na začátku, pokud liše-krát, bude opačný), a tento počet operací se měněním jejich pořadí nemění.
Vyřešit lehkou variantu teď vůbec nebude těžké: zadání slibuje, že si vystačíme pouze s jedním typem operací. My tedy můžeme napsat dvě řešení: jedno, které bude používat pouze první operaci, a druhé, které bude používat pouze tu druhou, a pak si z nich pro každý vstup vybrat to, které dává lepší výsledek. Řešení, které využívá pouze první operaci, však určitě napsat umíme: stačí obrátit všechny jedničky na nuly, tedy počet provedených operací bude počet jedniček v r. Řešení využívající pouze druhé operace, můžeme napsat více způsoby, my si však v návaznosti na těžší variantu zvolíme ten, který využívá metodu dynamického programování, o kterém si můžete více přečíst v KSPí kuchařce.
Pořídíme si dvourozměrné pole dp a v dp[i][b] pro i = 1, 2, …, n a b = 0, 1 si spočítáme, na kolik nejméně operací druhého typu zvládneme změnit prvních i znaků na samé b (nuly nebo jedničky). Je zřejmé, že abychom se spočítaným polem dp leží odpověď v dp[n][0]. Jak ale spočítáme hodnotu dp[i][b] z předchozích? Předpokládejme, že počítáme dp[i][0], případ s jedničkou by se dělal podobně. Pokud je r[i] nula, pak dp[i][0] = dp[i - 1][0]: levněji, než že převedeme prvních i – 1 znaků na nuly a pak neuděláme nic, to určitě neumíme. Pokud je r[i] jedna, pak je dp[i][0] = dp[i - 1][1] + 1: nejprve převedeme všechny předchozí znaky také na jedničky a~pak na úsek [0…i] provedeme operaci druhého typu, čímž ho převedeme na samé nuly. Rozmyslíme si, že levněji to také neumíme.
A jak vyřešit těžší variantu? Úplně stejně, jen se nám trochu změní způsob, jak počítáme dp: díky tomu, že máme povoleny obě operace, nám přibydou další možnosti, ze ketrých budeme pro dp[i][b] vybírat nejlevnější. Rozebereme opět pouze počítání dp[i][0]. Pokud je na i-té pozici nula, nic se nezmění: dp[i][0] = dp[i - 1][0], protože levněji to stále neumíme. Zajímavý je případ, kdy r[i] = 1. Pak máme dvě možnosti: převést r[0 … i–1] na samé nuly a použít na r[i] operaci prvního typu, nebo převést r[0 … i–1] na samé jedničky a použít na r[i] operaci druhého typu. Z těchto dvou možností pak vybíráme tu levnější. Zapsáno vzorcem: dp[i][0] = min(dp[i – 1][0] + 1, dp[i – 1][1] + 1) = min(dp[i – 1][0], dp[i – 1][1]) + 1.
V obou případech máme celkem O(N) stavů a každý dokážeme spočítat v konstantním čase. Všimneme si, že pole dp si nemusíme pamatovat celé – pro výpočet dp[i] nám stačí jen hodnoty dp[i – 1]. Nicméně stále musíme do paměti načíst vstup, takže pamětová složitost je také O(N).
Ukázkový program (C++)
#include <bits/stdc++.h>
// "magický" include načítající celou standardní knihovnu
using namespace std;
/* Vyřeší jeden testovací vstup. */
void solve(void)
{
// Načteme N
int N;
cin >> N;
// Načteme naše dva stringy
string s, t;
cin >> s >> t;
// Trik: budeme se znaky 'a' a 'b' pracovat jako s čísly
// Navíc v kódování ASCII platí, že 'a' + 1 = 'b', takže odečtením 'a' od
// všech prvků s a t získáme dvě posloupnosti nul a jedniček
for (int i = 0; i < N; i++)
s[i] -= 'a', t[i] -= 'a';
// Naše rozdílové pole
vector<bool> r;
// Převedeme na ekvivalentní úlohu, kdy chceme, aby r = s XOR t bylo nulové
for (int i = 0; i < N; i++)
r.push_back(s[i] ^ t[i]);
/* Minimální počet operací potřebných na změnění prvních `i` znaků řetězce
* na samé nuly resp. jedničky (odpovídá dp[i][0] a dp[i][1]) */
int cena_nuly = 0, cena_jednicky = 0;
for (int i = 0; i < N; i++) {
int mi = min(cena_nuly, cena_jednicky);
if (r[i]) { // na i-tém políčku je jednička
cena_nuly = 1 + mi;
// cena_jednicky se nezmění
} else { // na A[i] je nula
// analogicky
cena_jednicky = 1 + mi;
// cena_nuly se nezmění
}
}
// Vypíšeme cenu za vynulování prvních N znaků, tedy všech
cout << cena_nuly << "\n";
}
int main(void)
{
int T;
cin >> T;
while (T--)
solve();
return 0;
}
Ukázkový program (C)
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <string.h>
/* Vyřeší jeden testovací vstup. */
void solve(void)
{
// Načteme N
int N;
scanf("%d", &N);
// Naalokujeme si pole pro oba řetězce (+1 za ukončovací \0)
char *s = malloc((N + 1) * sizeof(*s));
char *t = malloc((N + 1) * sizeof(*t));
assert(s && t); // Spadneme, pokud nám systém nepřidělil paměť
// Načteme oba řetězce
scanf("%s", s);
scanf("%s", t);
// Trik: budeme se znaky 'a' a 'b' pracovat jako s čísly
// Navíc v kódování ASCII platí, že 'a' + 1 = 'b', takže odečtením 'a' od
// všech prvků s a t získáme dvě posloupnosti nul a jedniček
for (int i = 0; i < N; i++)
s[i] -= 'a', t[i] -= 'a';
// Převedeme na ekvivalentní úlohu, kdy chceme, aby r = s XOR t bylo nulové.
// Pole s a t už nepotřebujeme, takže můžeme s přepisovat a nemusíme pro r
// alokovat další paměť
for (int i = 0; i < N; i++)
s[i] ^= t[i];
char *r = s; // kvůli korespondenci s popisem řešení
// t už (také) nepotřebujeme
free(t);
/* Minimální počet operací potřebných na změnění prvních `i` znaků řetězce
* na samé nuly resp. jedničky, odpovídá dp[i][0], dp[i][1] */
int cena_nuly = 0, cena_jednicky = 0;
for (int i = 0; i < N; i++) {
int min = (cena_nuly < cena_jednicky) ? cena_nuly : cena_jednicky;
if (r[i]) { // na i-tém políčku je jednička
cena_nuly = 1 + min;
// cena_jednicky zůstává stejná
} else { // na A[i] je nula
// analogicky
cena_jednicky = 1 + min;
// cena_nuly se nemění
}
}
// Vypíšeme cenu za vynulování prvních N znaků, tedy všech
printf("%d\n", cena_nuly);
free(r); // Uvolní i s, protože oba ukazují na stejné místo v paměti
}
int main(void)
{
int T;
scanf("%d", &T);
while (T--)
solve();
return 0;
}
