Phân tích 8 mẹo kỹ thuật thường sử dụng trong Lập trình thi đấu

MỞ ĐẦU

Xin chào các bạn, chào mừng các bạn quay trở lại với series "Lên trình Thuật toán - Lập trình thi đấu 🏆".

Mình là Trần Minh Sáng (a.k.a Tờ Mờ Sáng học Lập trình), hiện tại mình cũng đang là admin của facebook page CLB Lập trình - THPT Ngọc Tảo

Nếu có duyên thì có thể các bạn đã từng đọc được những bài viết của mình trên đó 👋

Trong bài viết này, mình sẽ chia sẻ với các bạn 8 kỹ thuật phổ biến được nhiều anh em sử dụng trong các cuộc thi Lập trình thi đấu.

Bài viết không chỉ là liệt kê, mà mình sẽ phân tích chi tiết từng kỹ thuật, để các bạn có thể hiểu rõ những thứ mà trước giờ chúng ta đều thường xuyên sử dụng khi làm các contest trên các trang VNOI, Codeforces, SPOJ, ...

Các bạn có thể xem phiên bản video của bài viết này tại đây:

Khi xem solution của các bạn tham gia lập trình thi đấu, chắc hẳn các bạn sẽ thường xuyên nhìn thấy template điển hình như sau:

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

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // Do something
    
    return 0;
}

1. #include <bits/stdc++.h>

• Nếu bạn còn nhớ cảm giác khi được khai sáng với thư viện <bits/stdc++.h>, thì chắc hẳn đó là một cảm giác rất tuyệt vời.

• Khi mà không còn phải nhớ chi tiết việc cần include thư viện nào trong C++ Standard Library, khi muốn sử dụng các hàm trong đó nữa (nhưng khi đi làm thì có thể sẽ có cảm xúc ngược lại khi dùng <bits/stdc++.h> đó nha )

• Chữ "bits/" chính là tên thư mục chứa file "stdc++.h". Khi xem source code của file stdc++.h, bạn sẽ thấy trong này gồm rất nhiều những câu lệnh #include các thư viện chuẩn trong C++ như iostream, string, vector, stack, queue, ...

  

• Điều này đồng nghĩa với việc, chỉ với 1 dòng #include <bits/stdc++.h>, bạn sẽ không còn phải nhớ và khai báo nhiều thư viện khi muốn sử dụng các hàm khác nhau nữa.

• Việc này đặc biệt hữu ích khi chúng ta đang tham gia các cuộc thi lập trình thi đấu, nơi mà mọi người cần tập trung nhiều hơn vào việc tìm ra thuật toán để giải quyết vấn đề một cách hiệu quả, thì rõ ràng <bits/stdc++.h> sẽ giúp anh em tiết kiệm được rất nhiều thời gian và hạn chế lỗi thiếu thư viện khi code ✅

• Tuy nhiên, bước ra khỏi những cuộc thi này, đặc biệt là đến khi đi làm, việc sử dụng <bits/stdc++.h> lại không được khuyến khích ❌

• Có 2 lý do chính như sau:

  1.1. Tăng thời gian biên dịch

  • Bình thường khi cần dùng hàm của thư viện nào, chúng ta chỉ cần include thư viện đó, thì trình biên dịch sẽ thực hiện nhanh chóng.

  • Nhưng khi sử dụng <bits/stdc++.h>, trong header file này include rất nhiều những thư viện chuẩn của C++, tức là bao gồm cả những thư viện mà trong chương trình của chúng ta không cần dùng đến. Do đó, thời gian biên dịch sẽ lâu hơn ⏳

  • Đặc biệt là khi làm việc với những project lớn, thường xuyên phải code-run-test, mà biên dịch chương trình còn lâu nữa chắc chắn sẽ khiến cho anh em developer vô cùng khó chịu 🤬

  1.2. Một số trình biên dịch không hỗ trợ

  • Vì <bits/stdc++.h> chỉ là một phần của GNU C++ Standard Library (libstdc++), được sử dụng trong trình biên dịch GCC (GNU Compiler Collection), chứ không phải một thư viện chuẩn trong C++, nên các bạn sẽ có thể gặp lỗi khi build chương trình trên những trình biên dịch khác nhau.

