Матч 396, Строка DNA (DNAString)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Строка длины L называется периодической, если ее i-ый символ равен (i + p)-ому для всех i от 0 до L – p – 1 включительно. Например, строки “CATCATC”,“CATCAT”, “ACTAC” и “ACT” являются периодическими с периодом 3.

Составим строку, содержащую конкатенацию всех строк из массива dna. В ней необходимо совершить наименьшее количество замен, после выполнения которых строка будет иметь период, не больший maxPeriod. Заменой называется изменение одного символа на другой.

Класс: DNAString

Метод: int minChanges(int maxPeriod, vector<string> dna)

Ограничения: dna содержит от 1 до 50 элементов, dna[i] содержит от 1 до 50 символов ‘A’, ‘C’, ‘G’, ‘T’, 1 £ maxPeriod £ n, где n равно числу символов в объединенной строке.

Вход. Число maxPeriod и массив строк dna.

Выход. Наименьшее количество замен, после выполнения которых строка будет иметь период, не больший maxPeriod.

Пример входа

maxPeriod	dna
3	{"ATAGATA"}
1	{"AAAATTTCCG"}
12	{"ACGTATAGCATGACA","ACAGATATTATG","ACAGATGTAGCAGTA","ACCA","GAC"}

Пример выхода

1

6

20

РЕШЕНИЕ

обработка строк

Объединим строки массива dna при помощи функции accumulate.

Предположим, что мы хотим получить строку с периодом 1. Тогда все символы должны быть одинаковы. Найдем символ, чаще всего встречающийся в строке, и заменим на него все остальные символы.

Пусть требуется получить строку с периодом 2. Тогда символы, стоящие на четных местах, и символы на нечетных местах должны быть одинаковыми. В четных и нечетных позициях меняем символы на те, которые чаще всего в них встречаются.

Аналогично поступаем при получении строки с периодом i.

Для решения задачи перебираем все возможные значения периода i (1 £ i £ maxPeriod). Для каждого значения периода i вычисляем наименьшее число символов, которое следует изменить, в переменной add. Среди всех полученных значений add для разных i находим наименьшее, которое и будет результатом.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <numeric>

#include <algorithm>

using namespace std;

int d[256];

class DNAString

{

public:

int minChanges(int maxPeriod, vector<string> dna)

{

string s = accumulate(dna.begin(),dna.end(),string());

int add, i, j, k, res = s.size(), n = s.size();

for(i = 1; i <= maxPeriod; i++)

{

for(add = j = 0; j < i; j++)

{

memset(d,0,sizeof(d));

for(k = j; k < n; k += i) d[(int)s[k]]++;

add = accumulate(d,d+256,add) - *max_element(d, d + 256);

}

if (add < res) res = add;

}

return res;

}

};