21.1 นับก่อนลอง

โจทย์ค่ายจำนวนมากเขียนวิธีฉลาดๆ ได้ยาก แต่คำตอบที่เป็นไปได้มีจำกัด เช่น เลือกขนมสามชิ้นจากร้านที่มีร้อยชิ้น จัดลำดับเพื่อนแปดคน เลือกของบางชิ้นจากยี่สิบชิ้น วิธีที่ตรงที่สุดคือลองทุกคำตอบ ตรวจทีละแบบ แล้วเก็บแบบที่ถูกหรือดีที่สุด เรียกว่า brute force หรือ exhaustive search (การค้นหาแบบถี่ถ้วน) วิธีนี้ถูกแน่นอนถ้าลองครบ คำถามมีแค่ว่าทันเวลาไหม หน้านี้สอนให้นับก่อนเขียน และเขียนตัวไล่ด้วยลูปซ้อนให้ครบโดยไม่ซ้ำ

สามขั้นก่อนลองทุกแบบ

1. คำตอบหนึ่งแบบหน้าตาเป็นยังไง เช่น ขนมสามชิ้นคือเลขตำแหน่งสามตัว i j k การจัดลำดับคือการเรียงสับเปลี่ยนหนึ่งแบบ ชุดของคำตอบทั้งหมดที่ต้องไล่เรียกว่า search space (ปริภูมิการค้นหา)
2. มีกี่แบบ และตรวจหนึ่งแบบใช้งานเท่าไร คูณกันแล้วเทียบกับราว 10⁸ ครั้งต่อวินาทีที่วัดไว้ในหน้า 4.5 ถ้าเกินไปมาก ไม่ต้องเขียน ไปหาวิธีอื่นก่อน
3. ไล่ยังไงให้ครบและไม่ซ้ำ ขาดไปแบบเดียวอาจตอบผิด นับซ้ำก็ตอบผิดเหมือนกันในโจทย์ที่ถามว่ามีกี่แบบ

ขั้นที่ 2 คือขั้นที่คนข้ามบ่อยที่สุด เขียนเสร็จแล้วค่อยรู้ว่าต้องรันเป็นชั่วโมง เสียเวลาสอบไปฟรีๆ

ลูปซ้อนเมื่อเลือกของจำนวนตายตัว

ห้องเรียนมีไม้ N อัน ยาวไม่เท่ากัน เลือกไม้สามอันต่อเป็นสามเหลี่ยมได้กี่แบบ ไม้สามอันยาว a b c ต่อเป็นสามเหลี่ยมได้ก็ต่อเมื่อผลรวมของสองด้านใดๆ ยาวกว่าด้านที่เหลือ คำตอบหนึ่งแบบคือไม้สามอันที่ต่างกัน จึงใช้ลูปสามชั้น

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

int main()
{
    int n;
    cin >> n;
    vector<int> stick(n);
    for (int i = 0; i < n; i++) {
        cin >> stick[i];
    }
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) { // (1)!
            for (int k = j + 1; k < n; k++) {
                int a = stick[i], b = stick[j], c = stick[k];
                if (a + b > c && a + c > b && b + c > a) {
                    cout << a << ' ' << b << ' ' << c << '\n';
                    count++;
                }
            }
        }
    }
    cout << "total " << count << '\n';
    return 0;
}

1. j เริ่มที่ i + 1 และ k เริ่มที่ j + 1 บังคับให้ i < j < k ไม้สามอันจึงต่างกันเสมอ และไม้ชุดเดียวกันถูกนับแค่ครั้งเดียว ไม่นับ (2, 3, 4) กับ (3, 2, 4) เป็นสองแบบ

5
2 3 4 5 9

2 3 4
2 4 5
3 4 5
total 3

