Wataru

Состояний сильно больше не из-за 4-х лишних клеток, а потому что теперь для завершения надо собрать не 3 в ряд, а 4 а ряд. Поэтому состояний без вилок/выигрышных ситуаций становится сильно больше, ведь раньше только 2 фишки рядом поставить надо и все, а теперь 3, да еще и в ряд.

Но вообще, какая-то фигня у вас с кодом. Всего различных состояний для поля 3*4: 3^12 = 531441. Это включая невозможные состояния после завершения игры и те, где крестиков сильно больше чем ноликов например. Потому что каждая клетка может иметь 3 варианта (пустая, крестик, нолик). Вот 12 клеток дают 3^12. Вы же там как-то 1.2 миллиона насчитали - более чем в 2 раза больше. На самом деле это раз в 10 больше чем должно быть, если считать только допустимые состояния.

Для 4x4 всего состояний меньше 3^16 = 43миллиона. Это никак не может переполнить память, даже если на каждое состояние выделять по все 16 байт, то это займет едва 700 мегабайт. Даже если в 2 раза умножить на любые дополнительные расходы питоновских словарей, то будет полтора гига.

На таких мелких полях вам вообще никакие эвристики не нужны, все 43 миллиона можно сгенерировать меньше чем за секунду на стареньком процессоре.

А если еще и поле хранить в виде битовой маски, по 2 бита на клетку, то все поле 4x4 займет у вас 32 бита, поместится в обычную интовую переменную. И манипуляциями с битами можно быстро проверять, если где-то 3 в ряд.

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

Можно сделать указатель на const. Вот этот ваш const, он относится к самому указателю, его нельзя менять (в смысле, на другой адрес). Но после разыменовывания получается не константная ссылка. Вот оно в документации:

typename std::add_lvalue_reference<T>::type operator*() const

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

Так что если вы хотите запретить менять объект, то можно сделать так:

void foo(const std::unique_ptr<const int>& ptr) {
    if (ptr) {
        *ptr += 5; // Ошибка компиляции.
        std::cout << *ptr;
    }
}

int main() {
    std::unique_ptr<const int> ptr = std::make_unique<const int>(5);
    foo(ptr);
}

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

Но вообще, обычно нет смысла передавать unique_ptr по ссылке. Можно передать по ссылке сам объект, все равно владение в функцию не передается же. И уже там можно навешивать const, если надо. Или, если передавать просто unique_ptr, без ссылки, то даже лишнего кода не надо для обработки const:

void foo(const std::unique_ptr<const int> ptr) {
}

int main() {
    std::unique_ptr<int> ptr = std::make_unique<int>(5);
    foo(std::move(ptr));
}

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

Так же угол из двух двоек с пустыми местами через центр - если можно поставить центральную клетку, ставьте

Если нельзя выиграть вот прям щас, или поставить вилку, то надо ставить туда, где будет выигрыш оппонента, и если нет таких, то туда, где будет вилка.

У вас конструктор не передает initializer_list в поле arr[N], а сначала конструирует массив по умолчанию, а потом туда копирует ручками значения из initializer_list. Перед выполнением тела конструктора вся память должна быть выделена и все не иницилизированные явно поля инициализируются по умолчанию.

В качестве решения можно весь ваш ручной код выкинуть и передать список в конструктор arr:

static_array(std::initializer_list<type> il)
		requires std::is_copy_constructible_v<type> : 
        arr(std::forward(il)) {}

Если хотите проверить длину списка, можно это все еще сделать потом в теле конструктора.
Аналогично в остальных случаях.

Но вообще, можно не расписывать разные конструкторы, а сделать только один static_array(T&& init), где этот init и передавать в конструктор arr.

Если вы так хотите руками данные копировать через ваш place_at, то вам надо ваш array сделать типа char или uint8_t, выровнять и задать нужный размер через sizeof(type). Простой случай показан тут.

А вообще, чем вам std::array не нравится?

Это называется aliasing. Ну не ложится гладкая окружность (да и наклонные прямые) на прямоугольную сетку пикселей. SDL renderer похоже слишком примитивен и умеет красить только черные и белые пиксели. Если бы он где-то рисовал серые, картинка выглядила бы более гладкой.

