Miners: วิธีหาว่าอดีตส่วนไหนทิ้งได้ จนแสนชิ้นเหลือ 256 สถานะ

คำถามในใบ้มีคำตอบสั้นมาก ของชิ้นถัดไปจะให้ถ่านเท่าไร ขึ้นกับสองชิ้นล่าสุดของเหมืองที่มันไปลงเท่านั้น ชิ้นที่สามนับจากท้ายไม่มีสิทธิ์โผล่ในหน้าต่างของชิ้นถัดไปอีกแล้ว และของที่อยู่ในอีกเหมืองหนึ่งก็ไม่เกี่ยวกัน เพราะคนงานสองเหมืองไม่ได้กินข้าวร่วมกัน

แปลว่าอดีตทั้งกอง ไม่ว่าจะยาวเป็นแสนชิ้น ยุบลงเหลือของที่ต้องจำแค่สี่ช่อง คือคู่ล่าสุดของเหมือง 1 กับคู่ล่าสุดของเหมือง 2 เรียกมันว่า (x₁, y₁) และ (x₂, y₂) โดย y คือชิ้นล่าสุด แต่ละช่องเป็นได้ 4 ค่า คือ M, F, B หรือ "ยังว่าง" สำหรับตอนที่เหมืองนั้นเพิ่งเริ่ม

พอนับได้ว่า 256 แบบ ข้อนี้ก็จบไปครึ่งหนึ่งแล้ว เพราะไม่ว่ากองจะยาวแค่ไหน จำนวนสถานะที่ต้องแบกไปข้างหน้า ก็ไม่โตตามความยาวกอง มันตันอยู่ที่ 256 ตลอดกาล

ให้ dp[s] คือถ่านรวมที่มากที่สุด ที่ทำได้เมื่อแจกของไปแล้ว i ชิ้น แล้วลงเอยที่สถานะ s พอดี ถ้าสถานะไหนไปไม่ถึงก็ปล่อยว่างไว้ ส่วนกำไรของการวางของหนึ่งชิ้นเขียนเป็นฟังก์ชันสั้น ๆ ได้แบบนี้

อ่านว่า นับจำนวนสมาชิกที่ไม่ซ้ำกันของ x, y, c โดยตัดช่องว่างทิ้ง ถ้าเหมืองยังไม่เคยได้ของเลย ทั้ง x และ y เป็นช่องว่าง เหลือแค่ c ตัวเดียว ได้ถ่าน 1 ซึ่งตรงกับที่โจทย์บอกว่า "ถ้ายังมีไม่ครบสามชิ้นก็ดูเท่าที่มี"