ไม้ 2 3 5 ใช้ไม่ได้เพราะ 2 + 3 เท่ากับ 5 พอดี ต่อแล้วแบนเป็นเส้นตรง ส่วนไม้ยาว 9 ใช้ไม่ได้เลย เพราะสองอันที่ยาวที่สุดที่เหลือคือ 4 + 5 ก็ยังไม่เกิน 9

นับจำนวนแบบก่อนว่าทันไหม เลือกสามอันจาก N อันได้ C(N, 3) = N(N - 1)(N - 2) / 6 แบบ ตรวจหนึ่งแบบใช้งานไม่กี่ครั้ง

เงื่อนไข i < j < k ทำให้ลูปสามชั้นทำงานแค่ราวหนึ่งในหกของ N³ แต่ในแง่ Big O ยังเป็น O(N³) เท่าเดิม ถ้าเลือกสี่อันก็ซ้อนสี่ชั้น แต่ถ้าจำนวนที่เลือกเป็นตัวแปรที่รับเข้ามา ลูปซ้อนใช้ไม่ได้ ต้องใช้ bitmask หรือ recursion ในหน้า 21.2 และ 21.3

ตัดลูปชั้นในที่คำนวณได้

แม่แบ่งลูกอม N เม็ดให้ลูกสามคน ทุกคนต้องได้อย่างน้อย 1 เม็ด และไม่มีใครได้เกิน L เม็ด แบ่งได้กี่แบบ ถ้าคนที่หนึ่งได้ a คนที่สองได้ b คนที่สามได้ c คำตอบหนึ่งแบบคือ (a, b, c) ที่ a + b + c = N ลองตรงๆ คือวนทั้งสามตัว

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

int main()
{
    int n, limit;
    cin >> n >> limit;
    long long ways = 0;
    for (int a = 1; a <= limit; a++) {
        for (int b = 1; b <= limit; b++) {
            for (int c = 1; c <= limit; c++) {
                if (a + b + c == n) {
                    ways++;
                }
            }
        }
    }
    cout << ways << '\n';
    return 0;
}

10 4

6

ลูกอม 10 เม็ด ไม่เกินคนละ 4 ได้ 6 แบบ คือ (2, 4, 4) กับ (3, 3, 4) อย่างละสามลำดับ แต่ลูปนี้ลองถึง L³ แบบ ทั้งที่แบบส่วนใหญ่ผลรวมไม่ใช่ N เลย สังเกตว่าพอรู้ a กับ b แล้ว c ถูกบังคับให้เป็น N - a - b ไม่มีทางเลือกอื่น ลูปชั้นในสุดจึงทำงานฟรีเกือบทุกรอบ เปลี่ยนเป็นคำนวณ c แล้วตรวจว่าอยู่ในช่วงที่ใช้ได้

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

int main()
{
    int n, limit;
    cin >> n >> limit;
    long long ways = 0;
    for (int a = 1; a <= limit; a++) {
        for (int b = 1; b <= limit; b++) {
            int c = n - a - b;
            if (c >= 1 && c <= limit) {
                ways++;
            }
        }
    }
    cout << ways << '\n';
    return 0;
}

10 4

6

จาก O(L³) เหลือ O(L²) ทดลองกับ N = 1.5L ซึ่งมีคำตอบเยอะ วัดบนโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 Windows 11 คอมไพล์ด้วย GCC 14.2 ของ Code::Blocks ทั้งแบบ Code::Blocks (-Wall อย่างเดียว) และแบบ -O2 แต่ละช่องคือค่ากลางของการรัน 5 ครั้ง นับรวมเวลาเปิดโปรแกรมราว 0.02 วินาที

ลูปสามชั้นที่ L = 1000 ทำงานถึง 10⁹ รอบแต่ใช้แค่ 0.35 วินาทีแบบ -O2 เพราะงานในลูปเบามากและ compiler ปรับให้เร็วได้ อย่าไว้ใจตัวเลขนี้กับงานที่หนักกว่า ส่วน L = 2000 ไม่ทันแน่นอน แบบสองชั้นทำงานแค่ 4 × 10⁶ รอบ เร็วจนเวลาที่วัดได้เกือบทั้งหมดคือเวลาเปิดโปรแกรม

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

