ZeroJudge 解題筆記：a291. nAnB problem

作者：王一哲
日期：2025年7月6日


ZeroJudge 題目連結：a291. nAnB problem

解題想法

先掃過一次答案與猜測的數字，計算位置、數字都對的數量 A，如果不是位置、數字都對，則用兩個串列記錄 0 ~ 9 各個數字的數量。接下來再掃過這兩個串列，計算位置不對、數字對的數量 B。但是這一題我在 Python 上遇到很大的困難，換了好幾種寫法都超時，用 C++ 會過關但是速度還不夠快，需要改變寫法。

Python 程式碼

超時。

import sys
   
result = []
for line in sys.stdin:
    if not line.rstrip(): continue
    ans = list(map(int, line.split()))
    n = int(sys.stdin.readline())
    for _ in range(n):
        guess = list(map(int, sys.stdin.readline().split()))
        A, B = 0, 0  # 位置、數字都對的數量 A，位置不對、數字對的數量 B
        cnt_a, cnt_g = [0]*10, [0]*10  # 0 ~ 9 各個數字的數量
        for a, g in zip(ans, guess):  # 先掃一輪
            if a == g: A += 1  # 位置、數字都對，A 加 1
            else:  # 反之，記錄數字對應的數量
                cnt_a[a] += 1
                cnt_g[g] += 1
        for a, g in zip(cnt_a, cnt_g):  # 計算 B 的數量
            if a >= g: B += g
            else: B += a
        result.append(f"{A:d}A{B:d}B\n")
sys.stdout.write("".join(result))

寫法2，一次讀取所有的測資，但還是超時。

import sys
   
result = []
lines = sys.stdin.readlines()
idx, lines_num = 0, len(lines)
while idx < lines_num:
    ans = list(map(int, lines[idx].split())); idx += 1
    n = int(lines[idx]); idx += 1
    for _ in range(n):
        guess = list(map(int, lines[idx].split())); idx += 1
        A, B = 0, 0  # 位置、數字都對的數量 A，位置不對、數字對的數量 B
        cnt_a, cnt_g = [0]*10, [0]*10  # 0 ~ 9 各個數字的數量
        for a, g in zip(ans, guess):  # 先掃一輪
            if a == g: A += 1  # 位置、數字都對，A 加 1
            else:  # 反之，記錄數字對應的數量
                cnt_a[a] += 1
                cnt_g[g] += 1
        for a, g in zip(cnt_a, cnt_g):  # 計算 B 的數量
            if a >= g: B += g
            else: B += a
        result.append(f"{A:d}A{B:d}B\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 0.3 s，記憶體約為 56 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int ans[4], guess[4], n;
    while(scanf("%d", &ans[0]) != EOF) {
        for(int i=1; i<4; i++) scanf("%d", &ans[i]);
        scanf("%d", &n);
        for(int t=0; t<n; t++) {
            for(int i=0; i<4; i++) scanf("%d", &guess[i]);
            // 位置、數字都對的數量 A，位置不對、數字對的數量 B
            // 0 ~ 9 各個數字的數量，已經扣掉位置、數字都對的數量
            int A = 0, B = 0, cnt_a[10] = {0}, cnt_g[10] = {0};
            for(int i=0; i<4; i++) {  // 先掃一輪
                if (ans[i] == guess[i]) {  // 位置、數字都對，A 加 1
                    A++;                
                } else {  // 反之，記錄數字對應的數量
                    cnt_a[ans[i]]++;
                    cnt_g[guess[i]]++;
                }
            }
            for(int i=0; i<10; i++) {  // 計算 B 的數量
                if (cnt_a[i] >= cnt_g[i]) B += cnt_g[i];
                else B += cnt_a[i];
            }
            printf("%dA%dB\n", A, B);
        }
    }
    return 0;
}