programming.in.th · ข้อ 2015

ใบเรือโจรสลัด: ฟังก์ชันนูนบอกคำตอบไปแล้ว เหลือแค่ใครได้เลือกก่อน

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

โจทย์ · ใบเรือที่บังลมกันเอง

เรือโจรสลัดลำใหม่มีเสา N ต้น เรียงจากหัวเรือไปท้ายเรือ เสาต้นที่ i สูง H ช่อง และต้องติดใบเรือ K ใบ โดยหนึ่งช่องติดได้ไม่เกินหนึ่งใบ เราเลือกได้ว่าจะติดใบไหนที่ระดับไหนของเสาต้นนั้น

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

สังเกตจุดที่ทำให้โจทย์ง่ายลงเยอะทันที ถ้าระดับหนึ่งมีใบเรืออยู่ c ใบ ผลรวมของระดับนั้นคือ จำนวนคู่ที่จับได้จาก c ใบ นั่นคือ c × (c − 1) / 2 โดยไม่เกี่ยวกับลำดับหัวท้ายเลย เพราะทุกคู่ในระดับเดียวกันย่อมมีตัวหนึ่งอยู่หน้าอีกตัวหนึ่งอยู่แล้ว

คำถามจึงเหลือแค่ ให้แจกใบเรือลงระดับต่าง ๆ โดยเสาต้นที่ i แจกได้เฉพาะระดับ 1 ถึง H และแจกได้ระดับละไม่เกินหนึ่งใบ จะทำยังไงให้ผลรวมของ c × (c − 1) / 2 ทุกระดับน้อยที่สุด

ลองเอง · วางใบเรือให้เสียแต้มน้อยที่สุด

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

เฉลย · ใส่ลงกองที่ว่างที่สุดเสมอ และไล่จากเสาที่เตี้ยที่สุด

long long v = at(H - K + 1);            // ค่าที่ระดับตัวที่ K นับจากท้ายช่วง [1..H]
// [l, r] = บล็อกของระดับที่มีค่าเท่ากับ v พอดี หาแบบไบนารีได้เพราะอาเรย์ไม่มีทางเพิ่มขึ้น
int below = H - r;                      // ระดับที่ค่าน้อยกว่า v อยู่ท้ายสุด ใส่ก่อนทั้งหมด
range(r + 1, H, 1);
int k2 = K - below;                     // ที่เหลือหยิบจาก "หัว" ของบล็อก ไม่ใช่ท้าย
if (k2 > 0) range(l, l + k2 - 1, 1);

ไล่ท่าโลภทีละเสาบนตัวอย่าง

อีกมุมหนึ่ง: ไล่ทุกวิธีจัด (ชุดทดสอบย่อย 25 คะแนน)

// เฉลยชุดทดสอบย่อย จำนวนวิธีจัดใบเรือทั้งหมดไม่เกินหนึ่งล้านแบบ (25 คะแนน)
// ไล่ทุกวิธีจัดจริง ๆ แล้วเก็บค่าที่น้อยที่สุด ไม่ต้องรู้อะไรเรื่องความโลภเลย
#include <bits/stdc++.h>
using namespace std;
int n, MX;
vector<int> H, K, cnt;
long long best = LLONG_MAX;

void rec(int i) {
    if (i == n) {
        long long v = 0;
        for (int c : cnt) v += 1LL * c * (c - 1) / 2;      // คู่ที่อยู่ระดับเดียวกัน
        best = min(best, v);
        return;
    }
    vector<int> pick(H[i], 0);
    fill(pick.begin(), pick.begin() + K[i], 1);
    sort(pick.begin(), pick.end());                        // เริ่มจากรูปแบบที่เล็กที่สุดของ next_permutation
    do {
        for (int h = 0; h < H[i]; h++) if (pick[h]) cnt[h]++;
        rec(i + 1);
        for (int h = 0; h < H[i]; h++) if (pick[h]) cnt[h]--;
    } while (next_permutation(pick.begin(), pick.end()));
}

int main() {
    scanf("%d", &n);
    H.resize(n); K.resize(n); MX = 0;
    for (int i = 0; i < n; i++) { scanf("%d %d", &H[i], &K[i]); MX = max(MX, H[i]); }
    cnt.assign(MX, 0);
    rec(0);
    printf("%lld\n", best);
}