Tóm lại,

• Khi đi thi lập trình thi đấu, bạn có thể dùng <bits/stdc++.h>, nó không làm chương trình của bạn chạy chậm đi so với include từng thư viện đâu, chỉ làm chậm thời gian biên dịch thôi. Mà lập trình thi đấu thì đâu có chấm thời gian biên dịch đúng không nè 🤗

• Oái oăm lắm thì có chăng là trường hợp cuộc thi mà các bạn tham gia sử dụng trình biên dịch trên máy chấm điểm không hỗ trợ <bits/stdc++.h>. Nhưng trường hợp này rất hiếm gặp, bản thân mình cũng chưa gặp bao giờ.

• Thế còn sau này đi làm dự án thì không nên dùng <bits/stdc++.h> nha, bị các anh gõ cho u đầu đó. 🥴

2. using namespace std;

• Đây chắc hẳn là một trong những câu hỏi phổ biến của nhiều bạn khi mới học lập trình C++

• Nếu dịch word-by-word thì using namespace std; sẽ có ý nghĩa như sau:

  

• Nhờ có câu lệnh này mà chương trình có thể hiểu các đối tượng như cin, cout đến từ namespace nào.

• Các namespace trong C++ sẽ giúp các đoạn code tách biệt lẫn nhau trong những "không gian" riêng

  2.1. Vấn đề

• Cùng xem ví dụ dưới đây:

  #include <bits/stdc++.h>
  
  namespace MyNamespace
  {
      class Person // Class này trùng tên với class dưới
      {
      public:
          string name;
          int age;
      };
  
      class Person // Class này trùng tên với class trên
      {
      public:
          string name;
          int age;
      };
  }
  
  using namespace MyNamespace;
  
  int main()
  {
      Person person; // Lỗi: "Person" is ambiguous
      person.name = "Trần Minh Sáng";
      ...
  }
  

• Trong đoạn code này mình tự khai báo ra một namespace riêng có tên là MyNamespace

• Trong namespace này, mình lại khai báo 2 class có trùng tên là Person

• Khi mình sử dụng class Person để khởi tạo đối tượng trong hàm main(), chương trình ngay lập tức báo lỗi “Person” is ambiguous, tức là nó “mơ hồ” không hiểu phải sử dụng class Person ở trên hay Person ở dưới.

• Từ đó chúng ta có thể kết luận: Trong cùng một namespace sẽ KHÔNG ĐƯỢC PHÉP có 2 class có tên giống nhau.

  2.2. Cách khắc phục

• Để khắc phục lỗi này, chúng ta có thể làm theo 2 cách:

• Cách 1: Sửa tên class thứ hai thành Person2, để tránh trùng tên với class thứ nhất

  #include <bits/stdc++.h>
  
  namespace MyNamespace
  {
      class Person
      {
      public:
          string name;
          int age;
      };
  
      class Person2 // Đổi tên class này để không còn trùng tên với class trên nữa
      {
      public:
          string name;
          int age;
      };
  }
  
  using namespace MyNamespace;
  
  int main()
  {
      Person person; // Hết lỗi. Đối tượng person sẽ được khởi tạo từ class Person của namespace tên là MyNamespace
      person.name = "Trần Minh Sáng";
      ...
  }
  

• Cách 2: Tạo thêm một namespace khác làYourNamespace, và đưa 1 trong 2 class Person này sang namespace mới vừa tạo.

  #include <bits/stdc++.h>
  
  namespace MyNamespace
  {
      class Person // Mặc dù cùng có tên là Person, nhưng class này nằm ở namepsace khác với class bên dưới
      {
      public:
          string name;
          int age;
      };
  }
  
  namespace YourNamespace // Tạo 1 namespace mới là YourNamespace
  {
      class Person // Mặc dù cùng có tên là Person, nhưng class này nằm ở namepsace khác với class bên trên
      {
      public:
          string name;
          int age;
      };
  }
  
  int main()
  {
      MyNamespace::Person person; // Hết lỗi. Đối tượng person sẽ được khởi tạo từ class Person của namespace tên là MyNamespace
      person.name = "Trần Minh Sáng";
      ...
  }
  