ดูขอบเขตแล้วเดาวิธี

บทที่ 18 มีตารางขอบเขตครบทุกแบบแล้ว หน้านี้ขยายเฉพาะแถวบนๆ ที่เป็นเรื่องลองทุกแบบ ตัวเลขในคอลัมน์ที่สองคือจำนวนแบบจริง ส่วนงานต่อแบบให้คูณเพิ่มเอง

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

brute force ไว้ตรวจวิธีเร็ว

แม้โจทย์จะให้ N ใหญ่จน brute force ไม่ทัน ก็ยังควรเขียนไว้ เพราะมันเขียนง่ายและถูกแน่ เอาไว้เทียบกับวิธีเร็วที่เราไม่มั่นใจ สุ่มข้อมูลเข้าขนาดเล็กหลายร้อยชุด รันทั้งสองโปรแกรม ถ้าคำตอบไม่ตรงกันเมื่อไร ก็ได้ชุดข้อมูลเล็กๆ ที่ทำให้วิธีเร็วผิดมาไล่หาบั๊ก วิธีนี้เรียกว่า stress test ไฟล์ naive.cpp ในแบบฝึกหัดของเว็บนี้ก็มีไว้ทำหน้าที่นี้ ตัวตรวจรันมันกับชุดทดสอบเล็กทุกชุด เพื่อยืนยันว่าเฉลยกับวิธีช้าตอบตรงกัน

ลองทำให้พัง

ลูปชั้นในเริ่มที่ 0

ในโปรแกรม triangle เปลี่ยน int j = i + 1 เป็น int j = 0 และ int k = j + 1 เป็น int k = 0 คอมไพล์ผ่านโดยไม่มีคำเตือน ป้อนไม้ชุดเดิม โปรแกรมพิมพ์ 69 บรรทัด เป็นไม้สามอัน 68 บรรทัดกับบรรทัด total อีกหนึ่งบรรทัด ห้าบรรทัดแรกคือ

2 2 2
2 2 3
2 3 2
2 3 3
2 3 4

และบรรทัดสุดท้ายคือ total 68 แทนที่จะเป็น 3 ผิดสองชั้น ชั้นแรก หยิบไม้อันเดิมซ้ำได้ 2 2 2 คือใช้ไม้ยาว 2 อันเดียวกันสามครั้ง ซึ่งไม่มีอยู่จริง ชั้นที่สอง ไม้ชุดเดียวกันถูกนับหลายครั้งตามลำดับที่หยิบ (2, 3, 4) โผล่มาครบหกลำดับ ถ้าโจทย์ถามว่ามีกี่แบบ ต้องบังคับให้ไล่แบบละครั้งเดียว ทางที่ง่ายที่สุดคือบังคับลำดับ i < j < k แบบโปรแกรมต้นฉบับ

สรุป

• brute force คือลองทุกคำตอบที่เป็นไปได้ ถูกแน่ถ้าลองครบ ปัญหามีแค่เรื่องเวลา
• ก่อนเขียน นับจำนวนแบบคูณงานต่อแบบ แล้วเทียบกับราว 10⁸ ต่อวินาที
• เลือกของจำนวนตายตัวใช้ลูปซ้อน บังคับ i < j < k ให้ได้แบบละครั้งเดียวและไม่หยิบซ้ำ
• ถ้าตัวแปรตัวสุดท้ายถูกบังคับด้วยเงื่อนไข ให้คำนวณแทนการวน ลดไปได้หนึ่งชั้น
• N ≤ 10 มักเป็น N! N ≤ 20 มักเป็น 2^N N ≤ 40 มักเป็น meet in the middle
• เก็บ brute force ไว้ตรวจวิธีเร็วด้วยข้อมูลสุ่มขนาดเล็ก