แผนการเรียน
/

Arrays, Control Structures & Fast I/O
หัวใจของการเริ่มเขียนโปรแกรมแข่งขัน

วันที่ 1 ช่วงบ่าย: การควบคุมทิศทางโปรแกรมและการจัดการข้อมูลชุด

สิ่งที่จะได้เรียนรู้

1
การจัดการหน่วยความจำด้วย Arrays ทั้งแบบคงที่และ Dynamic
2
การใช้ Loops และ Conditionals อย่างมีประสิทธิภาพ
3
เทคนิค Fast I/O เพื่อหลีกเลี่ยง Time Limit Exceeded (TLE)

ความถูกต้อง (Correctness) และความเร็ว

ในการแข่งขัน อัลกอริทึมที่ถูกต้องต้องมาคู่กับการ구현 (Implementation) ที่แม่นยำ

การจัดการข้อมูล

โจทย์ส่วนใหญ่เกี่ยวข้องกับการประมวลผลลำดับตัวเลข (Sequences) ทำให้ Arrays เป็นโครงสร้างข้อมูลพื้นฐานที่ใช้บ่อยที่สุด

ความเร็วในการอ่านข้อมูล

ในโจทย์ที่มี Input ขนาดใหญ่ (เช่น \(10^6\) ตัว) การอ่านข้อมูลช้าอาจทำให้โปรแกรมทำงานเกินเวลาแม้จะใช้อัลกอริทึมที่เร็วแล้วก็ตาม

Arrays แบบคงที่ (Fixed-size)

int arr[9]; // จองพื้นที่สำหรับ 100 ตัวเต็ม

arr = 5; // เข้าถึงข้อมูลด้วย Index (เริ่มที่ 0)

  • • การเข้าถึงข้อมูลใช้เวลา \(O(1)\) เสมอ
  • • ข้อควรระวัง: การเข้าถึง Index ที่อยู่นอกช่วงที่จองไว้ (Out of bounds) จะทำให้เกิดพฤติกรรมที่ไม่แน่นอนหรือ Runtime Error
  • • ในการแข่งขัน มักจะประกาศ Array ขนาดใหญ่เป็น Global เพื่อให้อยู่ใน Data segment และถูก Initialize เป็น 0 โดยอัตโนมัติ

Where to declare?

Global (แนะนำ)

ประกาศไว้นอกฟังก์ชัน `main` สามารถมีขนาดใหญ่ได้มาก (ถึงระดับ \(10^7\)) และค่าเริ่มต้นจะเป็น 0 เสมอ

Local

ประกาศในฟังก์ชัน มีขนาดจำกัด (Stack size) และค่าเริ่มต้นจะเป็นค่าขยะ (Random values) ถ้าไม่กำหนดค่า

2D Arrays: การจัดการตาราง

ใช้สำหรับโจทย์ที่เป็นตารางหรือกราฟ (Adjacency Matrix)

int grid[9];

for(int i=0; i<100; i++) {

for(int j=0; j<100; j++) { cin >> grid[i][j]; }

}

ทิป: การวนลูปแถวนอก (i) แล้วค่อยหลักใน (j) จะเร็วกว่าเนื่องจากหลักการ Cache Locality ในหน่วยความจำ

std::vector: Array ที่ยืดหยุ่น

เปลี่ยนขนาดได้ตามต้องการ (Dynamic resizing)

vector<int> v;

v.push_back(10); // เพิ่มข้อมูลต่อท้าย

cout << v.size(); // ดูจำนวนข้อมูลปัจจุบัน

หมายเหตุ: รายละเอียดเชิงลึกของ vector จะอยู่ในหัวข้อ STL วันที่ 3

If-Else และ Comparison Operators

a == b // เท่ากัน
a != b // ไม่เท่ากัน
a < b // น้อยกว่า
a && b // AND (และ)
a || b // OR (หรือ)
!a // NOT (ไม่)

if (x % 2 == 0) {

cout << "Even";

} else {

cout << "Odd";

}

for Loop

for (int i = 0; i < n; i++) {

// ทำซ้ำ n ครั้ง

}

Competitive Tip: หากต้องการความรวดเร็วในการเขียน สามารถใช้ Macro:
#define rep(i, a, b) for(int i = a; i < b; i++)

while Loop

ใช้เมื่อไม่ทราบจำนวนรอบที่แน่นอน

while (n > 0) {

n /= 10; // เช่น การนับหลักของตัวเลข

}

do-while จะทำงานก่อน 1 รอบเสมอค่อยเช็คเงื่อนไข

Loop Control

break;

หยุดการทำงานของลูปทันทีเมื่อพบเงื่อนไขที่กำหนด

continue;

ข้ามการทำงานในรอบปัจจุบันและไปเริ่มรอบถัดไปทันที

Generating Permutations

C++ มีฟังก์ชันช่วยหา "ลำดับถัดไป" ของข้อมูล (Lexicographical order)

sort(v.begin(), v.end());

do {

// ประมวลผลแต่ละวิธีเรียงสับเปลี่ยน

} while (next_permutation(v.begin(), v.end()));

ทำไมต้อง Fast I/O?

ในโจทย์ที่มีข้อมูลขาเข้า \(10^5 - 10^6\) ตัว `cin` และ `cout` มาตรฐานอาจทำงานช้าเกินไป

เหตุผล: `cin` ต้องรอซิงโครไนซ์กับ `stdio` ของภาษา C และมีการจัดการ Buffer ที่ไม่เหมาะกับการรับส่งข้อมูลขนาดใหญ่ในการแข่งขัน

วิธีเร่งความเร็ว cin/cout

ios::sync_with_stdio(0);

cin.tie(0); // ใส่ไว้ที่บรรทัดแรกของ main()

  • • sync_with_stdio(0): ปิดการทำงานร่วมกับ C library (ห้ามใช้ scanf/printf ร่วมด้วย!)
  • • cin.tie(0): ปลดการรอระหว่าง input และ output (มีประโยชน์มาก)

endl: ตัวทำลายความเร็ว

cout << endl;

ขึ้นบรรทัดใหม่ + Flush Buffer (สั่งล้างบัฟเฟอร์ลงจอทันที) ซึ่งช้ามากในลูปใหญ่ๆ

cout << "\n";

ขึ้นบรรทัดใหม่เพียงอย่างเดียว (ข้อมูลจะถูกเก็บไว้ส่งทีเดียว) รวดเร็วกว่ามาก

scanf และ printf

ฟังก์ชันดั้งเดิมจากภาษา C ที่มีความเร็วสูงโดยธรรมชาติ

scanf("%d %d", &a, &b);
printf("%d\n", sum);
หมายเหตุ: การใช้ `cin.tie(0)` ร่วมกับ `sync_with_stdio(0)` จะทำให้ `cin/cout` เร็วเท่ากับ `scanf/printf`

Working with Files

บางสนามแข่ง (เช่น USACO หรือโจทย์เก่า) กำหนดให้อ่าน/เขียนผ่านไฟล์

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);

สามารถใช้ cin/cout ได้ตามปกติหลังจากใส่ 2 บรรทัดนี้

Summary & Next Steps

  • • ใช้ Global Arrays เพื่อป้องกัน Memory limit และการ Initialize
  • • ใช้ Fast I/O เสมอในการแข่งขันระดับสากล
  • • หลีกเลี่ยง endl และใช้ "\n" แทน
  • • ตรวจสอบ Index ของ Array ให้ดีเพื่อป้องกัน Error ที่ไล่ยาก
ได้เวลาทดสอบทักษะใน Practice Session! (15.00 - 17.00 น.)