棒球遊戲 (APCS 2016-10 中級) 的題解


簡潔題意

九位球員固定依 \(1, 2, \ldots, 9, 1, 2, \ldots\) 的順序輪流打擊。輸入給的是每位球員各自的歷次打擊結果(第 \(i\) 行先給次數 \(a_i\),再給 \(a_i\) 個結果),要還原成實際發生的順序來模擬:1B、2B、3B 讓打者和壘上所有跑者各前進 \(1\)、\(2\)、\(3\) 個壘,HR 讓所有人回本壘,每回到本壘得 \(1\) 分;SO、FO、GO 出局數加 \(1\)、跑者不動;每累積 \(3\) 次出局就清空壘包。求第 \(b\) 次出局發生時的總得分(\(1 \le a_i \le 5\)、\(1 \le b \le 27\),紀錄保證至少有 \(b\) 次出局)。

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

  • 子題組 1(\(20\) 分):打擊結果只有 HR 與 SO。
  • 子題組 2(\(20\) 分):安打只有 1B,且 \(b = 3\)。
  • 子題組 3(\(20\) 分):\(b = 3\)。
  • 子題組 4(\(40\) 分):無額外限制。

先把順序排對:第 \(t\) 次打擊是誰的第幾次?

輸入是「一人一行」,比賽卻是「一人一次輪著來」——這題的第一個關卡就是把兩者接起來。把全場的打擊從 \(0\) 開始編號,第 \(t\) 次打擊:

  • 是第 \(t \bmod 9\) 位球員(\(0\) 起算)——每九次輪一圈;
  • 是他的第 \(t / 9\) 次打擊(整數除法)——每輪一圈,每個人各多打了一次。

\(t \bmod 9\) 與 \(t / 9\) 是上冊 2.6 的餘數與整除;九行長度不一樣的紀錄,用巢狀 vector<vector<string>> 收(10.3),record[i][j] 就是第 \(i\) 位球員的第 \(j\) 次結果。接下來只要讓 \(t\) 從 \(0\) 開始一路數上去,每次查 record[t % 9][t / 9],數到第 \(b\) 次出局就停——題目保證 \(b\) 次出局一定會在紀錄用完之前發生,所以不用擔心查到不存在的紀錄。

不能一位球員的整行處理完再換下一位:範例 1 的第 1 位球員打了 \(5\) 次,但第 \(3\) 次出局在他第 \(2\) 次上場之前就發生了。

先拿下子題組 1(20 分):只有全壘打和三振

只有 HR 和 SO 時壘上永遠沒人:HR 就是打者自己回本壘得 \(1\) 分,SO 就是出局數加 \(1\),數到第 \(b\) 次就停。這一段的重點是上面那個順序:

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

int main() {
    vector<vector<string>> record(9);      // record[i][j]:第 i 位球員的第 j 次結果
    for (int i = 0; i < 9; i++) {
        int a;
        cin >> a;
        record[i].resize(a);
        for (int j = 0; j < a; j++) cin >> record[i][j];
    }
    int b;
    cin >> b;

    int outs = 0, score = 0;
    for (int t = 0; ; t++) {               // 第 t 次打擊:第 t%9 位球員的第 t/9 次
        string result = record[t % 9][t / 9];
        if (result == "HR") {
            score++;                       // 子題組 1 保證壘上沒人:全壘打只有打者得分
        } else {                           // SO
            outs++;
            if (outs == b) break;          // 第 b 次出局:停
        }
    }
    cout << score << '\n';
    return 0;
}

兩個範例都有安打,這份程式交上去範例會 WA——這是正常的,逐筆給分之下子題組 1 的 \(20\) 分穩穩到手;想自己驗,用自測表的第 4 列。

從 20 分到 100 分:壘包用一排格子推

安打之後「打者和壘上每個人各前進 \(d\) 個壘」,用一個四格的陣列 base[0..3] 來記:base[1]、base[2]、base[3] 是一、二、三壘有沒有人(題目講「第幾壘」,照 6.3 從 \(1\) 用起),base[0] 是打者站的本壘。前進 \(d\) 個壘不用分一壘安打、二壘安打各寫一套——一格一格推 \(d\) 次就好:每推一次,三壘的人回本壘得分,二壘的人到三壘,一壘的人到二壘,本壘的打者到一壘。全壘打就是推 \(4\) 次,壘上所有人連打者都會回來。

出局時出局數加 \(1\),剛好湊滿 \(3\) 的倍數就把 base[1..3] 清空;加到 \(b\) 就停,後面的紀錄不看。

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

