Задача F. "Умный мальчик"

Эта задача решается методом динамического программирования, где состояние - это текущая записанная на доске строка, а хранимое значение - это тройка , где result - это результат игры для игрока, который в данный момент ходит (проиграл он, или выиграл), a - это максимальное количество очков у него, и b - минимальное количество очков у соперника.

Тогда мы перебираем букву, перебираем куда мы ее поставим, и пытаемся улучшить текущий ответ. Для этого мы используем следующий критерий: наше состояние выигрышное тогда и только тогда, когда существует ход в проигрышное состояние. Из всех ходов, гарантирующих наш выигрыш, вы выберем такое, чтобы наши очки были максимальны, а при равенстве - очки соперника минимальны. Если наше состояние - проигрышное, то выбирать по этому критерию надо вообще из всех переходов.

Количество очков, которое получает игрок при записи новой строки, можно было считать, используя, например, префикс-функцию, но замечу, что решения, которые использовали встроенные в языки функции проверки вхождения одной строки в другую, тоже проходили по времени.

Хранить все состояния было проще всего в структуре данных map (или HashMap, TreeMap и подобные), но вполне адекватным решением было хранить результаты в массиве d[][][], где первое измерение - номер строки из алфавита, второе и третье измерение - начало и конец вхождения текущей строки в эту строку из алфавита.