คู่มือโอลิมปิกคอมพิวเตอร์

การเขียนโปรแกรมเชิงแข่งขัน

หลักการ

การเขียนโปรแกรมเชิงแข่งขันแบ่งออกเป็นสองหัวข้อหลักๆ คือ

การออกแบบวิธีการคิด

ส่วนนี้จะเน้นเรื่องทักษะการแก้ปัญหาและพื้นฐานการคิด บางทีต้องมีความคิดสร้างสรรค์ ประกอบกับทฤษฎีต่างๆ โดยทั่วไปแล้ววิธีการแก้ปัญหาจะประกอบด้วยเทคนิคที่รู้กันทั่วไปร่วมกับความเป็นเอกลักษณ์ของปัญหานั้นๆ

การเขียนโปรแกรมตามวิธี

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

การบริหารเวลา

เป็นสิ่งสำคัญที่สุดในการแข่งขัน

• ให้คำนึงให้ได้ว่าเราจะใช้เวลาเท่าไรในการทำโจทย์ลักษณะนี้ แล้วจะได้คะแนนเท่าไร แล้วลำดับความสำคัญในการเลือกโจทย์ให้ได้

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

Time Complexity

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

• Big O Notation เป็นสิ่งสำคัญที่ควรจะคาดคะเนให้ได้ว่าเราจะได้คะแนนเท่าไร

• จุดอ้างอิงคร่าวๆ ให้คาดว่า C++ สามารถรันได้ 1, 000, 000, 000 (พันล้าน) คำสั่งต่อหนึ่งวินาที ซึ่งหมายความว่า

  • N = 1, 000 สามารถคิดวิธี O(N³) ได้แบบฉิวเฉียด O(N²log N) ได้อย่างปลอดภัย

  • N = 1, 000, 000 ควรจะ O(Nlog N)

  • N = 20 อาจจะเป็น O(2^N)

• จำว่า 2²⁰ มีค่าประมาณ 1, 000, 000 (หนึ่งล้าน)