Problem 938, Exhausting a Colour, asks for the value \(P(24690,12345)\). The three implementations make clear that the natural state is \(P(r,b)\), where \(r\) counts unresolved red objects and \(b\) counts unresolved blue pairs. The quantity being computed is the exact probability that red is the colour exhausted first.
The solution does not simulate randomness. Instead, it writes down the exact conditioning equation for each smaller state and builds the answer by dynamic programming. Once that structure is identified, the large target input becomes a straightforward table-filling problem.
The whole derivation comes from choosing the right state description and conditioning on the next partner seen by one distinguished red object.
Let \(P(r,b)\) denote the probability that red is eventually exhausted first when the unresolved part of the process contains \(r\) red objects and \(b\) blue pairs.
The boundary states are immediate. If no red objects remain, the desired event has already happened, so
$$P(0,b)=1 \qquad (b\ge 0).$$
If the blue pairs have all been consumed while red objects still remain, then red cannot be the first exhausted colour, so
$$P(r,0)=0 \qquad (r>0).$$
The code also encodes the relation
$$P(1,b)=P(1,b-1).$$
Since \(P(1,0)=0\), this forces
$$P(1,b)=0 \qquad (b\ge 1).$$
Now consider a state \((r,b)\) with \(r\ge 2\) and \(b\ge 1\), and expose one distinguished red object. The recurrence used in all three implementations shows that the next interaction has
$$r-1+2b$$
equiprobable possibilities.
There are \(r-1\) ways for the distinguished red object to meet another red object. In that branch, two red objects disappear from the unresolved configuration, so the state becomes \((r-2,b)\).
There are \(2b\) ways for it to meet one endpoint belonging to one of the blue pairs. In that branch, exactly one blue pair disappears from the remaining structure, while the reduced subproblem still has \(r\) red objects waiting to be exhausted, so the state becomes \((r,b-1)\).
Applying the law of total probability gives the central recurrence:
$$P(r,b)=\frac{(r-1)P(r-2,b)+2b\,P(r,b-1)}{(r-1)+2b}, \qquad r\ge 2,\ b\ge 1.$$
This formula is the mathematical heart of the solution. Every value needed for the final answer comes from repeated use of this identity together with the boundary states.
The recurrence never changes the parity of \(r\): one branch replaces \(r\) by \(r-2\), and the other leaves \(r\) unchanged. Therefore an odd number of red objects can never reach \(0\).
By induction on \(b\), this yields the stronger statement
$$P(r,b)=0 \qquad \text{for every odd } r.$$
This explains the special handling of the \(r=1\) column in the implementations. It also shows why the target state is meaningful: \(24690\) is even, so the desired probability is not ruled out by parity.
A small example makes the recurrence concrete. First, from the boundary values,
$$P(2,1)=\frac{1\cdot P(0,1)+2\cdot P(2,0)}{1+2}=\frac{1\cdot 1+2\cdot 0}{3}=\frac13.$$
Now apply the same recurrence one row later:
$$P(2,2)=\frac{1\cdot P(0,2)+4\cdot P(2,1)}{1+4}=\frac{1+4\cdot \frac13}{5}=\frac{7}{15}\approx 0.4666666667.$$
This example already shows the full structure of the real computation: each state depends on one entry in the same row, one entry in the previous row, and the exact branch counts \(r-1\) and \(2b\).
The C++, Python, and Java implementations evaluate the dynamic program row by row in increasing \(b\). For a fixed number of blue pairs, they sweep \(r\) from \(0\) to \(R\). That order is forced by the recurrence: \(P(r,b)\) needs \(P(r-2,b)\), which must already exist in the current row, and \(P(r,b-1)\), which comes from the previous row.
Each new row starts with \(P(0,b)=1\). The \(r=1\) entry is copied from the previous row, matching the relation \(P(1,b)=P(1,b-1)\). For every \(r\ge 2\), the implementation forms the weighted average from the recurrence and stores it immediately.
Only two one-dimensional buffers are necessary: one buffer holds the previous value of \(b\), and the other buffer is being filled for the current value of \(b\). After finishing a row, the buffers are swapped. This reduces memory from a full two-dimensional table to linear space while preserving exactly the same DP values. The final cell \(P(24690,12345)\) is then printed to 10 decimal places.
The conceptual DP table has \((R+1)(B+1)\) states, and each non-boundary state is filled in constant time. Therefore the running time is
$$O(RB).$$
For the target input, that is about \(24690\times 12345 \approx 3.05\times 10^8\) simple updates, which is large but still practical for an iterative implementation.
A naive full table would require \(O(RB)\) memory, but the recurrence only refers to the current row and the previous row. The implementations therefore use
$$O(R)$$
memory. Numerically, every newly computed state is a convex combination of values already known to lie in \([0,1]\), so the computation is stable for the required 10-decimal output.
Problem 938, Exhausting a Colour, verlangt den Wert \(P(24690,12345)\). Aus der gemeinsamen Rekurrenz der C++-, Python- und Java-Implementierungen erkennt man, dass der natürliche Zustand \(P(r,b)\) aus \(r\) noch offenen roten Objekten und \(b\) noch offenen blauen Paaren besteht. Gesucht ist die exakte Wahrscheinlichkeit, dass Rot die zuerst erschöpfte Farbe ist.
Die Lösung arbeitet nicht mit Zufallssimulation. Stattdessen wird für jeden kleineren Zustand die exakte Konditionierungsgleichung ausgewertet und daraus per dynamischer Programmierung der Zielwert aufgebaut. Sobald diese Struktur sichtbar ist, wird der große Eingabewert zu einem klaren Tabellenproblem.
Die gesamte Herleitung folgt daraus, dass man den richtigen Zustand wählt und dann nach dem nächsten Partner eines ausgezeichneten roten Objekts aufspaltet.
Sei \(P(r,b)\) die Wahrscheinlichkeit dafür, dass Rot am Ende zuerst erschöpft ist, wenn der noch ungelöste Teil des Prozesses aus \(r\) roten Objekten und \(b\) blauen Paaren besteht.
Die Randwerte sind sofort klar. Sind keine roten Objekte mehr übrig, dann ist das gewünschte Ereignis bereits eingetreten, also
$$P(0,b)=1 \qquad (b\ge 0).$$
Sind alle blauen Paare verbraucht, während noch rote Objekte vorhanden sind, dann kann Rot nicht mehr zuerst erschöpft werden, also
$$P(r,0)=0 \qquad (r>0).$$
Zusätzlich steckt im Code die Beziehung
$$P(1,b)=P(1,b-1).$$
Da \(P(1,0)=0\) gilt, folgt daraus
$$P(1,b)=0 \qquad (b\ge 1).$$
Betrachte nun einen Zustand \((r,b)\) mit \(r\ge 2\) und \(b\ge 1\), und wähle ein ausgezeichnetes rotes Objekt. Die in allen drei Implementierungen verwendete Rekurrenz zeigt, dass es für die nächste Auflösung genau
$$r-1+2b$$
gleichwahrscheinliche Möglichkeiten gibt.
In \(r-1\) Fällen trifft das ausgezeichnete rote Objekt auf ein weiteres rotes Objekt. Dann verschwinden zwei rote Objekte aus dem ungelösten Zustand, und man landet bei \((r-2,b)\).
In \(2b\) Fällen trifft es auf einen Endpunkt, der zu einem der blauen Paare gehört. Dann verschwindet genau ein blaues Paar aus der Reststruktur, während im reduzierten Teilproblem weiterhin \(r\) rote Objekte übrig bleiben, also entsteht der Zustand \((r,b-1)\).
Mit dem Satz der totalen Wahrscheinlichkeit erhält man die zentrale Rekurrenz:
$$P(r,b)=\frac{(r-1)P(r-2,b)+2b\,P(r,b-1)}{(r-1)+2b}, \qquad r\ge 2,\ b\ge 1.$$
Diese Formel ist der mathematische Kern der gesamten Lösung. Alle Werte für die Zielausgabe entstehen durch wiederholte Anwendung dieser Identität zusammen mit den Randzuständen.
Die Rekurrenz ändert die Parität von \(r\) nie: Ein Zweig ersetzt \(r\) durch \(r-2\), der andere lässt \(r\) unverändert. Deshalb kann eine ungerade Zahl roter Objekte niemals \(0\) erreichen.
Per Induktion über \(b\) folgt sogar die stärkere Aussage
$$P(r,b)=0 \qquad \text{für jedes ungerade } r.$$
Dadurch erklärt sich die Sonderbehandlung der Spalte \(r=1\) in den Implementierungen. Zugleich sieht man, warum der Zielzustand sinnvoll ist: \(24690\) ist gerade, also verbietet die Parität die gesuchte Wahrscheinlichkeit nicht.
Ein kleines Beispiel macht die Rekurrenz greifbar. Zuerst folgt aus den Randwerten
$$P(2,1)=\frac{1\cdot P(0,1)+2\cdot P(2,0)}{1+2}=\frac{1\cdot 1+2\cdot 0}{3}=\frac13.$$
Eine Zeile später ergibt sich dann
$$P(2,2)=\frac{1\cdot P(0,2)+4\cdot P(2,1)}{1+4}=\frac{1+4\cdot \frac13}{5}=\frac{7}{15}\approx 0.4666666667.$$
Schon dieses Miniaturbeispiel zeigt die volle Struktur der eigentlichen Rechnung: Jeder Zustand hängt von genau einem Eintrag in derselben Zeile, einem Eintrag in der vorherigen Zeile und den exakten Fallzahlen \(r-1\) und \(2b\) ab.
Die C++-, Python- und Java-Implementierungen berechnen das DP zeilenweise in aufsteigendem \(b\). Für eine feste Anzahl blauer Paare wird \(r\) von \(0\) bis \(R\) durchlaufen. Diese Reihenfolge ist durch die Rekurrenz erzwungen: \(P(r,b)\) benötigt \(P(r-2,b)\) aus der aktuellen Zeile und \(P(r,b-1)\) aus der vorherigen Zeile.
Jede neue Zeile beginnt mit \(P(0,b)=1\). Der Eintrag für \(r=1\) wird aus der vorherigen Zeile übernommen und implementiert damit direkt die Beziehung \(P(1,b)=P(1,b-1)\). Für jedes \(r\ge 2\) wird anschließend der gewichtete Mittelwert aus der Rekurrenz berechnet und sofort gespeichert.
Dafür genügen zwei eindimensionale Puffer: einer enthält die Werte für das vorige \(b\), der andere wird für das aktuelle \(b\) gefüllt. Nach Abschluss einer Zeile werden beide Puffer vertauscht. So sinkt der Speicherbedarf von einer vollständigen zweidimensionalen Tabelle auf linearen Speicher, ohne dass sich die DP-Werte ändern. Am Ende wird \(P(24690,12345)\) mit 10 Nachkommastellen ausgegeben.
Die konzeptionelle DP-Tabelle hat \((R+1)(B+1)\) Zustände, und jeder Nicht-Randzustand wird in konstanter Zeit berechnet. Daher beträgt die Laufzeit
$$O(RB).$$
Für die Zieleingabe sind das etwa \(24690\times 12345 \approx 3.05\times 10^8\) einfache Aktualisierungen. Das ist groß, aber für eine iterative DP noch praktikabel.
Eine naive Volltabelle bräuchte \(O(RB)\) Speicher. Da die Rekurrenz aber nur auf die aktuelle und die vorige Zeile zugreift, reduzieren die Implementierungen den Speicherverbrauch auf
$$O(R).$$
Numerisch ist die Berechnung stabil, weil jeder neue Zustand eine konvexe Kombination von bereits bekannten Werten aus dem Intervall \([0,1]\) ist.
Problem 938, Exhausting a Colour, için istenen değer \(P(24690,12345)\)'tir. C++, Python ve Java uygulamalarının ortak yinelemesi, doğal durumun \(P(r,b)\) olduğunu gösterir; burada \(r\) çözülmemiş kırmızı nesnelerin, \(b\) ise çözülmemiş mavi çiftlerin sayısıdır. Hesaplanan nicelik, kırmızının ilk tükenen renk olma olasılığının tam değeridir.
Çözüm rastgele deneme üretmez. Bunun yerine her küçük durum için tam koşullandırma denklemi yazılır ve sonuç dinamik programlama ile yukarı doğru kurulur. Bu bakış açısı kurulduğunda büyük hedef girdi, düzenli bir tablo doldurma problemine dönüşür.
Tüm türetim, doğru durum değişkenini seçip tek bir seçilmiş kırmızı nesnenin bir sonraki eşine göre koşullandırma yapmaktan çıkar.
\(P(r,b)\), çözülmemiş kısmında \(r\) kırmızı nesne ve \(b\) mavi çift kaldığında, sonunda ilk tükenen rengin kırmızı olma olasılığı olsun.
Sınır durumları doğrudan zorunludur. Hiç kırmızı nesne kalmamışsa istenen olay zaten gerçekleşmiştir; dolayısıyla
$$P(0,b)=1 \qquad (b\ge 0).$$
Buna karşılık bütün mavi çiftler tüketilmiş ama hâlâ kırmızı nesneler kalmışsa, artık ilk tükenen rengin kırmızı olması mümkün değildir; bu yüzden
$$P(r,0)=0 \qquad (r>0).$$
Kodda ayrıca şu ilişki açıkça yer alır:
$$P(1,b)=P(1,b-1).$$
\(P(1,0)=0\) olduğundan buradan
$$P(1,b)=0 \qquad (b\ge 1)$$
sonucu çıkar.
Şimdi \(r\ge 2\) ve \(b\ge 1\) olan bir \((r,b)\) durumunu ele alalım ve seçilmiş bir kırmızı nesneyi açığa çıkaralım. Üç uygulamanın da kullandığı yineleme, bir sonraki çözülmenin tam
$$r-1+2b$$
eş olasılıklı seçenek içerdiğini gösterir.
Bu seçilmiş kırmızı nesnenin başka bir kırmızı nesneyle eşleşmesinin \(r-1\) yolu vardır. Bu dalda çözülmemiş yapıdan iki kırmızı nesne kaybolur ve durum \((r-2,b)\) olur.
Bir mavi çifte ait uçlardan biriyle karşılaşmasının ise \(2b\) yolu vardır. Bu dalda kalan yapıdan tam bir mavi çift eksilir; fakat indirgenmiş alt problem hâlâ tükenmeyi bekleyen \(r\) kırmızı nesne içerir. Bu yüzden yeni durum \((r,b-1)\) olur.
Toplam olasılık kuralı merkezi yinelemeyi verir:
$$P(r,b)=\frac{(r-1)P(r-2,b)+2b\,P(r,b-1)}{(r-1)+2b}, \qquad r\ge 2,\ b\ge 1.$$
Çözümün matematiksel çekirdeği budur. Nihai cevap için gereken her değer, bu özdeşliğin sınır durumlarıyla birlikte tekrar tekrar uygulanmasından gelir.
Yineleme \(r\)'nin paritesini hiç değiştirmez: bir dal \(r\)'yi \(r-2\)'ye indirir, diğer dal ise olduğu gibi bırakır. Bu nedenle tek sayıda kırmızı nesne hiçbir zaman \(0\)'a ulaşamaz.
\(b\) üzerinde indüksiyonla daha güçlü ifade elde edilir:
$$P(r,b)=0 \qquad \text{her tek } r \text{ için}.$$
Bu gözlem, uygulamalarda \(r=1\) sütununun neden özel işlendiğini açıklar. Ayrıca hedef girdinin neden anlamlı olduğunu da gösterir: \(24690\) çifttir, dolayısıyla aranan olasılık parite tarafından baştan yok edilmez.
Küçük bir örnek yinelemeyi somutlaştırır. Önce sınır değerlerden
$$P(2,1)=\frac{1\cdot P(0,1)+2\cdot P(2,0)}{1+2}=\frac{1\cdot 1+2\cdot 0}{3}=\frac13$$
elde edilir.
Bir sonraki satırda ise
$$P(2,2)=\frac{1\cdot P(0,2)+4\cdot P(2,1)}{1+4}=\frac{1+4\cdot \frac13}{5}=\frac{7}{15}\approx 0.4666666667$$
olur. Bu küçük hesap bile gerçek çözümün tamamını özetler: her durum aynı satırdaki bir girişe, önceki satırdaki bir girişe ve tam dal sayıları olan \(r-1\) ile \(2b\)'ye bağlıdır.
C++, Python ve Java uygulamaları dinamik programı \(b\) artacak şekilde satır satır hesaplar. Sabit bir mavi çift sayısı için \(r\), \(0\)'dan \(R\)'ye kadar dolaşılır. Bu sıra zorunludur; çünkü \(P(r,b)\) hesabı, mevcut satırda önceden bulunmuş olması gereken \(P(r-2,b)\) değerine ve önceki satırdan gelen \(P(r,b-1)\) değerine ihtiyaç duyar.
Her yeni satır \(P(0,b)=1\) ile başlar. \(r=1\) girdisi önceki satırdan kopyalanır; bu da doğrudan \(P(1,b)=P(1,b-1)\) ilişkisini uygular. \(r\ge 2\) için yinelemedeki ağırlıklı ortalama hesaplanır ve sonuç hemen saklanır.
Bu işlem için yalnızca iki tek boyutlu tampon yeterlidir: biri önceki \(b\) değerini tutar, diğeri mevcut \(b\) için doldurulur. Bir satır bittiğinde tamponlar yer değiştirir. Böylece kavramsal olarak iki boyutlu olan DP tablosu, aynı sayısal sonuçlar korunarak doğrusal belleğe indirgenir. Son hücre olan \(P(24690,12345)\) daha sonra 10 ondalık basamakla yazdırılır.
Kavramsal DP tablosunda \((R+1)(B+1)\) durum vardır ve sınır olmayan her durum sabit zamanda doldurulur. Bu yüzden çalışma süresi
$$O(RB)$$
olur. Hedef girdi için bu, yaklaşık \(24690\times 12345 \approx 3.05\times 10^8\) basit güncelleme demektir; sayı büyüktür ama sıkı bir yinelemeli uygulama için hâlâ uygundur.
Naif bir tam tablo \(O(RB)\) bellek gerektirirdi. Oysa yineleme yalnızca mevcut satıra ve bir önceki satıra baktığı için uygulamalar belleği
$$O(R)$$
düzeyine düşürür. Sayısal açıdan da hesap kararlıdır; çünkü yeni her durum, zaten \([0,1]\) aralığında olduğu bilinen değerlerin konveks birleşimidir.
El problema 938, Exhausting a Colour, pide el valor \(P(24690,12345)\). La recurrencia compartida por las implementaciones en C++, Python y Java muestra que el estado natural es \(P(r,b)\), donde \(r\) cuenta los objetos rojos que siguen sin resolverse y \(b\) cuenta los pares azules que siguen activos. La cantidad buscada es la probabilidad exacta de que el rojo sea el primer color en agotarse.
La solución no hace simulación aleatoria. En lugar de eso, resuelve exactamente la ecuación de condicionamiento para cada estado más pequeño y construye la respuesta mediante programación dinámica. Una vez vista esa estructura, la entrada grande deja de ser un proceso probabilístico inabordable y pasa a ser una tabla que se rellena de forma determinista.
Toda la derivación sale de elegir bien el estado y de condicionar sobre el siguiente compañero de un objeto rojo distinguido.
Sea \(P(r,b)\) la probabilidad de que el rojo termine agotándose primero cuando la parte todavía no resuelta del proceso contiene \(r\) objetos rojos y \(b\) pares azules.
Las condiciones de borde son inmediatas. Si ya no queda ningún objeto rojo, el evento deseado ya ocurrió, así que
$$P(0,b)=1 \qquad (b\ge 0).$$
Si los pares azules se han consumido por completo y aún quedan objetos rojos, entonces el rojo ya no puede ser el primer color agotado, por lo que
$$P(r,0)=0 \qquad (r>0).$$
Además, el código hace explícita la relación
$$P(1,b)=P(1,b-1).$$
Como \(P(1,0)=0\), de ahí se deduce
$$P(1,b)=0 \qquad (b\ge 1).$$
Ahora tomemos un estado \((r,b)\) con \(r\ge 2\) y \(b\ge 1\), y fijemos un objeto rojo distinguido. La recurrencia utilizada en las tres implementaciones muestra que la siguiente resolución tiene exactamente
$$r-1+2b$$
posibilidades equiprobables.
Hay \(r-1\) maneras de que el objeto rojo distinguido se encuentre con otro objeto rojo. En esa rama desaparecen dos objetos rojos de la parte pendiente, de modo que el estado se reduce a \((r-2,b)\).
Hay \(2b\) maneras de que se encuentre con un extremo que pertenece a uno de los pares azules. En esa rama desaparece un par azul de la estructura restante, mientras que el subproblema reducido sigue teniendo \(r\) objetos rojos que todavía deben agotarse, así que el estado pasa a ser \((r,b-1)\).
Aplicando la ley de la probabilidad total se obtiene la recurrencia central:
$$P(r,b)=\frac{(r-1)P(r-2,b)+2b\,P(r,b-1)}{(r-1)+2b}, \qquad r\ge 2,\ b\ge 1.$$
Esta fórmula es el corazón matemático de toda la solución. Todos los valores necesarios para la respuesta final se obtienen repitiendo esta identidad junto con los estados de borde.
La recurrencia nunca cambia la paridad de \(r\): una rama sustituye \(r\) por \(r-2\) y la otra deja \(r\) intacto. Por lo tanto, un número impar de objetos rojos nunca puede llegar a \(0\).
Por inducción sobre \(b\), se obtiene la afirmación más fuerte
$$P(r,b)=0 \qquad \text{para todo } r \text{ impar}.$$
Esto explica el tratamiento especial de la columna \(r=1\) en las implementaciones. También aclara por qué la entrada objetivo es válida: \(24690\) es par, así que la probabilidad buscada no queda anulada de antemano por la paridad.
Un ejemplo pequeño hace tangible la recurrencia. Primero, usando los bordes,
$$P(2,1)=\frac{1\cdot P(0,1)+2\cdot P(2,0)}{1+2}=\frac{1\cdot 1+2\cdot 0}{3}=\frac13.$$
Luego, una fila más arriba,
$$P(2,2)=\frac{1\cdot P(0,2)+4\cdot P(2,1)}{1+4}=\frac{1+4\cdot \frac13}{5}=\frac{7}{15}\approx 0.4666666667.$$
Este ejemplo ya contiene la estructura completa del cálculo real: cada estado depende de una entrada en la misma fila, una entrada en la fila anterior y los conteos exactos de ramas \(r-1\) y \(2b\).
Las implementaciones en C++, Python y Java evalúan la programación dinámica fila por fila, con \(b\) creciendo de forma ascendente. Para un número fijo de pares azules, recorren \(r\) desde \(0\) hasta \(R\). Ese orden está impuesto por la recurrencia: \(P(r,b)\) necesita \(P(r-2,b)\), que ya debe haberse calculado en la fila actual, y \(P(r,b-1)\), que proviene de la fila anterior.
Cada fila nueva empieza con \(P(0,b)=1\). La entrada con \(r=1\) se copia desde la fila previa, implementando exactamente la identidad \(P(1,b)=P(1,b-1)\). Para cada \(r\ge 2\), el programa forma el promedio ponderado de la recurrencia y lo guarda inmediatamente.
Solo hacen falta dos búferes unidimensionales: uno para los valores del \(b\) anterior y otro para los valores del \(b\) actual. Al terminar una fila, ambos se intercambian. Así se reduce la memoria desde una tabla bidimensional completa hasta espacio lineal, sin cambiar en absoluto los valores del DP. La celda final \(P(24690,12345)\) se imprime con 10 decimales.
La tabla conceptual de DP tiene \((R+1)(B+1)\) estados, y cada estado no trivial se calcula en tiempo constante. Por tanto, el tiempo total es
$$O(RB).$$
Para la entrada objetivo, eso equivale a unas \(24690\times 12345 \approx 3.05\times 10^8\) actualizaciones simples; es mucho trabajo, pero sigue siendo razonable para una implementación iterativa compacta.
Una tabla completa ocuparía \(O(RB)\) memoria. Sin embargo, como la recurrencia solo consulta la fila actual y la anterior, las implementaciones reducen el espacio a
$$O(R).$$
Además, el cálculo es numéricamente estable porque cada nuevo estado es una combinación convexa de valores ya conocidos dentro del intervalo \([0,1]\).
第 938 题 Exhausting a Colour 要求计算 \(P(24690,12345)\)。从 C++、Python 和 Java 三份实现共享的递推式可以直接看出，自然状态应写成 \(P(r,b)\)：其中 \(r\) 表示还未处理完的红色对象数量，\(b\) 表示还未消去的蓝色配对数量。程序求的不是近似模拟值，而是“红色先被耗尽”的精确概率。
真正的关键在于：这道题不需要对随机过程做暴力模拟。只要把每个状态满足的条件概率方程写出来，再按照状态规模从小到大填表，就能精确得到最终答案。于是一个看起来很大的概率过程，被压缩成了一个完全确定的动态规划问题。
整套推导建立在两个观察上：第一，要把状态定义成真正能递推的形式；第二，要对某个固定红色对象接下来会遇到什么进行分类讨论。
定义 \(P(r,b)\) 为：当当前尚未解决的结构中还有 \(r\) 个红色对象和 \(b\) 个蓝色配对时，最终“红色先耗尽”的概率。
边界条件是直接确定的。如果已经没有红色对象了，那么红色显然已经先耗尽，因此
$$P(0,b)=1 \qquad (b\ge 0).$$
如果蓝色配对已经全部消失，而红色对象还没有耗尽，那么红色就不可能再成为先耗尽的颜色，所以
$$P(r,0)=0 \qquad (r>0).$$
代码中还显式体现了另一条关系：
$$P(1,b)=P(1,b-1).$$
再结合 \(P(1,0)=0\)，立刻得到
$$P(1,b)=0 \qquad (b\ge 1).$$
这说明只剩一个红色对象时，无论蓝色配对还剩多少，都不可能走到“红色先耗尽”的成功状态。
现在考虑 \(r\ge 2\)、\(b\ge 1\) 的状态 \((r,b)\)，并固定其中一个红色对象。三份实现所使用的递推式告诉我们：下一次解析这个对象时，一共有
$$r-1+2b$$
种等可能的选择。
其中有 \(r-1\) 种情况，是它遇到另一个红色对象。这样一来，未解决部分中的红色对象总数减少 2，于是状态变成 \((r-2,b)\)。
另外有 \(2b\) 种情况，是它遇到某个蓝色配对中的一个端点。沿着这个分支往下看，剩余结构里正好少掉一个蓝色配对，而还需要被耗尽的红色对象数量仍然是 \(r\)，所以状态变成 \((r,b-1)\)。
把这两类情况按概率加权平均，就得到核心递推：
$$P(r,b)=\frac{(r-1)P(r-2,b)+2b\,P(r,b-1)}{(r-1)+2b}, \qquad r\ge 2,\ b\ge 1.$$
这就是整道题真正的数学核心。最终答案所需的所有数值，都是靠这条公式配合边界条件逐步推出的。
观察递推可以发现，\(r\) 的奇偶性永远不会改变：一条分支把 \(r\) 变成 \(r-2\)，另一条分支则保持 \(r\) 不变。因此，如果一开始 \(r\) 是奇数，就永远不可能走到 \(r=0\)。
对 \(b\) 做归纳，可以得到更强的结论：
$$P(r,b)=0 \qquad \text{当 } r \text{ 为奇数时。}$$
这正好解释了实现里为什么要特别处理 \(r=1\) 这一列。它也说明目标状态 \(P(24690,12345)\) 是有意义的，因为 \(24690\) 是偶数，不会被这个不变量直接判成 \(0\)。
用一个小状态就可以把递推的工作方式看得很清楚。先计算 \(P(2,1)\)：
$$P(2,1)=\frac{1\cdot P(0,1)+2\cdot P(2,0)}{1+2}=\frac{1\cdot 1+2\cdot 0}{3}=\frac13.$$
然后再往上一行：
$$P(2,2)=\frac{1\cdot P(0,2)+4\cdot P(2,1)}{1+4}=\frac{1+4\cdot \frac13}{5}=\frac{7}{15}\approx 0.4666666667.$$
这个例子已经把完整算法的结构展示出来了：每个状态只依赖于同一行里更靠前的一个值、上一行同一列的一个值，以及精确的分支计数 \(r-1\) 和 \(2b\)。大规模输入只是把这件事重复很多次而已。
C++、Python 和 Java 实现都按 \(b\) 从小到大逐行计算这个 DP。对固定的蓝色配对数，它们再让 \(r\) 从 \(0\) 递增到 \(R\)。这种顺序不是随意选择的，而是由递推本身决定的：计算 \(P(r,b)\) 时，需要当前行已经算好的 \(P(r-2,b)\)，以及上一行保存下来的 \(P(r,b-1)\)。
每一新行都从 \(P(0,b)=1\) 开始。对于 \(r=1\)，实现直接把上一行的值搬过来，这正对应关系 \(P(1,b)=P(1,b-1)\)。当 \(r\ge 2\) 时，就按递推公式计算加权平均并立刻写入当前行。
因为每个状态只会访问“当前行”和“上一行”，所以实现根本不需要保存整张二维表，只需要两个一维缓冲区：一个表示上一行，一个表示当前行。当前行算完后交换两者，继续进入下一轮。这样空间复杂度从二维表的规模降到了线性规模，而数值结果完全不变。最后输出的就是 \(P(24690,12345)\) 的 10 位小数形式。
概念上的 DP 表共有 \((R+1)(B+1)\) 个状态，除边界外，每个状态都只需要常数次运算，因此总时间复杂度为
$$O(RB).$$
对目标输入来说，这大约是 \(24690\times 12345 \approx 3.05\times 10^8\) 次简单更新。数量不小，但对于紧凑的迭代型动态规划来说仍然是可行的。
如果直接保存整张二维表，空间复杂度会是 \(O(RB)\)。但由于递推只依赖当前行和上一行，实际实现把空间压缩到了
$$O(R).$$
从数值稳定性的角度看，这种做法也很稳健，因为每个新状态都是若干已知 \([0,1]\) 区间内数值的凸组合。
В задаче 938, Exhausting a Colour, требуется вычислить \(P(24690,12345)\). Общая для реализаций на C++, Python и Java рекуррентная схема показывает, что естественное состояние имеет вид \(P(r,b)\): здесь \(r\) обозначает число ещё не исчерпанных красных объектов, а \(b\) - число ещё не устранённых синих пар. Искомая величина - это точная вероятность того, что красный цвет исчерпается первым.
Решение не строится на случайном моделировании. Вместо этого для каждого меньшего состояния выписывается точное уравнение условной вероятности, после чего ответ собирается динамическим программированием. Как только эта структура замечена, большой вход перестаёт быть пугающим вероятностным процессом и превращается в обычное табличное вычисление.
Вся идея опирается на два шага: правильно выбрать пространство состояний и разложить следующий шаг по тому, с кем встретится один фиксированный красный объект.
Пусть \(P(r,b)\) - вероятность того, что красный цвет в итоге исчерпается первым, если в ещё не обработанной части процесса остаются \(r\) красных объектов и \(b\) синих пар.
Граничные условия немедленны. Если красных объектов уже не осталось, нужное событие произошло, поэтому
$$P(0,b)=1 \qquad (b\ge 0).$$
Если синие пары уже исчезли, а красные объекты ещё остались, то красный уже не может стать первым исчерпанным цветом, значит
$$P(r,0)=0 \qquad (r>0).$$
Кроме того, код явно реализует соотношение
$$P(1,b)=P(1,b-1).$$
Так как \(P(1,0)=0\), отсюда сразу следует
$$P(1,b)=0 \qquad (b\ge 1).$$
Теперь рассмотрим состояние \((r,b)\) при \(r\ge 2\) и \(b\ge 1\) и выделим один красный объект. Рекурсия, используемая во всех трёх реализациях, показывает, что следующее разрешение имеет ровно
$$r-1+2b$$
равновероятных возможностей.
Есть \(r-1\) способов, при которых выбранный красный объект связывается с другим красным объектом. Тогда из ещё не решённой части исчезают два красных объекта, и задача переходит в состояние \((r-2,b)\).
Есть \(2b\) способов, при которых он попадает на один из концов некоторой синей пары. Тогда из оставшейся структуры исчезает одна синяя пара, а число красных объектов, которые ещё должны исчерпаться, остаётся равным \(r\). Следовательно, новое состояние равно \((r,b-1)\).
По формуле полной вероятности получаем основную рекурсию:
$$P(r,b)=\frac{(r-1)P(r-2,b)+2b\,P(r,b-1)}{(r-1)+2b}, \qquad r\ge 2,\ b\ge 1.$$
Именно эта формула составляет математическое ядро решения. Все значения, необходимые для конечного ответа, появляются из многократного применения данного тождества вместе с граничными условиями.
Рекурсия никогда не меняет чётность \(r\): одна ветвь заменяет \(r\) на \(r-2\), а другая вообще не меняет \(r\). Значит, если число красных объектов нечётно, достичь состояния \(r=0\) невозможно.
Индукцией по \(b\) получается более сильное утверждение:
$$P(r,b)=0 \qquad \text{для любого нечётного } r.$$
Этим объясняется особая обработка столбца \(r=1\) в реализациях. Заодно становится ясно, почему целевое состояние не вырождено: число \(24690\) чётно, поэтому искомая вероятность не уничтожается одним лишь инвариантом.
Небольшой пример делает рекурсию наглядной. Сначала из граничных условий получаем
$$P(2,1)=\frac{1\cdot P(0,1)+2\cdot P(2,0)}{1+2}=\frac{1\cdot 1+2\cdot 0}{3}=\frac13.$$
Затем для следующей строки
$$P(2,2)=\frac{1\cdot P(0,2)+4\cdot P(2,1)}{1+4}=\frac{1+4\cdot \frac13}{5}=\frac{7}{15}\approx 0.4666666667.$$
В этом примере уже содержится вся структура полного вычисления: каждое состояние зависит от одного значения в той же строке, одного значения в предыдущей строке и точных счётчиков ветвей \(r-1\) и \(2b\).
Реализации на C++, Python и Java вычисляют DP построчно по возрастанию \(b\). При фиксированном числе синих пар значение \(r\) проходит от \(0\) до \(R\). Такой порядок обязателен, потому что для вычисления \(P(r,b)\) нужно значение \(P(r-2,b)\), уже посчитанное в текущей строке, и значение \(P(r,b-1)\), сохранённое из предыдущей строки.
Каждая новая строка начинается с \(P(0,b)=1\). Ячейка при \(r=1\) просто копируется из предыдущей строки, что напрямую реализует равенство \(P(1,b)=P(1,b-1)\). Для всех \(r\ge 2\) программа вычисляет взвешенное среднее по рекурсии и сразу записывает результат.
Полная двумерная таблица не нужна. Достаточно двух одномерных буферов: один хранит строку для предыдущего значения \(b\), второй заполняется для текущего. После завершения строки буферы меняются ролями. Поэтому память остаётся линейной, хотя математически DP имеет два параметра. В конце печатается значение \(P(24690,12345)\) с точностью до 10 знаков после запятой.
Концептуальная DP-таблица содержит \((R+1)(B+1)\) состояний, и каждое неграничное состояние считается за постоянное время. Следовательно, итоговая временная сложность равна
$$O(RB).$$
Для целевого входа это примерно \(24690\times 12345 \approx 3.05\times 10^8\) простых обновлений. Объём работы большой, но для плотной итеративной динамики он вполне реалистичен.
Полная таблица потребовала бы \(O(RB)\) памяти. Однако рекурсия обращается только к текущей и предыдущей строкам, поэтому реализации сокращают память до
$$O(R).$$
С вычислительной точки зрения схема устойчива: каждое новое значение является выпуклой комбинацией уже известных чисел из интервала \([0,1]\).
تطلب المسألة 938، Exhausting a Colour، حساب القيمة \(P(24690,12345)\). ومن العلاقة العودية المشتركة بين تطبيقات C++ وPython وJava يتضح أن الحالة الطبيعية هي \(P(r,b)\)، حيث يمثّل \(r\) عدد العناصر الحمراء التي لم تُستنزف بعد، ويمثّل \(b\) عدد الأزواج الزرقاء التي ما زالت قائمة. والكمية المطلوبة هي الاحتمال الدقيق لأن يكون الأحمر هو اللون الذي ينفد أولاً.
الحل لا يعتمد على المحاكاة العشوائية. بل يكتب معادلة التكييف الاحتمالي الدقيقة لكل حالة أصغر، ثم يبني الجواب بواسطة البرمجة الديناميكية. وبمجرد رؤية هذا البناء، تتحول المدخلة الكبيرة من عملية احتمالية معقدة إلى جدول حسابي محدد تماماً.
الفكرة كلها تقوم على اختيار توصيف الحالة بشكل صحيح، ثم التكييف على الشريك التالي لعنصر أحمر مميَّز.
لنعرّف \(P(r,b)\) على أنه احتمال أن يكون الأحمر هو اللون الذي يُستنزف أولاً عندما يحتوي الجزء غير المحسوم من العملية على \(r\) عناصر حمراء و\(b\) أزواج زرقاء.
حالات الحافة مباشرة. إذا لم يبق أي عنصر أحمر، فقد تحقق الحدث المطلوب بالفعل، ومن ثم
$$P(0,b)=1 \qquad (b\ge 0).$$
أما إذا اختفت الأزواج الزرقاء كلها بينما لا تزال عناصر حمراء موجودة، فلا يمكن عندئذٍ أن يكون الأحمر هو اللون الأول نفاداً، وبالتالي
$$P(r,0)=0 \qquad (r>0).$$
كما أن الشيفرة تجسّد أيضاً العلاقة
$$P(1,b)=P(1,b-1).$$
ومع \(P(1,0)=0\) نحصل فوراً على
$$P(1,b)=0 \qquad (b\ge 1).$$
الآن خذ الحالة \((r,b)\) عندما يكون \(r\ge 2\) و\(b\ge 1\)، واختر عنصراً أحمر مميزاً. العودية المستخدمة في التطبيقات الثلاثة تُظهر أن الخطوة التالية لها بالضبط
$$r-1+2b$$
احتمالاً متساوياً.
هناك \(r-1\) طريقة يلتقي فيها هذا العنصر الأحمر بعنصر أحمر آخر. في هذا الفرع يختفي عنصران أحمران من الجزء غير المحسوم، فتتحول الحالة إلى \((r-2,b)\).
وهناك \(2b\) طريقة يلتقي فيها بأحد طرفي زوج أزرق. في هذا الفرع يختفي زوج أزرق واحد من البنية المتبقية، بينما يبقى عدد العناصر الحمراء التي يجب أن تُستنزف مساوياً لـ \(r\)، ولذلك تصبح الحالة \((r,b-1)\).
وباستخدام قانون الاحتمال الكلي نحصل على العلاقة العودية المركزية:
$$P(r,b)=\frac{(r-1)P(r-2,b)+2b\,P(r,b-1)}{(r-1)+2b}, \qquad r\ge 2,\ b\ge 1.$$
وهذه الصيغة هي القلب الرياضي للحل كله. فجميع القيم اللازمة للإجابة النهائية تنتج من تكرار هذه الهوية مع شروط الحافة.
لا تغيّر العودية زوجية \(r\) أبداً: أحد الفرعين يستبدل \(r\) بـ \(r-2\)، والفرع الآخر يترك \(r\) كما هو. لذلك إذا كان عدد العناصر الحمراء فردياً، فلن يصل أبداً إلى \(0\).
وبالاستقراء على \(b\) نحصل على العبارة الأقوى
$$P(r,b)=0 \qquad (r \equiv 1 \pmod 2).$$
وهذا يفسر المعالجة الخاصة للعمود \(r=1\) في التطبيقات. كما يوضح أن الحالة الهدف ليست مستحيلة من البداية، لأن \(24690\) عدد زوجي.
يكفي مثال صغير لجعل العودية ملموسة. أولاً، من شروط الحافة نحصل على
$$P(2,1)=\frac{1\cdot P(0,1)+2\cdot P(2,0)}{1+2}=\frac{1\cdot 1+2\cdot 0}{3}=\frac13.$$
ثم في الصف التالي
$$P(2,2)=\frac{1\cdot P(0,2)+4\cdot P(2,1)}{1+4}=\frac{1+4\cdot \frac13}{5}=\frac{7}{15}\approx 0.4666666667.$$
هذا المثال الصغير يعرض البنية نفسها التي يستعملها الحل الكامل: كل حالة تعتمد على قيمة واحدة في الصف الحالي، وقيمة واحدة في الصف السابق، ومعاملي التفرع الدقيقين \(r-1\) و\(2b\).
تقيّم تطبيقات C++ وPython وJava البرمجة الديناميكية صفاً صفاً مع زيادة \(b\). ولكل عدد ثابت من الأزواج الزرقاء، تتحرك عبر \(r\) من \(0\) إلى \(R\). وهذا الترتيب مفروض من العودية نفسها: فحساب \(P(r,b)\) يحتاج إلى \(P(r-2,b)\) الذي يجب أن يكون محسوباً في الصف الحالي، وإلى \(P(r,b-1)\) القادم من الصف السابق.
يبدأ كل صف جديد بالقيمة \(P(0,b)=1\). أما الخانة \(r=1\) فتُنقل من الصف السابق، وهو ما يطابق تماماً العلاقة \(P(1,b)=P(1,b-1)\). وبعد ذلك، لكل \(r\ge 2\)، تُحسب القيمة الجديدة بوصفها متوسطاً موزوناً وفق العودية.
لا حاجة إلى جدول ثنائي الأبعاد كامل. يكفي استعمال مصفوفتين أحاديتَي البعد: واحدة للصف السابق وأخرى للصف الجاري. وبعد اكتمال الصف، يجري التبديل بينهما. وبهذا ينخفض الاستهلاك من ذاكرة بحجم الجدول الكامل إلى ذاكرة خطية، مع الحفاظ على القيم نفسها تماماً. وفي النهاية تُطبع القيمة \(P(24690,12345)\) بدقة 10 منازل عشرية.
يحتوي جدول البرمجة الديناميكية المفهومي على \((R+1)(B+1)\) حالة، وتُحسب كل حالة غير حدية بزمن ثابت. لذلك يكون الزمن الكلي
$$O(RB).$$
وبالنسبة إلى المدخلة الهدف، فهذا يعني نحو \(24690\times 12345 \approx 3.05\times 10^8\) تحديثات بسيطة. وهو عدد كبير، لكنه ما يزال عملياً ضمن تنفيذ تكراري محكم.
الجدول الكامل يحتاج إلى ذاكرة \(O(RB)\)، لكن بما أن العودية تعتمد فقط على الصف الحالي والصف السابق، فإن التطبيقات تخفض الذاكرة إلى
$$O(R).$$
ومن الناحية العددية، يبقى الحساب مستقراً لأن كل قيمة جديدة هي تركيب تحدبي لقيم معروفة مسبقاً ضمن المجال \([0,1]\).