ปูพื้นฐาน

นับก่อน แล้วค่อยเดิน: หาตัวที่ R ในกองที่ใหญ่เกินจะสร้างจริง

โจทย์ที่ขอ "ตัวที่ R ตามพจนานุกรม" กับโจทย์ที่ขอ "อันดับของตัวนี้" เป็นโค้ดชุดเดียวกันที่ต่างกันแค่ทิศทาง บทนี้ให้แม่พิมพ์นั้น พร้อมสองบักที่เกิดกับทุกคนอย่างน้อยครั้งหนึ่ง

ปัญหาที่บทนี้แก้

โจทย์ตระกูลนี้ถามอยู่สองแบบ ซึ่งเป็นคำถามกลับด้านกัน

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

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

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

ขั้นที่ 1 นับ

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

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

ขั้นที่ 2 เดิน

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

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

ลองเอง · เดินไปหาสตริงอันดับที่ขอ

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

โจทย์ฝึกข้อที่ 1 · สตริงฐานสองที่ไม่มีเลขหนึ่งติดกัน ตัวที่ R

หาสตริงฐานสองยาว n ที่ไม่มีเลข 1 อยู่ติดกัน ตัวที่ R ตามลำดับพจนานุกรม (โดย 0 มาก่อน 1) ถ้ามีไม่ถึง R ตัวให้ตอบ -1

เฉลยข้อที่ 1

// สตริงฐานสองยาว n ที่ไม่มีเลข 1 ติดกัน  ตัวที่ R ตามลำดับพจนานุกรม
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int main() {
    int n; ull R;
    scanf("%d %llu", &n, &R);
    // f[i][last] = จำนวนวิธีเติมตำแหน่ง i..n-1 เมื่อตัวก่อนหน้าคือ last
    vector<array<ull,2>> f(n + 1);
    f[n][0] = f[n][1] = 1;
    for (int i = n - 1; i >= 0; i--) {
        f[i][0] = f[i + 1][0] + f[i + 1][1];   // ตัวก่อนเป็น 0 ใส่ได้ทั้ง 0 และ 1
        f[i][1] = f[i + 1][0];                 // ตัวก่อนเป็น 1 ใส่ได้แค่ 0
    }
    if (R > f[0][0]) { printf("-1\n"); return 0; }
    string out; int last = 0;
    for (int i = 0; i < n; i++) {
        for (int b = 0; b <= 1; b++) {         // ไล่ 0 ก่อน 1 ตามพจนานุกรม
            if (b == 1 && last == 1) continue;
            ull cnt = f[i + 1][b];
            if (R <= cnt) { out.push_back('0' + b); last = b; break; }
            R -= cnt;
        }
    }
    printf("%s\n", out.c_str());
}

โจทย์ฝึกข้อที่ 2 · อันดับของการเรียงสับเปลี่ยน

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

เฉลยข้อที่ 2

// อันดับของการเรียงสับเปลี่ยนตามพจนานุกรม  (สมาชิกคือ 1..n ไม่ซ้ำ)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int main() {
    int n; scanf("%d", &n);
    vector<int> p(n);
    for (auto& v : p) scanf("%d", &v);
    vector<ull> fact(n + 1, 1);
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
    vector<char> used(n + 2, 0);
    ull rank_ = 1;
    for (int i = 0; i < n; i++) {
        int smaller = 0;                        // ตัวที่ยังไม่ถูกใช้และเล็กกว่า p[i]
        for (int v = 1; v < p[i]; v++) if (!used[v]) smaller++;
        rank_ += (ull)smaller * fact[n - i - 1];
        used[p[i]] = 1;
    }
    printf("%llu\n", rank_);
}

อีกท่าหนึ่งของคำถามเดียวกัน · เมื่อของที่ต้องเรียงไม่มีลำดับตามธรรมชาติ

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

แต่มีโจทย์ "ขออันดับที่ k" อีกตระกูลที่ของไม่มีโครงแบบนั้นเลย เช่น ผลบวกของทุกคู่ในอาเรย์ ที่เล็กเป็นอันดับที่ k ผลบวกไม่ได้ประกอบขึ้นทีละหลัก มันเป็นเพียงตัวเลข และมีทั้งหมด n(n-1)/2 ตัว ซึ่งที่ n = 200,000 คือราวสองหมื่นล้านตัว สร้างทั้งกองไม่ได้

ท่าที่ใช้ตรงนี้คือค้นหาคำตอบแบบไบนารี คู่กับการนับ ซึ่งกลับทิศของคำถามทั้งหมด แทนที่จะถามว่า "อันดับที่ k คือค่าอะไร" ให้ถามว่า

ถ้าคำตอบคือ x จะมีของกี่ชิ้นที่ไม่เกิน x

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

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

// ค้นหาคำตอบแบบไบนารีคู่กับการนับ: หาผลบวก a[i]+a[j] (i<j) ที่เล็กเป็นอันดับที่ k
// ไม่ต้องสร้างผลบวกทั้ง n(n-1)/2 ตัวเลย
// อินพุต: n k แล้วอาเรย์ n ตัว   เอาต์พุต: ค่าผลบวกอันดับที่ k (นับจาก 1)
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; long long k;
    if (scanf("%d %lld", &n, &k) != 2) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
    sort(a.begin(), a.end());

    // นับว่ามีผลบวกกี่คู่ที่ไม่เกิน x ด้วยสองตัวชี้ ซึ่งเป็น O(n) ต่อการนับหนึ่งครั้ง
    auto countLE = [&](long long x) {
        long long c = 0;
        int j = n - 1;
        for (int i = 0; i < n; i++) {
            if (j <= i) j = i;                       // ไม่ให้ตัวชี้ขวาแซงมาซ้ายกว่าตัวชี้ซ้าย
            while (j > i && a[i] + a[j] > x) j--;
            if (j > i) c += j - i;                   // คู่ (i, i+1..j) ผ่านทั้งหมด
        }
        return c;
    };

    long long lo = a[0] + a[1], hi = a[n - 1] + a[n - 2];
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;          // ระวังการปัดของเลขลบ ใช้รูปนี้จึงปลอดภัย
        if (countLE(mid) >= k) hi = mid;
        else lo = mid + 1;
    }
    printf("%lld\n", lo);
    return 0;
}

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

int main() {
    int n; long long k;
    if (scanf("%d %lld", &n, &k) != 2) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
    vector<long long> all;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) all.push_back(a[i] + a[j]);
    sort(all.begin(), all.end());
    printf("%lld\n", all[k - 1]);
    return 0;
}

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

เอาไปใช้ที่ไหนในคลังนี้

• สวนหลวงที่ต้องสมดุลทุกช่วง เป็นแบบ "ขออันดับ" โดยของยากอยู่ที่การบีบสถานะให้เหลือหกแบบ
• ลำดับ DNA ตัวที่ R เป็นแบบ "ขอตัวที่ R" โดยของยากอยู่ที่การแปลนิยามที่เรียกตัวเองให้เป็นการนับรอยต่อ

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

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

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