Если вас это качество не устраивает, то вам надо найти какой-то алгоритм рисования окружности по пикселям и руками его реализовать (что-то вроде этого). Или реализовывать (сглаживание) anti-aliasing. Например, можно нарисовать сцену в текстуре в 2-3-4 раза больше нужного размера, потом ее отмасштабировать до размера на экране и уже это показывать.

Еще где-то пишут, что если использовать GPU а не software рендеринг в SDL то качество получше.

Проблема в том, что TInput с одной стороны выводится из первого аргумента, там у вас BuildableProperty<...,...,const Cursor&> согласно определению CursorProperty.

Но третий аргумент выводит TInput как просто Cursor, потому что это аргумент функции, а там передача по ссылке, даже в шаблонах, должна быть указана явно. Cursor != Cursor&, это разные типы.

Один из способов это починить - в объявлении SetProperty:

SetProperty(..., typename std::remove_reference<TInput>::type value)

Теперь, даже если в первом аргументе в BuildProperty используются ссылки, они не будут мешать в третьем аргументе.

Но вообще, по уму вам бы ваш шаблон BuildableProperty пофиксить. Вот у вас для каких-то случаев надо в нем ссылки использовать. Так может ссылки имеет смысл использовать всегда? Тогда вы в шаблоне BuildableProperty предполагайте что T, TInput - это просто типы, без ссыльности и константности, и внутри где надо расставьте &.

Не надо для каких-то случаев "передавать" в шаблон ссылки на какие-то типы.

Можно, но нужно ли? Польза только в том, что вы экономите 6 симолов (std:: уже можно убрать через using namespace std например). И то, только в случае, когда вам нужен именно вот такой вот указатель. А если вам нужен unique_ptr, а если вам нужен ваш собственный умный указатель, который как-то по другому память выделяет? А если вам надо не make_shared вызывать, а какой-то фабричный метод? Плюс это добавит кучу вопросов вроде, а как будет указатель на указатель? Указатель обычно идет после типа вроде int*, почему shared вы ставите перед ним?

В общем, возни много, а польза весьма ограниченная.

То, что вы описали в комментариях, это буквально блокировка чтения-записи. Функтор читает данные и может выполнятся параллельно несколько раз, но запись может быть только одна и она блокирует все чтения. Решение описано в википедии: 2 мьютекса, один счетчик. Атомиков не надо.

Вопрос только в том, какие именно значения подаются на вход в некоторых операциях.

входы (x) вам даны в таблице. Считайте слева на право а каждой коробочке ответ. Легче всего прямо на схеме результаты подписывать.

Единственная мысль: попробуйте что-то вроде кубических сплайнов. Для первого интервала делайте квадратичную интерполяцию по 3 первым точкам. Для каждого следующего интервала - кубическую по 4 точкам (начало предыдущего интервала, этот интервал, конец следующего).
Типа если мы видим что между точками 1 и 2 много регистраций, между 3 и 4 мало, то скорее всего на текущем интервале от 2 до 3 точки идут более плотно в начале.

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

Во-первых, оператор не виртуальный.

Во-вторых, это проблема из-за правил поиска операторов. Они ищутся только в типах, которые участвуют в выражении, т.е. int и WidthProperty.

Если хотите использовать оператор из родительского класса, надо в дочернем сделать
using Base::operator=;

Что бы протащить этот метод в пространство имен дочернего класса, где компилятор его найдет.

горизонтальной прямой, проходящей на заданном расстоянии С от соотвествующей оси координат.

Это прямая y=C. Горизонтальная прямая - она всегда на одно и то же расстояние выше оси OX. Вот это расстояние - C - вам и дано. Ясно, что "соответствующая" ось координат - это OX. потому что с OY горизонтальная прямая пересекается. И вообще, расстояние между двумя прямыми имеет смысл, если они параллельны.

Легче сначала решить другую задачу: Найдите нужную площадь, если расстояние от прямой до центра окружности - D. Уже потом подставьте в это abs(C-Y0).

Не вижу, где тут ДП.

Вы правильно заметили, что можно вместо ai и bi рассматривать только ai^bi. Мы как будто берем все A по дефолту и каждый игрок может своим решением это стандартное действие отменить, что равносильно брать или не брать ai^bi.

