เทคนิค C++ ที่น่ารู้สำหรับมือใหม่ในการแข่งขันเขียนโปรแกรม (Competitive Programming)

บทความนี้รวบรวมเทคนิค C++ ที่มีประโยชน์สำหรับการแข่งขันเขียนโปรแกรม (Competitive Programming) ช่วยลดเวลาเขียนโค้ดและเพิ่มประสิทธิภาพ ให้ดูตัวอย่างแต่ละข้อกันครับ

1. ตรวจสอบเลขคู่/คี่ โดยไม่ใช้ตัวดำเนินการ % (Modulo)

ใช้บิตเวิร์ส AND (&) กับเลข 1 แทน หากผลลัพธ์ไม่ใช่ 0 = เลขคี่, หากเป็น 0 = เลขคู่ เนื่องจากเลขคี่ทุกตัวมีบิตน้อยที่สุด (LSB) เป็น 1 เสมอ

if ((n & 1) != 0) {
    // เลขคี่
} else {
    // เลขคู่
}

2. คูณและหารด้วยกำลังของ 2 ด้วยตัวดำเนินการ Shift

คูณด้วย 2ⁿ ให้ Shift ซ้าย n ครั้ง, หารด้วย 2ⁿ ให้ Shift ขวา n ครั้ง

x = 40; y = x << 2; // x * 4 = 160
x = 40; y = x >> 2; // x / 4 = 10

3. สลับค่าตัวแปรสองตัวโดยไม่ใช้ตัวแปรช่วย

ใช้ XOR (^) สามารถสลับค่าได้โดยไม่ต้องใช้ตัวแปรชั่วคราว

// swap x and y
x ^= y;
y ^= x;
x ^= y;

4. เข้าถึงตัวอักษรในสตริงโดยไม่ใช้ strlen()

ตรวจสอบว่าตัวอักษรที่ตำแหน่ง i ไม่เป็น null (non-zero) คือยังไม่ถึงปลายสตริง

for (int i = 0; s[i]; i++) {
    cout << s[i];
}

5. ใช้ emplace_back() แทน push_back() ใน STL

emplace_back() เร็วกว่าเพราะสร้างออบเจ็กต์ตรงในคอนเทนเนอร์ ไม่ต้องจัดสรรหน่วยความจำแยก

6. ฟังก์ชัน GCD ในตัว (__gcd)

C++ มี __gcd(x, y) สำหรับหาตัวหารร่วมมาก

7. ขนาดอาร์เรย์สูงสุด

• ในฟังก์ชัน main: ประมาณ 10⁶ องค์ประกอบ
• ประกาศแบบ Global: ได้ถึง 10⁷ องค์ประกอบ

8. หาตัวเลขหลักแรก (Most Significant Digit) ด้วย Logarithm

n = 4578;
double k = log10(n);
k = k - floor(k);
int x = pow(10, k); // x คือตัวเลขหลักแรก

9. นับจำนวนหลักตัวเลขโดยไม่ใช้ลูป

n = 4578;
int digit_count = floor(log10(n)) + 1;

10. ตรวจสอบว่าเป็นกำลังของ 2 หรือไม่

x = 1024;
bool check = x && (!(x & (x - 1))); // true = เป็นกำลังของ 2

11. อัลกอริทึมในตัว: all_of, any_of, none_of

all_of(left, left + n, isPositive());  // ทุกตัวเป็นบวกหรือไม่
any_of(left, left + n, isPositive());  // มีตัวบวกอย่างน้อย 1 ตัวหรือไม่
none_of(left, left + n, isPositive()); // ไม่มีตัวบวกเลยหรือไม่

12. คัดลอกข้อมูลระหว่างคอนเทนเนอร์ด้วย copy_n

int src[5] = {10, 20, 30, 40, 50};
int des[5];
copy_n(src, 5, dest);

13. สร้างลำดับตัวเลข/ตัวอักษรด้วย iota()

int arr[5] = {0};
char str[5] = {0};
iota(arr, arr+5, 15); // {15, 16, 17, 18, 19}
iota(str, str+5, 'A'); // {'A', 'B', 'C', 'D', 'E'}

14. กำหนดค่าในรูปแบบ Binary (Binary Literals)

int x = 0b1101; // x = 13

15. ใช้คีย์เวิร์ดแทนตัวดำเนินการเงื่อนไข

เช่น and แทน &&, or แทน ||, not แทน !

x = 10;
if (x < 10 and x > 5)
    cout << "True" << endl;
else
    cout << "False" << endl;