โค้ด C++

#include <bits/stdc++.h>
using namespace std;
int MX; vector<long long> bit;                 // BIT แบบ range-update / point-query
void upd(int i,long long v){ for(;i<=MX;i+=i&-i) bit[i]+=v; }
void range(int l,int r,long long v){ if(l>r) return; upd(l,v); upd(r+1,-v); }
long long at(int i){ long long s=0; for(;i>0;i-=i&-i) s+=bit[i]; return s; }
int main(){
    int n; if(scanf("%d",&n)!=1) return 0;
    vector<pair<int,int>> m(n);
    for(auto&p:m) scanf("%d %d",&p.first,&p.second);
    sort(m.begin(),m.end());
    MX=m.back().first; bit.assign(MX+2,0);
    for(auto&[H,K]:m){
        long long v=at(H-K+1);
        // [l,r] = ช่วงใน [1..H] ที่ค่าเท่ากับ v พอดี (อาเรย์ไม่เพิ่ม จึงค้นแบบไบนารีได้)
        int l=1,r=H,lo,hi;
        lo=1; hi=H; int first=H+1;
        while(lo<=hi){ int md=(lo+hi)/2; if(at(md)<=v){ first=md; hi=md-1; } else lo=md+1; }
        l=first;
        lo=1; hi=H; int last=0;
        while(lo<=hi){ int md=(lo+hi)/2; if(at(md)>=v){ last=md; lo=md+1; } else hi=md-1; }
        r=last;
        int below=H-r;                 // ช่องที่ค่าน้อยกว่า v อยู่ท้ายสุด เติมก่อนทั้งหมด
        range(r+1,H,1);
        int k2=K-below;                // ที่เหลือหยิบจาก "หัว" ของบล็อกค่าเท่ากับ v
        if(k2>0) range(l,l+k2-1,1);
    }
    long long ans=0;
    for(int i=1;i<=MX;i++){ long long c=at(i); ans+=c*(c-1)/2; }
    printf("%lld\n",ans);
}

int below = H - r;                     // ระดับที่ค่าน้อยกว่า v อยู่ท้ายสุด ใส่ก่อนทั้งหมด
range(r + 1, H, 1);
int k2 = K - below;
if (k2 > 0) range(r - k2 + 1, r, 1);   // <-- บรรทัดที่ผิด หยิบจากท้ายบล็อก
                                       // ของจริงคือ range(l, l + k2 - 1, 1)

2
2 1
2 1

ทำไมท่าโลภนี้ถูก · ข้อโต้แย้งแลกเปลี่ยน

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

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

ใช้กับข้อนี้

แต้มที่เสียของระดับหนึ่งคือจำนวนคู่ของใบเรือที่อยู่ระดับเดียวกัน ซึ่งเท่ากับ c(c−1)/2 เมื่อระดับนั้นมีใบอยู่ c ใบ สิ่งที่ต้องสังเกตคือ ต้นทุนของการเพิ่มใบที่ c + 1 คือ c พอดี คือยิ่งระดับนั้นแน่นอยู่แล้ว ใบใหม่ยิ่งแพง เรียกคุณสมบัตินี้ว่าต้นทุนส่วนเพิ่มไม่ลด

ทีนี้สมมติมีคำตอบที่ดีที่สุดอันหนึ่ง ที่ไม่ได้ทำตามท่าโลภ นั่นแปลว่ามีเสาต้นหนึ่ง ที่วางใบลงระดับ p ทั้งที่มีระดับ q ที่มันเอื้อมถึงและว่างกว่า (คือ cnt[q] < cnt[p]) ลองย้ายใบนั้นจาก p ไป q ต้นทุนที่ลดลงคือ cnt[p] − 1 และต้นทุนที่เพิ่มขึ้นคือ cnt[q] เพราะ cnt[q] ≤ cnt[p] − 1 การย้ายนี้จึงไม่ทำให้แย่ลงเลย

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

เขียนอีกแบบ · คิวลำดับความสำคัญ

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

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