• Sau đó, mình sẽ chỉ định rằng muốn sử dụng class Person của namespace nào bằng toán tử :: (thuật ngữ chuyên ngành gọi là scope resolution operator)

• Khi ấy, việc tồn tại 2 class cùng có tên là Person, nhưng nằm ở 2 namespace khác nhau, thì lại hoàn toàn hợp lệ.

• Khi đi làm, các bạn cũng sẽ thấy các anh chị tiền bối sẽ hay sử dụng toán tử :: hơn là using namespace, để giúp tránh lỗi xung đột tên giữa các namespace với nhau.

  

• Ngoài ra, một namespace không nhất thiết chỉ xuất hiện trong 1 file, mà nó có thể nằm ở nhiều file riêng lẻ.

• Bạn có thể xem source code của các thư viện iostream, heap, deque, ... cũng sẽ thấy sự xuất hiện của namespace std bao bọc lấy xung quanh đoạn code của các thư viện này.

  

• Điều này chỉ ra rằng: những hàm, biến, class, ... được khai báo bên trong đó đều thuộc về namespace std.

• Đó cũng là lý do tại sao khi include các thư viện này, các bạn chỉ cần “using namespace std“ là có thể sử dụng được các biến, hàm, class, ... nằm trong tất cả những thư viện ấy.

3. Input và Output

• Trong C++, chúng ta thường xuyên sử dụng đối tượng cin và cout với ý nghĩa:

  cin	cout
  Viết tắt của “character input”	Viết tắt của “character output”
  Đọc dữ liệu đầu vào	Xuất dữ liệu đầu ra

3.1. Đối tượng cin

• Đối tượng cin, là một đối tượng được định nghĩa trong thư viện iostream, thuộc namespace std, dùng để đọc một thông tin nào đó từ thiết bị nhập chuẩn (mặc định là bàn phím), sau đó lưu thông tin đó vào một biến.

• Toán tử >> mà các bạn thường nhìn thấy giống như mũi tên chỉ sang bên phải (thuật ngữ chuyên ngành gọi là extraction operator) được dùng chung với cin, cho biết hướng đi của dữ liệu từ màn hình console vào một biến.

• Đầu vào của chương trình thường bao gồm các số hoặc các chuỗi, được phân tách bằng dấu cách và dấu xuống dòng (newline).

• Khi đó, chúng có thể được đọc từ cin như đoạn code dưới đây:

  int a;
  string b;
  cin >> a >> b;
  

• Đoạn code này có thể đọc được cả 2 input sau:

  123 tmsangdev
  

  và

  123
  tmsangdev
  

• Dù là input sử dụng khoảng trắng hay sử dụng dấu xuống dòng (newline), thì biến a vẫn sẽ nhận được giá trị là 123, và biến b sẽ vẫn nhận được giá trị là chuỗi "tmsangdev".

3.2. Đối tượng cout

• Đối tượng cout cũng là một đối tượng được định nghĩa trong thư viện iostream thuộc namespace std, dùng để hiển thị một thông tin nào đó lên thiết bị xuất chuẩn (mặc định là màn hình).

• Toán tử << (thuật ngữ chuyên ngành gọi là insertion operator) được dùng chung với cout, cho biết hướng đi của dữ liệu từ giá trị bên phải toán tử này đến màn hình console.

• Bạn cũng có thể sử dụng toán tử << nhiều lần để in nhiều thông tin trên cùng một dòng. Ví dụ:

  cout << a << " " << b << "\n";
  

• Kết quả sẽ in ra màn hình là 123 tmsangdev và 1 dấu xuống dòng (newline)

  123 tmsangdev
  
  

