ZeroJudge 解題筆記：m283. 螞蟻的擴散

作者：王一哲
日期：2025年12月5日


ZeroJudge 題目連結：m283. 螞蟻的擴散

解題想法

這題可以用一個二維陣列 $dp$ 記錄螞蟻從 $(a, b)$ 開始移動到每一格的機率，走到 $x = 0$ 或 $y = 0$ 時停止。走到格子 $(r, c)$ 的機率為 $$ dp[r][c] = (dp[r+1][c] + dp[r][c+1] + dp[r+1][c+1]) \times \frac{1}{3} $$ 用二層 for 迴圈計算往 $(0, 0)$ 方向走到每一格的機率。最後的答案等於 $1 - dp[0][0]$。 如果用 Python 解題，可以引入 fractions.Fraction 計算分數，也可以先計算分子最後再約分。

Python 程式碼

用 fractions.Fraction 計算分數，使用時間約為 53 ms，記憶體約為 4.1 MB，通過測試。

import sys
from fractions import Fraction

for line in sys.stdin:
    y, x = map(int, line.split())
    dp = [[0]*(x+1) for _ in range(y+1)]
    dp[y][x] = Fraction(1, 1)
    for r in range(y-1, -1, -1):
        for c in range(x-1, -1, -1):
            dp[r][c] = (dp[r+1][c] + dp[r][c+1] + dp[r+1][c+1])*Fraction(1, 3)
    print(1 - dp[0][0])

先計算分子，最後再約分，使用時間約為 18 ms，記憶體約為 3.1 MB，通過測試。

import sys, math

for line in sys.stdin:
    y, x = map(int, line.split())
    denominator = 3**(x+y-1)
    dp = [[0]*(x+1) for _ in range(y+1)]
    dp[y][x] = denominator
    for r in range(y-1, -1, -1):
        for c in range(x-1, -1, -1):
            dp[r][c] = (dp[r+1][c] + dp[r][c+1] + dp[r+1][c+1]) // 3
    numerator = denominator - dp[0][0]
    igcd = math.gcd(numerator, denominator)
    print(f"{numerator//igcd:d}/{denominator//igcd:d}")

C++ 程式碼

使用時間約為 1 ms，記憶體約為 84 kB，通過測試。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
    int y, x;
    while(scanf("%d %d", &y, &x) != EOF) {
        long denominator = long(pow(3, x+y-1));
        long dp[y+1][x+1];
        memset(dp, 0, sizeof(dp));
        dp[y][x] = denominator;
        for(int r=y-1; r>=0; r--) {
            for(int c=x-1; c>=0; c--) {
                dp[r][c] = (dp[r+1][c] + dp[r][c+1] + dp[r+1][c+1]) / 3;
            }
        }
        long numerator = denominator - dp[0][0];
        long igcd = __gcd(numerator, denominator);
        printf("%ld/%ld\n", numerator/igcd, denominator/igcd);
    }
    return 0;
}