Editorial for 特殊位置 (APCS 2023-06 中級)


簡潔題意

\(n \times m\) 的正整數陣列(\(1 \le n, m \le 50\),每格 \(1 \sim 9\))。兩格的距離=列差的絕對值加行差的絕對值。對每個元素 \(A[i][j] = x\),把「距離不超過 \(x\)」的所有元素加起來(含自己,超出陣列的不算);總和除以 \(10\) 的餘數等於 \(x\) 除以 \(10\) 的餘數,\((i, j)\) 就是特殊位置。輸出特殊位置的個數,再一行一個、依列優先(列小的先、同列行小的先)列出。

依正確通過的測試資料筆數給分,其中:

  • 子題組 1(\(60\) 分):\(n = 1\)。
  • 子題組 2(\(40\) 分):無額外限制。

先拿下子題組 1(60 分):只有一列,範圍就是左右各 x 格

\(n = 1\) 時陣列是一排 \(m\) 個數,用一維陣列裝(上冊 6.1)。兩格的距離只剩「行差的絕對值」,所以 a[j] = x 的範圍就是第 \(j - x\) 個到第 \(j + x\) 個——一個 forj - x 跑到 j + x出界的索引跳過c < 0 || c >= mcontinue,上冊 4.5),剩下的加起來。這題的 \(x\) 最大 \(9\)、陣列可能只有幾格,範圍常常兩邊都伸出陣列外,出界判斷不是可有可無。

「特殊位置」的判斷照題目寫:total % 10 == x % 10(\(x\) 本來就小於 \(10\),x % 10 就是 x,照寫比較安心)。輸出格式是「先印個數、再一行一個位置」——所以要先全部判完、數好個數,再印位置:用一個 bool 陣列記每個位置是不是特殊位置(上冊 6.7),印的時候列註標永遠是 \(0\)。

#include <iostream>
using namespace std;

const int MAX_M = 50;

int main() {
    int n, m;
    cin >> n >> m;                    // 子題組 1 保證 n = 1:陣列只有一列
    int a[MAX_M];
    for (int j = 0; j < m; j++) cin >> a[j];

    int count = 0;
    bool special[MAX_M];              // 先記下每個位置是不是特殊位置,數完個數再印
    for (int j = 0; j < m; j++) {
        int x = a[j];
        int total = 0;
        for (int c = j - x; c <= j + x; c++) {    // 距離不超過 x:第 j - x 到第 j + x 個
            if (c < 0 || c >= m) continue;        // 超出陣列的不計算
            total += a[c];
        }
        special[j] = (total % 10 == x % 10);
        if (special[j]) count++;
    }

    cout << count << '\n';
    for (int j = 0; j < m; j++) {
        if (special[j]) cout << 0 << ' ' << j << '\n';
    }
    return 0;
}

這份程式交上去,範例 2 和子題組 2 會 WA——這是正常的,逐筆給分之下子題組 1 的 \(60\) 分穩穩到手。

從 60 分到 100 分:枚舉菱形範圍

二維的「距離不超過 \(x\)」是一個菱形(曼哈頓距離,13.6 的範圍枚舉):不是 \((2x + 1) \times (2x + 1)\) 的正方形——正方形的四個角落距離是 \(2x\),不在範圍裡。最直接的寫法是把包住菱形的正方形跑一遍(didj 各從 \(-x\) 到 \(x\)),每一格先看 abs(di) + abs(dj) > x 就跳過(不在菱形裡),再用 inside 擋掉出界的(13.2)。一維版那個「j - xj + x」的迴圈,就是這段在 \(n = 1\) 時的樣子。

輸出要「列小的先、同列行小的先」——這正好就是雙層迴圈的順序(外層 i、內層 j),判到一個就 push_back 進一個 vector<pair<int, int>>10.11),自然已經排好,不用另外排序;個數就是 answer.size()。陣列用巢狀 vector 裝(13.1),nma 放全域讓 inside 看得到。

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<vector<int>> a;

bool inside(int r, int c) {
    return 0 <= r && r < n && 0 <= c && c < m;
}

int main() {
    cin >> n >> m;
    a.assign(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];

    vector<pair<int, int>> answer;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int x = a[i][j];
            int total = 0;
            for (int di = -x; di <= x; di++) {          // 枚舉「範圍」裡的每一格
                for (int dj = -x; dj <= x; dj++) {
                    if (abs(di) + abs(dj) > x) continue;   // 曼哈頓距離超過 x:不在範圍內
                    int r = i + di, c = j + dj;
                    if (!inside(r, c)) continue;           // 出界的格子不計算
                    total += a[r][c];
                }
            }
            if (total % 10 == x % 10) answer.push_back({i, j});
        }
    }
    cout << answer.size() << '\n';
    for (auto [r, c] : answer) cout << r << ' ' << c << '\n';
    return 0;
}

最後那行 for (auto [r, c] : answer) 是範圍 for12.4)加結構化綁定(12.5),把每個 pair 一次拆成 rc。運算量:\(2500\) 個位置、每個最多掃 \(19 \times 19 = 361\) 格,總共不到 \(10^6\) 次。

測過再交:範例 2 的四個特殊位置怎麼排都一樣

範例 2 的答案是 \((0, 2)\)、\((1, 3)\)、\((2, 3)\)、\((3, 3)\)——列優先和行優先排出來剛好相同,輸出順序寫錯的程式兩個範例照樣全過。範例也沒有「一個特殊位置都沒有」和「範圍比整張陣列還大」的情況:

輸入 正確輸出 這一筆在測什麼
1 15 10 0 只有一格:範圍裡只有自己,總和 \(5\)、餘數 \(5\)
1 29 1 0 沒有特殊位置時只印一個 0;\(x = 9\) 的範圍兩邊都伸出陣列外,只算裡面的兩格
2 21 88 1 20 11 0 兩個特殊位置不同列也不同行:列小的 \((0, 1)\) 要先印。外層跑行、內層跑列的程式印成 1 0 在前——範例抓不到
2 37 3 39 4 1 10 0 菱形對正方形:\((1, 2)\) 的 \(1\) 只管上面的 \(3\) 和左邊的 \(4\)(\(1 + 3 + 4 = 8\),不特殊);把斜角 \((0, 1)\) 也算進去的程式得到 \(11\)、誤判它特殊,印 20 01 2
3 1555 30 01 02 0 直的陣列、每一格都是特殊位置(範例都是橫的)

五筆都親眼看過正確,這題就穩了。

常犯錯誤
  • 範圍用正方形(只看 \(|di| \le x\) 且 \(|dj| \le x\),沒檢查兩者相加):範例 1 是一列、沒有斜角,照樣過;範例 2 印 5 個。自測表第 4 列是手算得動的最小反例。
  • 只看同列同行的十字:範例 1 照樣過;範例 2 第三個位置印成 1 4(該印 2 3)。
  • 輸出順序用行優先(外層 j、內層 i):兩個範例全過;自測表第 3 列印 1 0 在前。
  • 距離寫成 < x:範例 1 印 3 個。
  • 自己沒算進總和:範例 1 印 0
  • 註標從 \(1\) 開始印,或列、行印反:範例 1 分別印 1 11 30 02 0
  • 沒判出界:範圍伸出陣列就讀到外面去——範例 1 第一格 \(x = 3\) 往左就出界,程式直接當掉。