programming.in.th · ข้อ 2006

สี่เหลี่ยมพิฆาต: หาโครงสร้างซ้ำในเงื่อนไข แล้วต้นทุนยุบสองพันเท่า

สองท่าที่หยิบไปใช้ต่อได้ตลอด คือการมองหาว่าเงื่อนไขก้อนใหญ่มีตัวมันเองซ่อนอยู่ข้างในไหม และการเอาแฮชสตริงมาทำให้การตรวจหนึ่งชั้นเหลือเวลาคงที่ ผลคือ 82,358,940,040 ครั้งยุบเหลือ 35,820,200 ครั้ง

โจทย์ · หน่วยความจำที่อ่านกลับหัวแล้วเหมือนเดิม

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

สิ่งที่มินตราตามล่าอยู่เขาเรียกมันว่า สี่เหลี่ยมพิฆาต (killer square) นั่นคือตารางย่อยรูปจัตุรัส ที่มีช่องมากกว่าหนึ่งช่อง และเมื่อหมุนมันไป 180 องศาแล้วยังได้ภาพเดิมเป๊ะทุกช่อง งานของเราคือหาว่าจัตุรัสแบบนี้ ที่ใหญ่ที่สุดในตารางมีด้านยาวเท่าไร

หมุน 180 องศาคือหมุนกลับหัวกลับหางในทีเดียว ช่องมุมบนซ้ายจะไปแทนที่มุมล่างขวา ช่องบนขวาไปแทนล่างซ้าย พูดอีกแบบคือทุกช่องต้องจับคู่กับช่องที่อยู่ตรงข้ามมันผ่านจุดกึ่งกลางของจัตุรัส แล้วสองช่องนั้นต้องมีค่าเท่ากัน

ตารางตัวอย่างแรกมีสี่เหลี่ยมพิฆาตอยู่ 3 อัน ด้านยาว 3, 2, 2 คำตอบจึงเป็น 3

ตรงไหนที่ทำให้ข้อนี้ไม่ง่าย

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

ตารางขนาด 300 คูณ 300 มีจัตุรัสให้พิจารณา 8.96 ล้าน อัน ตัวเลขนี้ยังพอไหว ปัญหาอยู่ที่ต้นทุนของการตรวจหนึ่งอัน เพราะจัตุรัสด้านยาว k มี k × k ช่อง รวมทั้งตารางแล้วต้องเทียบช่องต่อช่องราว 82.4 พันล้าน ครั้ง ในเวลาหนึ่งวินาที

ลองเอง · หาจัตุรัสพิฆาตที่ใหญ่ที่สุด

ลองสังเกตดูว่าตอนกรอบเป็นสีเขียว มุมทั้งสี่มีความสัมพันธ์อะไรกัน แล้วขอบทั้งสี่ด้านล่ะ

เฉลย ตอนที่ 1 · หัวหอมที่ปอกทีละวง

เฉลย ตอนที่ 2 · วงนอกหนึ่งวงเทียบกันได้ในสี่ครั้ง

โค้ด C++

if (!two[r + 1][c + 1]) continue;             // ไส้ในด้าน k-2 ต้องผ่านก่อน
if (!rowFit(r, r + k - 1, c, k)) continue;    // ขอบบนคู่ขอบล่าง
if (!colFit(c, c + k - 1, r, k)) continue;    // ขอบซ้ายคู่ขอบขวา
cur[r][c] = 1;

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

// แฮชโมดูโล 2^61 - 1 คูณกันแล้วพับด้วยบิต ไม่ต้องหารเลย
const ull MOD = (1ULL << 61) - 1;
static inline ull add(ull a, ull b) { a += b; if (a >= MOD) a -= MOD; return a; }
static inline ull sub(ull a, ull b) { return add(a, MOD - b); }
static inline ull mul(ull a, ull b) {
    __uint128_t c = (__uint128_t)a * b;
    return add((ull)(c & MOD), (ull)(c >> 61));
}

int R, C;
ull B;
vector<ull> pw;
vector<vector<ull>> hRow, hRowRev, hCol, hColRev;