// ท่าโลภของโจทย์ใบเรือ เขียนด้วยคิวลำดับความสำคัญ
// ไล่เสาจากเตี้ยไปสูง แต่ละเสาหย่อนใบลงระดับที่ "ว่างที่สุด" ในระยะที่มันเอื้อมถึง
// อินพุต: n แล้ว n บรรทัด h k    เอาต์พุต: แต้มที่เสียน้อยที่สุด
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<pair<int, int>> m(n);
    int H = 0;
    for (int i = 0; i < n; i++) { scanf("%d %d", &m[i].first, &m[i].second); H = max(H, m[i].first); }
    sort(m.begin(), m.end());                 // เตี้ยก่อน เพราะเสาเตี้ยมีตัวเลือกน้อยกว่า

    vector<int> cnt(H + 1, 0);                // cnt[l] = จำนวนใบที่ระดับ l (ระดับนับ 1..H)
    // คิวเก็บ (จำนวนใบตอนนี้, ระดับ) โดยเอาน้อยสุดขึ้นก่อน ค่าเท่ากันเอาระดับล่างก่อน
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    int opened = 0;                           // ระดับที่ปล่อยให้ใช้ได้แล้ว
    for (auto [h, k] : m) {
        while (opened < h) { ++opened; pq.push({cnt[opened], opened}); }
        // หยิบ k ระดับที่ว่างที่สุดออกมา แล้วใส่กลับพร้อมค่าที่เพิ่มขึ้น
        vector<int> picked;
        picked.reserve(k);
        for (int t = 0; t < k; t++) {
            // ค่าในคิวอาจเก่า ถ้าไม่ตรงกับ cnt จริงให้ทิ้งแล้วหยิบใหม่
            while (!pq.empty() && pq.top().first != cnt[pq.top().second]) pq.pop();
            auto [c, lv] = pq.top();
            pq.pop();
            cnt[lv] = c + 1;
            picked.push_back(lv);
        }
        for (int lv : picked) pq.push({cnt[lv], lv});
    }
    long long cost = 0;
    for (int l = 1; l <= H; l++) cost += (long long)cnt[l] * (cnt[l] - 1) / 2;
    printf("%lld\n", cost);
    return 0;
}

// ตัวตรวจอิสระของท่าโลภใบเรือ: ไล่ทุกวิธีจัดจริง
// ไม่รู้จักคำว่า "ว่างที่สุด" หรือลำดับเตี้ยไปสูงเลย จึงตรวจข้ออ้างของท่าโลภได้จริง
#include <bits/stdc++.h>
using namespace std;

int n, H;
vector<pair<int, int>> m;
vector<int> cnt;
long long best;

long long costNow() {
    long long c = 0;
    for (int l = 1; l <= H; l++) c += (long long)cnt[l] * (cnt[l] - 1) / 2;
    return c;
}

/** เลือก k ระดับจาก 1..h แบบไล่ทุกชุด */
void choose(int mast, int start, int left) {
    if (left == 0) {
        if (mast + 1 == n) best = min(best, costNow());
        else {
            int h = m[mast + 1].first, k = m[mast + 1].second;
            (void)h;
            choose(mast + 1, 1, k);
        }
        return;
    }
    int h = m[mast].first;
    for (int lv = start; lv <= h; lv++) {
        cnt[lv]++;
        choose(mast, lv + 1, left - 1);
        cnt[lv]--;
    }
}

int main() {
    if (scanf("%d", &n) != 1) return 0;
    m.resize(n);
    H = 0;
    for (int i = 0; i < n; i++) { scanf("%d %d", &m[i].first, &m[i].second); H = max(H, m[i].first); }
    cnt.assign(H + 1, 0);
    best = LLONG_MAX;
    choose(0, 1, m[0].second);
    printf("%lld\n", best);
    return 0;
}

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

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

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

แหล่งที่มา

1. โจทย์ Sails บน programming.in.th ข้อ 2015 programming.in.th/tasks/2015 (สืบค้น 6 กันยายน 2026)
2. ต้นทางของโจทย์คือ 19th International Olympiad in Informatics ที่เมืองซาเกร็บ ประเทศโครเอเชีย วันแข่งที่ 1