int main() {
    vector<vector<string>> record(9);      // record[i][j]:第 i 位球員的第 j 次結果
    for (int i = 0; i < 9; i++) {
        int a;
        cin >> a;
        record[i].resize(a);
        for (int j = 0; j < a; j++) cin >> record[i][j];
    }
    int b;
    cin >> b;

    bool base[4] = {false, false, false, false};   // base[1..3]:一、二、三壘有沒有人
    int outs = 0, score = 0;
    for (int t = 0; ; t++) {               // 第 t 次打擊:第 t%9 位球員的第 t/9 次
        string result = record[t % 9][t / 9];
        if (result == "SO" || result == "FO" || result == "GO") {
            outs++;
            if (outs == b) break;          // 第 b 次出局:停,後面不算
            if (outs % 3 == 0) {           // 三出局:清空壘包
                base[1] = base[2] = base[3] = false;
            }
        } else {
            int d;                         // 要前進幾個壘
            if (result == "HR") d = 4;
            else d = result[0] - '0';      // "1B" → 1、"2B" → 2、"3B" → 3
            base[0] = true;                // 打者站上本壘
            for (int step = 0; step < d; step++) {   // 一格一格推 d 次
                if (base[3]) score++;      // 三壘的人回本壘得分
                base[3] = base[2];
                base[2] = base[1];
                base[1] = base[0];
                base[0] = false;
            }
        }
    }
    cout << score << '\n';
    return 0;
}

result[0] - '0' 是 8.2 的字元轉數字;全場最多 \(45\) 次打擊、每次最多推 \(4\) 格,運算量小到不用算。子題組 2、3 的 \(b = 3\) 不需要特別處理——跑到第 \(3\) 次出局自然就停了。

測過再交:兩個範例的 \(b\) 都是 \(3\) 的倍數

兩個範例用同一份紀錄,只差 \(b = 3\) 和 \(b = 6\)——都剛好停在半局結束。沒蓋到的:\(b\) 停在半局中間(後面的得分不能算)、滿壘全壘打、三壘安打把跑者送回來、以及九個人打擊次數不一樣時的順序。自己造的時候每人只給一、兩次紀錄,用「第 \(t\) 次是第 \(t \bmod 9\) 位的第 \(t / 9\) 次」在紙上排一遍就能算出答案。

輸入 正確輸出 這一筆在測什麼
1 1B / 1 1B / 1 1B / 1 HR / 1 SO / 1 SO / 1 SO / 1 SO / 1 SO / 1 4 滿壘全壘打:三位跑者加打者共 \(4\) 分,第 \(1\) 次出局就停
1 1B / 1 3B / 1 GO / 1 GO / 1 2B / 1 SO / 1 SO / 1 SO / 1 SO / 3 2 三壘安打把一壘跑者送回本壘、自己站三壘;兩出局後二壘安打再送他回來
1 1B / 1 SO / 1 SO / 1 SO / 1 1B / 1 3B / 1 SO / 1 SO / 1 SO / 4 1 三出局後壘包清空:第 1 位的跑者不能留到下半局被三壘安打送回來(不清空會印 2)
1 HR / 1 SO / 1 HR / 1 SO / 1 SO / 1 SO / 1 SO / 1 SO / 1 SO / 1 1 \(b = 1\) 停在半局中間:第 \(1\) 次出局之後的全壘打不算(子題組 1 版就能驗)
2 1B HR / 2 1B SO / 1 SO / 1 SO / 1 SO / 1 SO / 1 SO / 1 SO / 1 SO / 8 1 打擊次數不一樣:第 1、2 位的第二次要排在其他七人之後;一行一行處理會把兩支安打接在一起算成 2

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

常犯錯誤
  • 一位球員的整行處理完再換下一位:範例 1 印 3、範例 2 印 3。
  • 三出局沒清空壘包:範例 2 印 8;自測表第 3 列印 2。
  • 把 \(b\) 湊成整局(\(b\) 不是 \(3\) 的倍數也算到半局結束):兩個範例都剛好過,自測表第 4 列印 2。
  • 全壘打忘了打者自己也得分(只推 \(3\) 格、打者留在三壘):兩個範例都剛好過——他後來被別人的安打送回來了;自測表第 1 列印 3、第 4 列印 0。
  • 自己重排順序時用錯了長度(例如拿第 \(9\) 位的打擊次數當輪數):讀到不存在的紀錄,直接當掉。
  • 第 \(b\) 次出局之後還繼續算到紀錄用完:範例 1、2 都印 9。