// แฮชนำหน้าของทุกบรรทัดในชุดที่ให้มา
static void build(vector<vector<ull>>& h, const vector<string>& s) {
    int n = s.size(), m = s[0].size();
    h.assign(n, vector<ull>(m + 1, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            h[i][j + 1] = add(mul(h[i][j], B), (ull)(s[i][j] - '0' + 1));
}
static inline ull cut(const vector<vector<ull>>& h, int i, int l, int len) {
    return sub(h[i][l + len], mul(h[i][l], pw[len]));
}

int main() {
    scanf("%d %d", &R, &C);
    vector<string> row(R);
    for (int i = 0; i < R; i++) { char buf[512]; scanf("%s", buf); row[i] = buf; }

    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    B = rng() % (MOD - 300) + 256;                  // ฐานสุ่ม กันคนแต่งอินพุตมาชนแฮช
    pw.assign(max(R, C) + 1, 1);
    for (size_t i = 1; i < pw.size(); i++) pw[i] = mul(pw[i - 1], B);

    // เตรียมสี่ชุด: แถวปกติ แถวกลับด้าน คอลัมน์ปกติ คอลัมน์กลับด้าน
    vector<string> rowRev(R), col(C, string(R, '0')), colRev(C);
    for (int i = 0; i < R; i++) { rowRev[i] = row[i]; reverse(rowRev[i].begin(), rowRev[i].end()); }
    for (int j = 0; j < C; j++) {
        for (int i = 0; i < R; i++) col[j][i] = row[i][j];
        colRev[j] = col[j];
        reverse(colRev[j].begin(), colRev[j].end());
    }
    build(hRow, row); build(hRowRev, rowRev); build(hCol, col); build(hColRev, colRev);

    // ขอบบนช่วง [c, c+k-1] ต้องเท่ากับขอบล่างช่วงเดียวกัน "อ่านกลับด้าน"
    // ช่วงกลับด้านของ [c, c+k-1] ในสตริงที่กลับแล้ว คือ [C-c-k, C-c-1]
    auto rowFit = [&](int u, int v, int c, int k) {
        return cut(hRow, u, c, k) == cut(hRowRev, v, C - c - k, k);
    };
    auto colFit = [&](int a, int b, int r, int k) {
        return cut(hCol, a, r, k) == cut(hColRev, b, R - r - k, k);
    };

    int K = min(R, C);
    // สองชั้นที่ต้องเก็บคือ k-1 กับ k-2 เท่านั้น จัตุรัสด้าน 0 กับ 1 สมมาตรเสมอ
    vector<vector<char>> two(R, vector<char>(C, 1));
    vector<vector<char>> one(R, vector<char>(C, 1));
    int ans = -1;
    for (int k = 2; k <= K; k++) {
        vector<vector<char>> cur(R, vector<char>(C, 0));
        for (int r = 0; r + k <= R; r++)
            for (int c = 0; c + k <= C; c++) {
                if (!two[r + 1][c + 1]) continue;             // ไส้ในด้าน k-2 ต้องผ่านก่อน
                if (!rowFit(r, r + k - 1, c, k)) continue;    // ขอบบนคู่ขอบล่าง
                if (!colFit(c, c + k - 1, r, k)) continue;    // ขอบซ้ายคู่ขอบขวา
                cur[r][c] = 1;
                ans = k;
            }
        two = one;
        one = cur;
    }
    printf("%d\n", ans);
    return 0;
}

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

int main() {
    int R, C;
    scanf("%d %d", &R, &C);
    vector<string> g(R);
    for (auto& s : g) { char b[512]; scanf("%s", b); s = b; }

    int ans = -1;
    for (int k = 2; k <= min(R, C); k++)
        for (int r = 0; r + k <= R; r++)
            for (int c = 0; c + k <= C; c++) {
                bool ok = true;
                for (int i = 0; i < k && ok; i++)
                    for (int j = 0; j < k && ok; j++)
                        if (g[r + i][c + j] != g[r + k - 1 - i][c + k - 1 - j]) ok = false;
                if (ok) ans = max(ans, k);
            }
    printf("%d\n", ans);
}

แกะตัวอย่างที่ตอบ -1

ทางที่ไม่มีโอกาสชนเลย · Manacher

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

สำหรับคำถามเรื่องพาลินโดรม มีท่าที่ตอบได้เร็วเท่ากันโดยไม่มีโอกาสผิดเลย ชื่อ Manacher (อ่านว่า "มานาเชอร์" ตามชื่อคนคิด) มันคำนวณ รัศมีของพาลินโดรมที่ยาวที่สุดของทุกจุดศูนย์กลาง ในเวลาเชิงเส้น โดยเทียบตัวอักษรจริงทั้งหมด ไม่มีตัวเลขตัวแทนที่อาจชนกัน

มันมีสองท่าที่ต้องรู้ ท่าแรกคือการแทรกตัวคั่น พาลินโดรมมีสองแบบ คือความยาวคี่ที่มีตัวกลางหนึ่งตัว และความยาวคู่ที่ศูนย์กลางอยู่ระหว่างตัวอักษร การเขียนโค้ดแยกสองกรณีคือแหล่งบั๊กชั้นดี ท่าแก้คือแทรกตัวคั่นระหว่างทุกตัวอักษรและที่หัวท้าย ทุกพาลินโดรมในสตริงใหม่จะมีความยาวคี่เสมอ เหลือกรณีเดียว

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

// Manacher: หาความยาวพาลินโดรมที่ยาวที่สุด และรัศมีของทุกจุดศูนย์กลาง
// ไม่ใช้แฮชเลย จึงไม่มีโอกาสชนกัน
// อินพุต: สตริงหนึ่งบรรทัด   เอาต์พุต: ความยาวพาลินโดรมที่ยาวที่สุด
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    if (!(cin >> s)) return 0;
    // แทรกตัวคั่นเพื่อรวมกรณีความยาวคู่กับคี่เป็นกรณีเดียว
    string t = "#";
    for (char c : s) { t += c; t += '#'; }
    int n = (int)t.size();
    vector<int> rad(n, 0);
    int l = 0, r = -1;                  // ช่วงพาลินโดรมที่ขวาสุดที่รู้แล้ว
    for (int i = 0; i < n; i++) {
        int k = (i > r) ? 1 : min(rad[l + r - i], r - i + 1);   // ใช้ภาพสะท้อนของของเก่า
        while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++;
        rad[i] = k--;
        if (i + k > r) { l = i - k; r = i + k; }
    }
    int best = 0;
    for (int i = 0; i < n; i++) best = max(best, rad[i] - 1);
    printf("%d\n", best);
    return 0;
}

// ตัวตรวจอิสระของ Manacher: ลองทุกช่วงแล้วเช็คว่าเป็นพาลินโดรมไหมตรง ๆ
// ไม่รู้จักการใช้ภาพสะท้อนของของเก่าเลย
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    if (!(cin >> s)) return 0;
    int n = (int)s.size(), best = 0;
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) {
            bool ok = true;
            for (int a = i, b = j; a < b && ok; a++, b--) if (s[a] != s[b]) ok = false;
            if (ok) best = max(best, j - i + 1);
        }
    printf("%d\n", best);
    return 0;
}

