แนะนำ Competitive Programming

เอกสารนี้จัดทำโดย KU SRC (Kasetsart University Sriracha Campus) เพื่อเป็นแนวทางในการเตรียมตัวสำหรับการแข่งขัน ICPC (International Collegiate Programming Contest)

Competitive Programming คืออะไร?

Competitive Programming คือการแข่งขันแก้ปัญหาทางคอมพิวเตอร์ภายในเวลาจำกัด โดยผู้เข้าแข่งขันจะต้อง:

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

การแข่งขัน ICPC

ICPC (International Collegiate Programming Contest) เป็นการแข่งขันเขียนโปรแกรมระดับนานาชาติสำหรับนักศึกษาระดับมหาวิทยาลัย

รูปแบบการแข่งขัน

• ทีมละ 3 คน ใช้คอมพิวเตอร์ 1 เครื่อง
• ระยะเวลา 5 ชั่วโมง
• โจทย์ประมาณ 10-15 ข้อ
• ต้องแก้ปัญหาให้ได้มากที่สุดในเวลาที่น้อยที่สุด

เกณฑ์การให้คะแนน

1. จำนวนข้อที่แก้ได้ (มากกว่าดีกว่า)
2. เวลารวมที่ใช้ (น้อยกว่าดีกว่า)
3. Penalty time จากการส่งผิด (+20 นาทีต่อครั้ง)

ทักษะที่จำเป็น

1. Data Structures (โครงสร้างข้อมูล)

// ตัวอย่างโครงสร้างข้อมูลที่ใช้บ่อย
vector<int> arr;           // Dynamic array
set<int> s;                // Balanced BST
map<int, int> m;           // Key-value mapping
priority_queue<int> pq;    // Heap

โครงสร้างข้อมูลที่ควรรู้:

• Array, Vector, String
• Stack, Queue, Deque
• Set, Map, Unordered Set/Map
• Priority Queue (Heap)
• Segment Tree, Fenwick Tree
• Disjoint Set Union (DSU)

2. Algorithms (ขั้นตอนวิธี)

Algorithm พื้นฐานที่ต้องรู้:

หมวดหมู่	Algorithms
Sorting	Quick Sort, Merge Sort, Counting Sort
Searching	Binary Search, Ternary Search
Graph	BFS, DFS, Dijkstra, Floyd-Warshall
DP	Knapsack, LCS, LIS
Number Theory	GCD, Prime Sieve, Modular Inverse

3. Programming Language

ภาษาที่นิยมใช้ในการแข่งขัน:

• C++ - เร็วที่สุด, มี STL ที่ทรงพลัง (แนะนำ)
• Python - เขียนง่าย แต่ช้ากว่า
• Java - มี BigInteger สำหรับเลขใหญ่

Template Code สำหรับการแข่งขัน

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

#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;

void solve() {
    // Your solution here
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t = 1;
    // cin >> t; // Uncomment for multiple test cases
    while (t--) {
        solve();
    }
    
    return 0;
}

Fast I/O

การอ่าน/เขียนข้อมูลที่เร็วสำคัญมากในการแข่งขัน:

// เร็วกว่า cin/cout ปกติมาก
ios_base::sync_with_stdio(false);
cin.tie(NULL);

// หรือใช้ scanf/printf
scanf("%d", &n);
printf("%d\n", ans);

แหล่งฝึกฝน

เว็บไซต์สำหรับฝึกฝน:

1. Codeforces - มีการแข่งขันบ่อย, ระบบ rating
2. AtCoder - โจทย์คุณภาพดี, เหมาะกับผู้เริ่มต้น
3. USACO - มีหลายระดับ Bronze/Silver/Gold/Platinum
4. LeetCode - เหมาะสำหรับเตรียมสัมภาษณ์งาน
5. DMOJ - มีโจทย์หลากหลาย

เคล็ดลับสำหรับผู้เริ่มต้น

1. เริ่มจากโจทย์ง่าย - อย่าเพิ่งข้ามไปทำโจทย์ยาก
2. เข้าใจ Complexity - รู้ว่า Algorithm ของเราเร็วพอหรือไม่
3. อ่าน Editorial - เรียนรู้วิธีคิดจากคำตอบ
4. ฝึกทุกวัน - ความสม่ำเสมอสำคัญกว่าปริมาณ
5. เรียนรู้จากผู้อื่น - ดู code ของคนที่แก้ได้

💡 Tip: ในการแข่งขัน ให้อ่านโจทย์ทุกข้อก่อน แล้วค่อยเริ่มทำจากข้อที่ง่ายที่สุด