ทีนี้ของชิ้นถัดไปคือ c ยืนอยู่ที่สถานะเดิมหนึ่งตัว มันมีทางไปแค่สองทาง สมการจึงเขียนแบบผลัก คือยืนที่ต้นทางแล้วส่งค่าออกไปยังปลายทาง (ใช้ dp' แทนตารางของรอบถัดไป และ ⇐ แปลว่าเก็บค่าที่มากกว่าไว้)

สองบรรทัดนี้อ่านเป็นภาษาคนได้ทีละบรรทัด โดยมีหลักปักหมุดคือ y ของเหมืองไหนก็ตาม แปลว่า "ชิ้นล่าสุดของเหมืองนั้น" เสมอ ดังนั้นเหมืองที่เพิ่งรับของ ชิ้นล่าสุดของมันย่อมกลายเป็น c ทันที

• บรรทัดบน ของเข้าเหมือง 1 คู่ของเหมือง 1 เลื่อนไปหนึ่งช่อง y₁ ที่เคยเป็นชิ้นล่าสุด ถอยไปเป็นชิ้นก่อนหน้า และ c เข้ามาเป็นชิ้นล่าสุด กลายเป็น (y₁, c) ส่วน x₁ ตัวเก่า หลุดออกจากความจำถาวร เพราะมันอยู่ห่างจากชิ้นล่าสุดสามช่องแล้ว ถ่านที่ได้คิดจากคู่ก่อนเลื่อน คือ g(x₁, y₁, c) เพราะหน้าต่างที่คนงานมองคือของใหม่บวกสองชิ้นก่อนหน้าจริง ๆ ส่วนคู่ของเหมือง 2 คัดลอกมาทั้งดุ้น ไม่มีอะไรเกิดขึ้นกับมัน
• บรรทัดล่าง ของเข้าเหมือง 2 เรื่องเดียวกันเป๊ะ แค่สลับข้าง คู่ของเหมือง 2 เลื่อนเป็น (y₂, c) ถ่านคิดจาก g(x₂, y₂, c) ส่วนคู่ของเหมือง 1 คัดลอกมาเฉย ๆ

ผลที่ตามมาคือไม่มีเงื่อนไขให้ตัดทิ้งเลยสักบรรทัด ต่างจากตาราง DP ทั่วไปที่มักมีขอบตารางคอยกันไม่ให้ดัชนีติดลบ ที่นี่ทุกสถานะส่งของเข้าเหมืองไหนก็ได้เสมอ ของสองบรรทัดจึงใช้ได้ครบทุกช่องตลอดกอง เหลือแค่ต้องระวังว่า ปลายทางหนึ่งช่องอาจมีหลายต้นทางยิงเข้ามา จึงต้องเก็บตัวที่มากที่สุดไว้

คำตอบคือค่ามากที่สุดในตารางแถวสุดท้าย ไม่ต้องเจาะจงสถานะไหน เพราะจบกองแล้วสภาพของเหมืองไม่มีความหมายอีกต่อไป

เอากองกับดัก MMFFF มาเดินจริง ตารางข้างล่างคือสถานะทั้งหมดที่ไปถึงได้หลังแจกของครบ i ชิ้น เรียงจากถ่านมากไปน้อย กดถัดไปทีละขั้นเพื่อดูมันงอกและยุบ แถวสีเขียวคือสถานะที่จะพาไปจบที่คำตอบ 8

จำนวนสถานะโตขึ้นได้เร็วก็จริง แต่มันชนเพดาน 256 แล้วหยุด ต่อให้กองยาวเป็นแสนชิ้น ตารางนี้ก็สูงไม่เกิน 256 แถวเสมอ

แทนที่จะเก็บสถานะเป็นสตริงหรือ map เราอัด (x₁, y₁, x₂, y₂) เป็นเลขฐานสี่สี่หลัก ได้ตัวเลข 0 ถึง 255 พอดี ตารางจึงเป็นอาเรย์ธรรมดายาว 256 ช่อง เข้าถึงด้วยดัชนีตรง ๆ ไม่ต้องแฮชอะไรเลย

// หัวใจของทั้งข้อ: หนึ่งสถานะ แตกได้สองทาง เท่านั้น
int t1 = (y1 << 6) | (f << 4) | (x2 << 2) | y2;   // ของชิ้นนี้เข้าเหมือง 1
int v1 = cur[st] + coal(x1, y1, f);
if (v1 > nxt[t1]) nxt[t1] = v1;

int t2 = (x1 << 6) | (y1 << 4) | (y2 << 2) | f;   // ของชิ้นนี้เข้าเหมือง 2
int v2 = cur[st] + coal(x2, y2, f);
if (v2 > nxt[t2]) nxt[t2] = v2;

ค่า -1 ใช้แทน "สถานะนี้ยังไปไม่ถึง" เพราะ 0 เป็นถ่านที่ถูกต้องได้ (ตอนยังไม่แจกอะไรเลย) และต่างจากข้อ หยิบหนังสือ ตรงที่ตรงนี้ต้องล้างแถวปลายทางก่อนทุกรอบ เพราะเราเขียนแบบผลัก ช่องปลายทางบางช่องอาจไม่มีใครยิงเข้ามาเลยในรอบนี้ ถ้าไม่ล้างก็จะเหลือค่าเก่าจากรอบก่อนค้างอยู่

งานต่อของหนึ่งชิ้นคือวน 256 สถานะ สถานะละสองทาง ทั้งกองจึงเป็น O(256n) ที่ n = 100 000 คือราวห้าสิบล้านครั้งของงานเบา ๆ เครื่องผมวิ่งจบใน 56 มิลลิวินาที จากลิมิต 1.5 วินาที ส่วนหน่วยความจำใช้อาเรย์ int สองชุด ชุดละ 256 ช่อง รวมสองกิโลไบต์ ห่างจากลิมิต 16 เมกะไบต์อยู่มาก

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

// จำนวนชนิดอาหารที่ไม่ซ้ำกันในสามช่องล่าสุด (0 = ช่องว่าง ไม่นับ)
int coal(int a, int b, int c) {
    bool seen[4] = {false, false, false, false};
    seen[a] = seen[b] = seen[c] = true;
    return (int)seen[1] + (int)seen[2] + (int)seen[3];
}

int code(char c) { return c == 'M' ? 1 : (c == 'F' ? 2 : 3); }

int main() {
    int n;
    string s;
    if (!(cin >> n >> s)) return 0;

    // สถานะคือ (x1, y1, x2, y2) ช่องละ 4 ค่า อัดเป็นเลขฐานสี่สี่หลัก จึงมี 256 ช่อง
    const int S = 256;
    vector<int> cur(S, -1), nxt(S, -1);   // -1 = สถานะนี้ยังไปไม่ถึง (0 เป็นแต้มที่ถูกต้องได้)
    cur[0] = 0;                           // เริ่มต้น เหมืองทั้งสองยังว่าง

    for (int i = 0; i < n; i++) {
        int f = code(s[i]);
        fill(nxt.begin(), nxt.end(), -1); // ปลายทางถูกเขียนซ้ำได้ ต้องล้างก่อนทุกรอบ
        for (int st = 0; st < S; st++) {
            if (cur[st] < 0) continue;
            int x1 = st >> 6, y1 = (st >> 4) & 3, x2 = (st >> 2) & 3, y2 = st & 3;

            // ส่งเข้าเหมือง 1: คู่ล่าสุดของเหมือง 1 เลื่อนเป็น (y1, f) ส่วนเหมือง 2 ไม่ขยับ
            int t1 = (y1 << 6) | (f << 4) | (x2 << 2) | y2;
            int v1 = cur[st] + coal(x1, y1, f);
            if (v1 > nxt[t1]) nxt[t1] = v1;

            // ส่งเข้าเหมือง 2
            int t2 = (x1 << 6) | (y1 << 4) | (y2 << 2) | f;
            int v2 = cur[st] + coal(x2, y2, f);
            if (v2 > nxt[t2]) nxt[t2] = v2;
        }
        cur.swap(nxt);
    }

    cout << *max_element(cur.begin(), cur.end()) << '\n';
    return 0;
}

// ตัวตรวจสอบแบบซื่อ ๆ ลองแบ่งทุกแบบด้วยบิตมาสก์ ใช้ได้แค่ n ราว ๆ 20
// เอาไว้สุ่มเทียบกับโค้ดจริงก่อนส่ง ไม่ใช่โค้ดที่ส่งเข้าระบบตัดสิน
#include <bits/stdc++.h>
using namespace std;

int coal(int a, int b, int c) {
    bool seen[4] = {false, false, false, false};
    seen[a] = seen[b] = seen[c] = true;
    return (int)seen[1] + (int)seen[2] + (int)seen[3];
}
int code(char c) { return c == 'M' ? 1 : (c == 'F' ? 2 : 3); }

int main() {
    int n; string s;
    cin >> n >> s;
    int best = 0;
    for (long long mask = 0; mask < (1LL << n); mask++) {
        vector<int> q[2];
        int tot = 0;
        for (int i = 0; i < n; i++) {
            int f = code(s[i]);
            vector<int>& v = q[mask >> i & 1];
            int a = v.size() >= 2 ? v[v.size() - 2] : 0;
            int b = v.size() >= 1 ? v.back() : 0;
            tot += coal(a, b, f);
            v.push_back(f);
        }
        best = max(best, tot);
    }
    cout << best << '\n';
}

ตัวอย่างแรก MBMFFB มีจุดที่ชวนสะดุด เพราะแผนที่ดีที่สุดของมันคือเทของลงเหมืองเดียวทั้งกอง อีกเหมืองไม่ได้แตะเลยแม้แต่ชิ้นเดียว

นี่คือเหตุผลที่วิธีโลภตอบตัวอย่างในโจทย์ถูกทั้งสองข้อ กองที่สลับชนิดมาดีอยู่แล้วไม่ต้องการการวางแผนอะไรเลย กองที่หักวิธีโลภคือกองที่มีของซ้ำกันติดกัน ซึ่งเป็นตอนที่การแยกไปอีกเหมืองมีราคาเป็นศูนย์