เกณฑ์เลือกระหว่างสองทางในข้อนี้ ถ้าคำถามเป็นเรื่องพาลินโดรมล้วน ๆ ให้ใช้ Manacher เพราะไม่มีความเสี่ยง แต่โจทย์นี้ไม่ได้ถามพาลินโดรมของสตริงเดียว มันถามเรื่องตารางสองมิติที่หมุน 180 องศาแล้วเหมือนเดิม ซึ่งเทียบสองช่วงใดก็ได้ในตารางที่เปลี่ยนไปเรื่อย ๆ นั่นคือสิ่งที่แฮชทำได้และ Manacher ทำไม่ได้ตรง ๆ จึงเลือกแฮชเป็นท่าหลัก แล้วจ่ายค่าความเสี่ยงด้วยการเลือกมอดุลัสให้ดี

สรุปบรรทัดเดียว

การหมุน 180 องศาไม่เคยพาช่องข้ามวง จัตุรัสด้าน k จึงเท่ากับจัตุรัสด้าน k - 2 ที่อยู่ข้างในบวกวงนอกหนึ่งวง และวงนอกหนึ่งวงคือการเทียบสตริงสองคู่ ซึ่งแฮชนำหน้าตอบให้ได้ในเวลาคงที่

แหล่งที่มา

1. โจทย์ Killer บน programming.in.th ข้อ 2006 programming.in.th/tasks/2006 (สืบค้น 6 กันยายน 2026)
2. ต้นทางของโจทย์คือ Croatian Open Competition in Informatics คอนเทสต์ที่ 1 ฤดูกาล 2006/2007 แข่งวันที่ 28 ตุลาคม 2006