4. endl và "\n"

• Có thể sẽ có bạn thắc mắc tại sao mình ở đoạn code trên, mình không dùng endl để xuống dòng, mà lại dùng "\n".

• Thực tế là "\n" chạy nhanh hơn so với endl trong đa số các trường hợp.

  

Vậy khi nào nên sử dụng endl? Khi nào nên sử dụng "\n"?

5. Fast I/O

• Một mẹo thần thánh nữa mình cũng thấy mọi người thường sử dụng, được gọi là Fast I/O, với 2 dòng lệnh kinh điển sau:

  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  

• Tuy nhiên, mình có hỏi thử các bạn học sinh lớp 12 trong CLB lập trình từng tham gia thi HSG những năm gần đây, thì các bạn trả lời chỉ "nghe nói" hoặc "thấy mọi người bảo là" dùng cái này sẽ tăng tốc độ cho chương trình, mà chưa thực sự hiểu bản chất của nó là như thế nào.

• Một khi đã không hiểu, thì có thể bạn sẽ gặp phải trường hợp làm chương trình trở nên chậm hơn khi sử dụng thứ gọi là Fast I/O này đó.

• Trước tiên chúng ta cần hiểu ý nghĩa của 2 dòng lệnh này trước đã.

5.1. ios_base::sync_with_stdio(false);

• Nếu nhìn vào tên hàm, bạn có thể hiểu nôm na tác dụng của nó là để đồng bộ (sync) với standard input output (stdio)

• Hàm này truyền vào giá trị false, tức là muốn ngắt bỏ sự đồng bộ này đi ❌️

Vậy tại sao ngắt bỏ sự đồng bộ với stdio lại có thể tăng tốc độ của chương trình?

• Lý do là vì trong C++ có 2 hình thức để nhập/xuất từ stream, đó là:

  • Sử dụng scanf và printf của thư viện cstdio
  • Hoặc sử dụng cin và cout của thư viện iostream

• Theo mặc định, thứ tự nhập/xuất của cin và scanf, cout và printf sẽ được đồng bộ (sync) để đề phòng trường hợp, nếu trong code của bạn có sử dụng cả 2 hình thức này. Ví dụ:

  cout << "Hello";
  printf("Goodbye");
  

  thì thứ tự thực hiện sẽ được đồng bộ đúng như vậy, chứ không bị lộn xộn hết cả lên.

  

Ơ thế thì tại sao trong lập trình thi đấu, mọi người lại truyền vào hàm sync_with_stdio() giá trị false nhỉ???

• Đó là vì thông thường trong lập trình thi đấu, mọi người sẽ chỉ sử dụng hoặc là cặp cin-cout, hoặc là cặp scanf-printf, chứ không dùng lẫn cả 2 loại.

• Nên việc đồng bộ cho 2 luồng này rõ ràng là không cần thiết.

• Do đó, khi chúng ta tắt đồng bộ đi, đồng nghĩa với việc tốc độ thực thi sẽ nhanh hơn, khi không phải mất thời gian đồng bộ ở trên nữa.

  

• Ngoài ra, trên Viblo còn có 1 bài viết rất chi tiết của tác giả @bobamilktea, phân tích về hiểu lầm phổ biến của nhiều anh em chơi CP về Fast I/O, các bạn có thể đọc thêm tại đây nha.

5.2. cin.tie(nullptr)

• À thế còn dòng lệnh cin.tie(nullptr), cũng là 1 phần của Fast I/O thần thánh mà mọi người hay sử dụng. Vậy ý nghĩa của nó là gì?

  

• "tie" dịch sang tiếng Việt có nghĩa là thắt, buộc, các bạn có thể liên tưởng đến hình ảnh quen thuộc đó là thắt cà vạt.

• Còn ở đây, cin.tie() được dùng để đồng bộ hay nói dân dã hơn là "buộc" thứ tự nhập/xuất của cin và cout lại với nhau.

