Próbowałem różnych podejść, ale zawsze było trochę za wolno. Ostatecznie mam jakieś preprocessingi i bitsety, ale to i tak za wolne (na losowym maxteście minimalnie przekraczam TL, na nielosowym będzie gorzej).

Jak to się robi?

Dla każdego pola planszy zbadałem sąsiedztwo w odległości max. 4 pól i sumowałem wyniki, więc złożoność O(n^2). Dla 10d mam 2.96s.

Pokażesz kod?

Ja mam 1.17s największy czas. Nie chciałem aby kod rozumiał wszystkie przypadki, bo k nie mogło być większe od 4, więc przeliczałem je na palcach, co nie wyszło takie straszne.

Ja też mam O(n^2), ze sporą stałą, na ostatnim teście 1.7s. Rozważałem przypadki: jeśli X to pola które na początku są sąsiednie do tego zamalowanego kształtu, to zastanawiałem się ile pól z X biorę. Jeśli na przykład bierzemy jedno, to nasz kształt jest takim spójnym k-polowym "klockiem" - generuje sobie wszystkie takie klocki na początku jakkolwiek i potem próbuje je przykładać na planszy. Pozostałe przypadki sprowadziły się do jakiegoś mniej lub bardziej prostego przejścia po tej tablicy i posumowania czegoś.

A jak poradziliście sobie z policzeniem wszystkich kombinacji (np. podwójny klocek i podwójny klocek to jakaś możliwość, ale trzeba uważać żeby nie były obok siebie, bo wtedy jest policzone już jako poczwórny klocek)? Ja jakoś sobie rozrysowałem wszystkie możliwości z włączeń i wyłączeń, ale wyszło sporo kodu (i 10s na maxteście niestety).

U mnie też wyszło sporo różnych możliwości i sporo kodu, dożyłowałem go tak że różne "klocki" (triomina i tetramina) trzymam na maskach bitowych, które potem ANDuję z odpowiednią maską na planszy. Podobne maski przygotowałem dla wszystkim domin i triomin razem z ich sąsiedztwem. 2.93s na 10d, ale udało mi się wygenerować testy które na SIO na uruchomieniu próbnym chodziły 4.8s :P

Też mam O(n^2) z dużą stałą i 4.86s na ostatnim teście (uff).

Ja dla k=4 zliczam takie kombinacje:
- 4 klocki w strefie tuż przy istniejącej figurze (dowolnie stykające się ale różne)
- jeden podwójny klocek z dokładnie jednym polem w strefie i dwa pozostałe dowolnie niedotykające tego jednego
- dwa podwójne z dokładnie jednym w strefie, niedotykające się (ok. 40% czasu wykonania)
- jeden potrójny z przynajmniej jednym ale nie wszystkimi w strefie i jeden niedotykający go
- jeden poczwórny z przynajmniej jednym ale nie wszystkimi w strefie (ok. 50% czasu wykonania)

To ja chyba mam troszkę inaczej niż wszyscy i może nawet przyjemniej (4.19s na 10c po żyłowaniu) : (dla k = 4)
1.Liczę sobie odległości pustych pól od zamalowanych.
2.Zamieniam jedną jedynkę na zero (teraz będę liczył z tym polem wybranym) i poprawiam odległości, teraz w czasie stałym (!) liczę jaki jest wynik dla k = 3.
3.Wracam do poprzednich odległości (bez tej wybranej jedynki - ją zostawiam z zerem).
4.Powtarzam 2. i 3. dla wszystkich jedynek.
Wynik dla k = 3 w stałym to ta niefajna część rozwa: trzeba pamiętać liczbę jakichś takich kształtów: 1-2-3, 1-2-2, 1-2-1, 2-1-2, 1-2, 1 (to są odległości od zamalowanych pól).

Liczę BFS-em odległość od już ułożonych płytek przez 4 warstwy. Dodatkowo dla każdej z płytek o odległości od 1 do 4 liczę ile ma sąsiadów o stopień niższych, równych i wyższych. Podczas tych obliczeń również agreguję wyniki, żeby wiedzieć np. ile jest płytek o odległości 2 do której przylega dokładnie jedna o odległości 1, itp.
Te obliczenia wstępne są w miarę lekkie.
Rozwiązania dla k=1 i k=2 są trywialne.
Dla k=3 rozważam 4 przypadki: 1-1-1, 1-1-2, 1-2-2 oraz 1-2-3, przez numer oznaczam warstwę w której znajduje się płytka. Oczywiste jest, że nie może być płytki z trzeciej warstwy, jeśli w drugiej nie ma żadnej. Np. dla konfiguracji 1-2-3 sumuję iloczyny dla każdej płytki o odległości 2, czyli mnożę ilość przyległych jedynek razy ilość przyległych trójek. Dla reszty robię sobie podobne reguły.
Dla k=4 tych przypadków jest już 8. Co ciekawe cztery te, które mają tylko jedną jedynkę są proste, ale najbardziej czasochłonne dla obliczeń. Oczywiście miałem też programik do brute-force'owania małych testów, który pomógł mi wygenerować 76 przypadków kontynuacji z tej samotnej jedynki, tzn. jeśli mam jedynkę, to obok niej muszą być 3 kolejne płytki o odległościach 2 lub większych. Możliwe kontynuacje, np. dwie w lewo i jedna w górę to te 76 kombinacji. Mówiąc dosłownie dla każdej płytki o odległości 1 odpalam sprawdzenie wszystkich 76 kombinacji i zliczam ile się udało.
Reszta możliwości to O(n^2) lub stała.
W zastosowanym podejściu kombinacja 1-1-2-2 to istne piekło, o którym pragnę zapomnieć.
Wracając do pytania o żyłowanie czasu. Poza tymi 76-ma kombinacjami to zwykłe przejście przez każdy element planszy. Czas niewiele większy niż wczytywanie danych. Żyłować można te 76 kombinacji, których sprawdzenie w najgorszym przypadku zajmuje ponad 75% czasu. Np. jeśli płytka z prawej nie pasuje, to można pominąć od razu wszystkie inne kombinacje, które jej wymagają. Zrezygnowałem z tego, kiedy zobaczyłem na uruchomieniu próbnym, że najgorszy przypadek działa w trochę ponad 3s. Żyłowanie bardzo mocno będzie zależeć od przyjętego sposobu na rozwiązanie. U siebie widzę kilka możliwości, ale pewnie nie znajdą zastosowania u innych osób.
Przez chwilę rozważałem przejście na maski bitowe, czyli zamiast tablicy char[] "..#..##." trzymać 00100110, czyli 72. Dalej przejść na maski dwuwymiarowe trzymane w jednej liczbie. Dla każdego pola można spakować 40 otaczających pól w odległości <=5 w 64-bitową liczbę, wtedy sprawdzenie jakiejkolwiek kombinacji byłoby operacją jednostkową.
Swoją drogą, ciekawe jak poszłoby rozwiązywanie dla k=5?