Работая со студентами, я часто сталкиваюсь с тем, что если задача не кажется им понятной с первого взгляда, то они и не могут ее решить. В самом деле, всегда рассказывают конкретные методы и приемы, но не то, как надо думать, чтобы применить их. В этой заметке я попробую обобщить мой опыт решения задач на соревнованиях по программированию. Впрочем, некоторые советы будут применимы и для олимпиад по математике или первых шагов в научной работе.
Итак, вы прочли задачу и не знаете как ее решать. Попробуйте следующие приемы, зачастую какой-то из них может помочь.
Прием 1: "Вспомнить всё"
Попробуйте вспомнить какие-то похожие задачи, которые вам приходилось решать. Очень многие задачи не несут в себе совсем уж оригинальной идеи и, вероятно, опыт решения подобной задачи может быть использован для решения этой.
Прием 2: "От частного к общему"
Представьте, что у вы нашли решение задачи (ура!) Рассмотрите какой-то частный случай задачи. К нему, конечно, может быть применен алгоритм решения задачи. Поэтому, чтобы решить общую задачу вам необходимо решить все ее частные случаи. Попробуйте решить какой-либо частный случай (или несколько) и потом попытайтесь обобщить их до решения основной задачи. Такие частные случаи можно рассматривать как упрощения задачи, то есть рассуждать по принципу: "если я не знаю как решать сложную задачу, попробую-ка я ее упростить и найти решения упрощенной версии".
Популярные примеры упрощений (частных случаев):
- вам сформулирована задача для дерева, рассмотрите ее вариант, когда дерево вырождается в путь;
- в задаче фигурируют веса? рассмотрите вариант, когда все веса равны единице, или произвольному числу, или есть только два различных веса (и так далее).
Обратите внимание, что решение частного случая почти всегда не проще общего, поэтому надо пытаться найти максимально простое или эффективное решение.
Прием 3: "Смелая гипотеза"
Не стесняйтесь делать смелые гипотезы, которые вам кажутся правдоподобными. Далеко не всегда на контестах надо доказывать решения, развивайте внутреннюю интуицию. Сделав гипотезу, попробуйте ее доказать — возможно, это получится или даст понимание как её опровергнуть. Обязательно потестируйте гипотезу на широком наборе тестов, ведь будет очень обидно потратить время на реализацию решения на базе её и опровергнуть только после этого.
Примеры частых гипотез:
- ответ всегда существует;
- количество состояний небольшое.
Прием 4: "Чтобы решать задачу, ты должен думать как задача"
В самом деле, поставьте себя на место лирического героя задачи, представьте что это ваша работа обрабатывать наборы входных данных. Подумайте как бы вы действовали в этом случае. Попробуйте обработать самостоятельно несколько небольших примеров. Если задача про игру, поиграйте в нее. Иногда я пытаюсь визуализировать процесс или модель, чтобы лучше его понять. Это немного похоже на то, как показывают в фильмах способ мысли ученых. Попробуйте думать образами, представьте ответ, посмотрите на то, как он получается.
Прием 5: "Думаем вместе"
Этот прием применим только в командных контестах. Вдвоем или втроем начинайте по очереди называть какие-то понятные факты про задачу. Например: "если n четное, то ответ всегда 0", "если n простое, то решать надо так" и так далее. Иногда ваши коллеги будут подхватывать идеи и развивать их, так можно и дожать идею задачи до конца.
Прием 6: "Подбери метод"
Попробуйте перебрать популярные алгоритмы или методы, которые хоть как-то могут оказаться применимы для задачи. Полезно посмотреть на ограничения по задаче. Зафиксировав метод, попробуйте подумать над решением исходя из того, что задача решается с применением этого метода. Надо рассуждать как-то так: "Пусть задача решается с помощью разделяй-и-властвуй. Тогда пусть мы рекурсивно решили задачу для левой и правой половине, осталось как-то объединить эти ответы, как бы это сделать..."
Прием 7: "Распечатать-посмотреть"
Очень часто (особенно в задачах с небольшим вводом: одно/два числа) возникают какие-то закономерности в построении ответа. Чтобы увидеть закономерность иногда достаточно написать какой-то наивный метод решения задачи, сгенерировать ответы для большого количества тестов на небольших ограничениях и немного помедитировать над ответами. Чтобы не занимать компьютер, лучше распечатать полученные результаты и медитировать уже над листочком.
Иногда хорошо выводить не только сам ответ, но и какую-то дополнительную информацию, например, способ получения ответа.
Прием 8: "Гуглим"
Этот прием можно применять только, если правила раунда/контеста это разрешают. Если задача на последовательности, то можно поискать ответы (см. прием 7) на сайте https://oeis.org/. Полезно понять формальную модель задачи и гуглить по правильным математическим терминам.