Но надо заметить еще одно важное свойство (пусть di = ai ^ bi). Любое di можно заменть на di^dj (j > i) и задача остается эквивалентной. Тут каждый игрок вместо решения брать или не брать dj в зависимсоти от текущей суммы, он будет решать. делать ли статус у dj таким же как у di или нет. Ну или, рассуждение как выше, стандартное действие - брать dj если di было взято. Каждый игрок может своим решением это действие отменить.

А это уже очень похоже на вычитание линейных уравнений друг из друга в методе гауса. Можно этим заняться и привести Di к виду, где для каждого разряда мы найдем "базисный вектор" и единица будет стоять только в нем, а во всех остальных числах на этом разряде будет стоять 0. Для каких-то разядов мы может такого не найдем, там может быть много единиц, но все они будут в базисных векторах для каких-то других разрядов. При чем начинайте фиксировать базис с максимальных разрядов. Тогда у вас будут какие-то базисные разряды, и не базисные, которые однозначно определяются базисными и меньше их.

Т.е. идете с конца по массиву D, из текущего числа xor-ите все базисные вектора. если стоит единица в нужном разряде. Если там остался не ноль, добавляете это число в базис для старшего бита.

И тут уже сразу ясно, надо ли какое-то Di брать или нет. Каждый игрок знает, хочет ли он этот разряд в конце сделать 1 или 0 (в зависимости от его цели и того, стоит ли 1 в xor всех A в этом разряде).

Вот и все. Никакого ДП.

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

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

Что-то вроде такого расположения работает на больших досках:

*...*...*
..*...*..

Во-вторых, можно решать через графы. Пусть каждая клетка - вершина графа. Ребра между соседними клетками. Заметим, что граф - двудольный (шахматная раскраска доски - это и есть 2 доли). Исходная задача поиска минимального количества клеток с пауками, это фактически задача поиска контролирующего множества вершин: каждая клетка должна или быть во множестве, или быть соседней с клеткой из множества. В двудольном графе эта задача равнасильна поиску максимального паросочетания. Это решение за O(n^2m^2).

Если хотите ДП, то перед переходами надо определиться с состояниями. Ясно, что будет какое-то ДП по профилю. Будем целиком покрывать сколько-то первых строк, а состояние последней строки хранить в маске. Поскольку каждая клетка может быть покрыта как снизу, так и сверху, то в состоянии надо держать состояние 2 последних строк.
Например, состоянием может быть f(k,m1,m2) - расставили пауков в клетках их первых k строк. Считаем минимальное количество пауков. Первые k-1 целиком покрыты, строка k покрыта маской m1, а строка k+1 - маской m2. База f(0,0,0) = 0, f(0, m1, m2) = infinity. Ответ будет в min_m2 (f(n, 2**m-1, m2)).

Переход снизу вверх: перебираем, куда мы ставим пауков в строке k+1. При этом важно, что бы строка k оказалось целиком покрыта. Пресчитываем маску в строке k+1, а маска в строке k+2 - это будет куда мы поставили пауков:
F(k,m1,m2) --> F(k+1, m2 | m3 | (m3 << 1) | (m3 >> 1), m3), для всех m3, таких что m3 | m = 2**m-1

Это будет решение за O(n6^m).

Циклы в питоне - это ужасно медленно, да. Не лучший язык для написания числодробилки.

Еще, оффтопик, база даных тут совсем не нужна. Достаточно выводить числа на экран или в текстовый файл. так быстрее будет.

У вас самый наивный перебор в лоб, его можно ускорить. Сначала сгенерируйте все кубы и схраните их в массив. Их будет примерно кубический корень из |MAX_VAL-MIN_VAL| - это достаточно маленькая величина.

Теперь задача: найти 3 числа в массиве, дающих в сумме число из массива. Это все еще O(n^3), если исползовать 4 индекса. Но можно ускорить решение методом "встреча по середине".
Вместо A+B+C=D из массива будем искать A+B=C-D. Для этого переберем все пары чисел, подсчитаем их сумму и сохраним в dict() вместе со списком индексами этих чисел (список всех пар, дающих эту сумму). Потом опять переберем все пары, подсчитаем их разность и посмотрим в словаре, а была ли пара с такой же суммой. Если была - вот мы нашли 4 числа, таких что A+B=C-D. извлекаем корни и выдаем это в ответ.
Это будет уже O(n^2) - заметно быстрее.