Что такое специальные задачи в соревновательном программировании?

Ad Hoc задачи — это задачи, которые нельзя отнести ни к одной из категорий с хорошо изученными решениями, поскольку каждое описание проблемы и соответствующее решение уникальны. Эти проблемы не подпадают под стандартные категории, для их решения не существует конкретной или общей методики. Многие задачи Ad Hoc просты, но это не относится ко всем задачам Ad Hoc.

1. Специальные задачи часто появляются на соревнованиях по программированию. В ICPC ≈ 1-2 задачи из каждых ≈ 10 задач являются Ad Hoc задачами. В соревновании по программированию, если задача Ad Hoc проста, она обычно будет первой задачей, решаемой командами. Однако в тех случаях, когда решения специальных проблем были слишком сложны для реализации, некоторые команды решали их в последний час. В региональном соревновании ICPC, в котором участвует около 60 команд, ваша команда окажется в нижней половине рейтинга (30-60 место), если вы сможете решать только задачи Ad Hoc.
2. В IOI 2009 и 2010 было 1 легкое задание на 11-й день соревнований, обычно (легкое) специальное задание. Если вы являетесь участником IOI, вы определенно не выиграете ни одной медали, просто решив 2 простых специальных задания за 2 дня соревнований. Однако чем быстрее вы справитесь с этими 2 простыми задачами, тем больше времени у вас будет на работу над другими 2 × 3 = 6 сложными задачами.

Советы по специальной проблеме

Есть несколько общих советов по решению проблемы, которая кажется Ad Hoc:

1. Запись идей: Всякий раз, когда есть наблюдение, которое кажется полезным, запишите его, так как запись идей гарантирует, что они не будут забыты и потенциально могут быть решением.
2. Не зацикливайтесь: не зацикливайтесь на какой-либо конкретной идее, если только она не кажется полным решением проблемы. Лучше завершить поиск, так как проблемы Adhoc могут отнять много времени.
3. Нарисуйте много маленьких случаев: чтобы лучше понять проблему, рекомендуется потренироваться рисовать много маленьких случаев. Нарисуйте больше случаев, когда-
   • Есть проблема с отладкой.
   • Если вы не знаете, как начать с проблемы.
   • Всякий раз, когда неясно, как дальше подходить к проблеме.
   • Лучшая идея — нарисовать больше случаев и сделать наблюдения о свойствах проблемы.
4. Различные точки зрения: попробуйте подойти к проблеме с разных точек зрения. Продолжайте пробовать идеи, рисуйте визуальное изображение проблемы, пробуйте разные формулы, разные значения в формулах, пока не добьетесь прогресса.
5. Реализуйте шаблон в решении: после решения ряда задач программирования попытайтесь реализовать шаблон в решениях. Есть определенные идиомы, которые достаточно часто используются в соревновательном программировании.
   1. Например, с точки зрения C/C++, эти идиомы могут включать в себя библиотеки, такие как cstdio, cmath, cstring и т. д., ярлыки типов данных, основные процедуры ввода-вывода, макросы циклов и некоторые другие.
   2. Программисты на C/C++ могут хранить их в заголовочном файле, таком как adhocproblems.h. С таким заголовочным файлом решение любой проблемы можно начать с простого заголовочного файла в начале программы #include<adhocproblems.h>.

Категории набора специальных задач

Давайте обсудим некоторые категории набора задач Adhoc:

1. Карточная игра. Существует множество специальных задач, связанных с карточными играми. Один из подходов состоит в том, чтобы анализировать входные строки, поскольку игральные карты имеют обе масти.
   1. D/Diamond, C/Club, H/Heart и S/Spades.
   2. Для рангов обычный порядок: 2 < 3 < . . .< 9 < T/Десятка < J/Валет < Q/Queen < K/King < A/Ace12.
   3. Может быть хорошей идеей сопоставить эти строки с целочисленными индексами.
   4. Например, одним из возможных отображений является отображение D2 → 0, D3 → 1, . . . , DA → 12, C2 → 13, C3 → 14,. . . , SA → 51. Тогда работать с целыми индексами становится намного проще.
2. Игра в шахматы. Шахматы — еще одна популярная игра, которая появляется в задачах соревнований по программированию, и некоторые из этих задач являются задачами Ad Hoc. Например, комбинаторная задача подсчета количества способов расставить 8-ферзей на шахматной доске 8×8.
3. Другие игры: Многие другие игры, такие как Tic Tac Toe, Rock-Paper-Scissors, Snakes/Ladders, BINGO, Bowling и т. д., также участвовали в соревнованиях по программированию. Знание деталей этих игр может оказаться полезным, но большинство правил игры перечислены в описании задачи, чтобы не ставить в невыгодное положение участников, незнакомых с играми.
4. Проблемы, связанные с палиндромом: палиндром — это слово (или последовательность), которое можно читать одинаково в любом направлении. Наиболее распространенная стратегия проверки того, является ли слово палиндромным, состоит в том, чтобы перейти от первого символа к среднему и проверить, совпадают ли символы в соответствующей позиции сзади. Например, «ABCDCBA» — это палиндром.
5. Проблемы, связанные с анаграммой: анаграмма — это слово (или фраза), буквы которого можно переставить, чтобы получить другое слово (или фразу). Обычная стратегия проверки того, являются ли два слова анаграммами, состоит в сортировке букв слов и сравнении результатов. Например, возьмем wordA = 'cab', wordB = 'bca'. После сортировки wordA = 'abc' и wordB = 'abc', поэтому они являются анаграммами.