• Thao tác "buộc" này sẽ giúp đảm bảo rằng 1 stream (ví dụ cin) phải được hoàn thành và xóa xong (flushed), thì một stream khác (ví dụ cout) mới có thể thực hiện được.

• Nếu không có việc buộc (hay đồng bộ) này, thì thứ tự input/output của bạn nhiều khả năng sẽ bị xáo trộn tùm lum.

• Mặc định, cin và cout sẽ được đồng bộ với nhau để đảm bảo cho những ứng dụng tương tác với người dùng sẽ đi theo một trình tự hợp lý.

• Ví dụ:

  cout << "Nhập tên của bạn: ";
  cin >> name;
  

  • Khi cin và cout được đồng bộ, thì bạn có thể yên tâm là chỉ khi nào dòng chữ "Nhập tên của bạn: " được in hết lên màn hình console rồi, thì màn hình mới hiện ra con trỏ nhấp nháy để cho phép người dùng nhập tên và lưu vào biến name.

  

• Thử tưởng tượng, nếu cin và cout bị ngắt đồng bộ ở đây, thì có thể dòng chữ "Nhập tên của bạn: " chưa được in ra, thì màn hình đã yêu cầu người dùng nhập dữ liệu rồi. Lúc ý khi không có câu hướng dẫn kia, thì người dùng biết phải nhập gì bây giờ đúng không nào?

  

• Ấy thế nhưng khi đi thi lập trình thi đấu, đặc biệt phải kể đến những kỳ thi HSG ở Việt Nam, đề bài sẽ thường yêu cầu chúng ta lặp đi lặp lại việc đọc ghi qua file với số lượng bộ test lớn, thì việc bật đồng bộ giữa cin và cout này có thể khiến tốc độ thực thi bị chậm đi.

• Ngoài ra, vì bạn đọc ghi qua 2 file khác nhau, 1 file input, 1 file output riêng, chứ không có sự tương tác với người dùng như ví dụ ở trên, nên việc đồng bộ giữa cin và cout cũng là không cần thiết.

• Do đó, ngắt đồng bộ bằng câu lệnh cin.tie(nullptr) cũng không khiến cho chương trình hoạt động sai được, mà lại cải thiện tốc độ chạy của chương trình.

6. getline()

• Một lưu ý khác khi tham gia lập trình thi đấu, đó là đôi khi chương trình phải đọc cả 1 chuỗi dài, chứa các khoảng trắng.

• Ví dụ: "Tờ Mờ Sáng học Lập trình"

• Khi đó thay vì dùng cin, chúng ta sẽ dùng hàm getline() như đoạn code ví dụ dưới đây.

  string s;
  getline(cin, s);
  

7. Nhập rất nhiều bộ test, mỗi bộ test trên 1 dòng. Và bộ test sẽ kết thúc bởi 1 dòng chứa số 0

• Đây chắc hẳn cũng là trường hợp đặc biệt khác mà nhiều bạn có thể đã từng gặp trong các đề thi.

• Vòng lặp while đơn giản dưới đây sẽ giúp bạn nhanh chóng giải quyết được việc này:

  while (cin >> x)
  {
      if (x == 0) break;
      ...
  }
  

8. Đọc ghi file với freopen()

• Phần cuối cùng mình muốn chia sẻ với các bạn trong video này, đó là việc đọc ghi file.

• Trong một số kỳ thi lập trình (đặc biệt là ở Việt Nam), và xa hơn là trong công việc lập trình sau này, có những lúc dữ liệu nhập vào rất nhiều và lớn, việc nhập bằng tay là không khả thi.

  

• Khi đó, dữ liệu thường sẽ được sinh ra sẵn và đặt trong một file text nào đó.

• Nhiệm vụ của người làm bài là nhận dữ liệu từ file text đó, xây dựng thuật toán, sau đó xuất kết quả ra một file text tương đương.

• Và C++ cung cấp cú pháp rất đơn giản, đó là sử dụng hàm freopen() trong thư viện cstdio (viết tắt của C standard input output)

  freopen(filename, access_mode, stream);
  

