18 września (czwartek) - 14.35
Jaro powiedział coś o zadaniach z IOI.
Przepraszam, za żenadę która się zrobiła na kółku.
Dokończenie zadania o ogrodach (Linear Garden)
Definicje
Ciąg — słowo złożone z literek L, P, w którego każdym podsłowie różnica ilości literek L i P nie jest większa niż 2 (tzn. w ogóle w poniższym opisie nie obchodzą nas niepoprawne słowa).
Mówimy, że (poprawny) ciąg jest typu T jeśli dla każdego jego prefiksu różnica L-P test w podanym przedziale w poniższej tabelce.
| Typ | Przedział ( L-P ) |
|---|---|
| 1 | [-2; 2] |
| 2 | [-2; 1] |
| 3 | [-1; 2] |
| 4 | [-2; 0] |
| 5 | [-1; 1] |
| 6 | [0; 2] |
Zauważmy, że pojedynczy ciąg może być wielu typów. W szczególności każdy ciąg jest typu 1.
Graf
(Uwaga! Na rysunku wierzchołki są przenumerowane)
Z wierzchołka X do Y mamy krawędź o etykiecie E, wtedy i tylko wtedy gdy spełnione są oba warunki
- dla każdego ogródka typu X, zaczynającego się na E, po usunięciu pierwszego E mamy ogród typu Y.
- dla każdego ogródka typu Y, po dopisaniu z przodu E dostajemy ogródek typu X.
Oznaczenia:
- L[T] — typ na końcu strzałki wychodzącej z T o etykiecie L, jeśli istnieje
- P[T] — typ na końcu strzałki wychodzącej z T o etykiecie P, jeśli istnieje
Zliczanie ciągów danego typu
D[k,T] — liczba ciągów długości k, które są typu T
Aby policzyć D[k,T] korzystamy ze skonstruowanego grafu. Liczbę wszystkich k-słów (czyli słów długości k) typu T możemy policzyć dodając dwie liczby:
- Liczbę k-słów typu T zaczynających się na L. Tych słów jest tyle samo, co (k-1)-słów typu L[T] (o ile L[T] istnieje, w przeciwnym razie tych ciągów jest zero). Jeśli nie wierzysz, spróbuj dogłębnie przemyśleć definicję grafu. Jeśli dalej nie wierzysz, miej pretensje i pisz do Accka.
- Liczbę k-słów typu T zaczynających się na P, czyli D[k-1,P[T]] (oczywiście o ile P[T] istnieje).
A zatem (o ile L[T] i P[T] istnieją):
D[k,T] = D[k-1,L[T]] + D[k-1,P[T]]
Na samym początku programu możemy sobie stablicować D[k,T] dla wszystkich k i T.
Zliczanie ciągów o danym prefiksie
Ile jest n-elementowych ciągów postaci LPPLLPL*?
- Spostrzeżenie 1. Wszystkich n-elementowych ciągów jest D[n,1].
- Spostrzeżenie 2. Spośród wszystkich n-elementowych ciągów, D[n-1, L[1]] zaczyna się na literkę L (nie wierzysz? wróć do poprzedniego podrozdziału)
- Spostrzeżenie 3. Spośród wszystkich n-elementowych ciągów, które zaczynają się na L, D[n-2, P[L[1]]] ma jako drugą literkę P.
- Spostrzeżenie 4. Spośród wszystkich n-elementowych ciągów, które zaczynają się na LP, D[n-3, P[P[L[1]]]] ma jako trzecią literkę P.
- …
- Spostrzeżenie 8. Wszystkich n-elementowych ciągów, które zaczynają się na LPPLLPL jest D[n-7, L[P[L[L[P[P[L[1]]]]]]]].
L[P[L[L[P[P[L[1]]]]]]] to nic innego jak numer wierzchołka grafu, w którym się znajdziemy startując od jedynki i idąc kolejno po krawędziach: L, P, P, L, L, P, L.
Zliczanie ciągów leksykograficznie mniejszych od danego
Ile jest n-elementowych ciągów leksykograficznie mniejszych od LPPLLPPL?
Tyle, ile w sumie n-ciągów poniższych postaci:
LL*
LPL*
LPPLLL* (takich jest zero)
LPPLLPL*
Oczywiście, aby wyliczyć liczbę ciągów leksykograficznie mniejszych od LPPLLPPL, nie liczymy osobno, w czasie liniowym, każdego z powyższych składników, tylko robimy to sprytniej, łażąc po grafie. Mam nadzieję, że każdy potrafi to wymyślić. Jeśli nie, proszę krzyczeć na Accka i spojrzeć w poniższy kod.
Implementacja
#include <stdio.h> int graph[7][2]={{1, 2}, {3, 2}, {1, 5}, {6, 4}, {3, 5}, {4, 6}}; int wyn[1000000][7]; char tekst[1000000]; int n, m; int main(void){ scanf("%d %d %s", &n, &m, tekst); for(int i=0; i<n; ++i) tekst[i]=(tekst[i]=='P'); for(int i=0; i<6; ++i) wyn[0][i]=1; for(int i=1; i<n; ++i) for(int j=0; j<6; ++j) wyn[i][j]=(wyn[i-1][graph[j][0]] + wyn[i-1][graph[j][1]]) % m; int res=0; int state=0; for(int i=0; i<n; ++i){ if(tekst[i]) res=(res+wyn[n-i-1][graph[state][0]]) % m; state=graph[state][tekst[i]]; }; printf("%d\n", (res+1)%m); };
Dyskusja
Warto w tym miejscu informować w której sali odbędzie się MOKIP.
Post preview:
Close preview