การเขียนโปรแกรมเชิงแข่งขัน
หลักการ
การเขียนโปรแกรมเชิงแข่งขัน (competitive programming) ประกอบด้วยสองทักษะที่ต้องฝึกคู่กัน
ออกแบบวิธีคิด (algorithm design)
อ่านโจทย์ให้เข้าใจ แล้วหาวิธีแก้ที่ ถูกต้อง และ เร็วพอ ตามขนาดข้อมูล วิธีแก้ส่วนใหญ่คือการนำเทคนิคที่รู้จักกันดี (เช่น sorting, BFS, DP) มาผสมกับข้อสังเกตเฉพาะของโจทย์นั้น ยิ่งรู้จัก pattern มากก็ยิ่งเห็นทางได้เร็ว
เขียนโปรแกรมตามวิธีคิด (implementation)
วิธีคิดที่ถูกยังไม่พอ ต้องแปลงเป็นโค้ดที่ถูกต้องภายในเวลาจำกัด โปรแกรมในการแข่งขันมักสั้น (ไม่กี่สิบถึงไม่กี่ร้อยบรรทัด) และไม่ต้องดูแลต่อหลังแข่ง จึงเน้นความเร็วและความถูกต้องมากกว่าความสวยงาม
ขั้นตอนการทำโจทย์หนึ่งข้อ
อ่านโจทย์และ constraint ให้ครบ ขนาดของ n บอกใบ้ว่าต้องใช้วิธีเร็วแค่ไหน
ลองตัวอย่างด้วยมือ และคิดตัวอย่างเพิ่มเอง โดยเฉพาะกรณีขอบ (edge case) เช่น n = 1 หรือค่าซ้ำกันทั้งหมด
คิดวิธีและประเมิน time complexity ก่อนเขียน ถ้าช้าเกินไปให้คิดใหม่ตั้งแต่ตอนนี้
เขียนโค้ด ทีละส่วนและทดสอบกับตัวอย่าง
ส่งและอ่านผลตรวจ ถ้าไม่ผ่านให้หาว่าผิดเพราะอะไรจากสัญลักษณ์ผลตรวจ
การประเมินเวลา
grader ทั่วไปรัน C++ ได้ประมาณ 10^{8} คำสั่งง่าย ๆ ต่อวินาที (เครื่องเร็วอาจได้มากกว่านั้นหลายเท่า แต่ควรใช้ 10^{8} เป็นตัวเลขที่ปลอดภัย) นำ time complexity มาแทนค่า n สูงสุด แล้วเทียบกับเวลาที่โจทย์ให้
n = 10^{5} และวิธี O\left( n^{2} \right): 10^{10} คำสั่ง ใช้เวลาประมาณ 100 วินาที ช้าเกินไป
n = 10^{5} และวิธี O\left( n\log n \right): ประมาณ 1.7 \times 10^{6} คำสั่ง เร็วมาก
จำไว้ว่า 2^{10} \approx 10^{3} และ 2^{20} \approx 10^{6}
ตารางนี้ช่วยเดาวิธีที่ต้องใช้จากขนาด input เมื่อจำกัดเวลา 1 วินาที
| ขนาด n | complexity ที่ควรใช้ |
|---|---|
| n \leq 10 | O(n!) |
| n \leq 20 | O\left( 2^{n} \right) หรือ O\left( 2^{n}n \right) |
| n \leq 500 | O\left( n^{3} \right) |
| n \leq 5000 | O\left( n^{2} \right) |
| n \leq 10^{6} | O\left( n\log n \right) หรือ O(n) |
| n ใหญ่กว่านั้น | O\left( \log n \right) หรือ O(1) (มักเป็นสูตรคณิตศาสตร์) |
รายละเอียดการวิเคราะห์อยู่ในบท Big O Notation
ผลตรวจจาก grader
grader ไทยหลายแห่ง เช่น programming.in.th แสดงผลแต่ละ test case เป็นสัญลักษณ์
| สัญลักษณ์ | ความหมาย | สาเหตุที่พบบ่อย |
|---|---|---|
| P | ผ่าน (Pass) | - |
| - | คำตอบผิด (Wrong Answer) | วิธีคิดผิด, ลืม edge case, overflow, รูปแบบ output ผิด |
| X | โปรแกรมพัง (Runtime Error) | เข้าถึง array นอกขอบเขต, หารด้วย 0, recursion ลึกเกิน |
| T | เกินเวลา (Time Limit Exceeded) | complexity สูงเกินไป, วนไม่รู้จบ, I/O ช้า |
การบริหารเวลา
อ่านทุกข้อก่อน แล้วประเมินว่าข้อไหนใช้เวลาเท่าไรและได้คะแนนเท่าไร จากนั้นเรียงลำดับว่าจะทำข้อไหนก่อน
คะแนนบางส่วน (subtask) สำคัญมาก ถ้ายังคิดวิธีเต็มไม่ออก ให้เขียน brute force เก็บคะแนน subtask เล็กไว้ก่อน
ตั้งกฎให้ตัวเอง เช่น ถ้า debug เกิน 30 นาทีโดยไม่คืบหน้า ให้ไปอ่านข้ออื่นอย่างน้อย 5 นาทีแล้วค่อยกลับมา
เมื่อหา bug ไม่เจอ
พิมพ์ค่าตัวแปรระหว่างทาง (debug print) ไปที่
cerrแทนcoutเพื่อไม่ปนกับคำตอบคิด test case เล็ก ๆ ที่คำนวณคำตอบด้วยมือได้
Stress test: เขียน brute force ที่ช้าแต่แน่ใจว่าถูก แล้วสุ่ม input เล็ก ๆ มาเทียบคำตอบกับวิธีจริงจนกว่าจะเจอ input ที่ต่างกัน
โจทย์ฝึกฝน (Practice Problems)
ลองทำโจทย์เหล่านี้จาก CSES Problem Set เพื่อฝึกใช้ทักษะจากบทนี้ โดยเริ่มจากโจทย์ที่ง่ายที่สุดก่อน
โจทย์เพิ่มเติม: CSES Problem Set และ programming.in.th