• Hàm này lần lượt nhận 3 tham số đầu vào là:

  • filename: Tên của file. Đây có thể là file dữ liệu đầu vào, hoặc file kết quả đầu ra. Trong lập trình thi đấu, đề bài thường yêu cầu các file có định dạng như .INP (viết tắt của INPUT), .OUT (viết tắt của OUTPUT), hoặc .DAT (viết tắt của DATA)

  • access_mode: Chế độ truy cập file, cho biết rằng bạn muốn truy cập file này để làm gì. Có 6 chế độ truy cập với file văn bản, bao gồm:

    Chế độ	Mô tả
    r	Viết tắt của read. Mở file để đọc dữ liệu. Với điều kiện file đó bắt buộc phải có tồn tại.
    w	"Viết tắt của write. Tạo 1 file rỗng để ghi dữ liệu ra. Nếu như tồn tại 1 file cùng tên, thì nội dung file đó sẽ bị xóa và bị ghi đè bởi dữ liệu mới."
    a	"Viết tắt của append. Mở file để ghi dữ liệu vào cuối file. Nếu file đã tồn tại và có dữ liệu, thì dữ liệu đó sẽ vẫn nguyên vẹn, và dữ liệu mới sẽ được ghi tiếp vào cuối file. Nếu file chưa tồn tại, thì nó sẽ tự tạo file mới để ghi vào."
    r+	"Viết tắt của read/update. Mở file ra vừa để đọc dữ liệu, vừa để update dữ liệu. Với điều kiện là file này phải có tồn tại."
    w+	"Viết tắt của write/update. Tạo 1 file rỗng và mở nó ra để update dữ liệu. Nếu như tồn tại 1 file cùng tên, thì nội dung file đó sẽ bị xóa và bị ghi đè bởi dữ liệu mới."
    a+	Viết tắt của append/update. Mở 1 file để update dữ liệu vào cuối file.

    Mặc dù có nhiều chế độ như vậy, nhưng theo mình quan sát, thông thường trong lập trình thi đấu, chúng ta sẽ chỉ sử dụng 2 chế độ là "r" và "w", tức là read và write. nhập dữ liệu input từ một file, và xuất dữ liệu output ra một file khác.

  • stream: Ở các đề thi lập trình thi đấu, chúng ta thường sử dụng một trong hai luồng là stdin (standard in), hoặc stdout (standard out). Tương ứng với luồng đọc dữ liệu vào và luồng xuất dữ liệu ra.

• Dưới đây là một bí dụ minh họa trong kỳ thi HSG Tin, liên quan đến số Amstrong. Với yêu cầu nhập dữ liệu từ file AMSTRONG.INP và ghi kết quả ra file AMSTRONG.OUT

  

• Với kiến thức đã học ở trên, lúc này để đọc ghi file, chúng ta đơn giản chỉ cần thêm hai hàm freopen()ở đầu hàm main() là được:

  #include <bits/stdc++.h>
  using namespace std;
  
  int main()
  {
      freopen("AMSTRONG.INP", "r", stdin);
      freopen("AMSTRONG.OUT", "w", stdout);
  
      int number;
      cin >> number;
  
      ...
  
      return 0;
  }
  

KẾT LUẬN

• Vậy là mình vừa chia sẻ với các bạn toàn bộ nội dung của bài viết: Phân tích 8 mẹo kỹ thuật thường sử dụng trong Lập trình thi đấu.

• Mặc dù bài hơi dài, nhưng mình tin chắc rằng khi hiểu bản chất của những kỹ thuật này, các bạn sẽ thấy lập trình thi đấu thú vị hơn nhiều, chứ không chỉ đơn thuần là học mẹo để đi thi nữa.

Các bạn có thể tham khảo series video "Lên trình Thuật toán - Lập trình thi đấu 🏆" mà mình đang làm trên Youtube tại đây

Hi vọng kiến thức này hữu ích với bạn. Hẹn gặp lại 👋