Chào mừng độc giả Cafedev đến với một chia sẻ mới! Hôm nay, chúng ta sẽ khám phá thế giới lập trình cạnh tranh với sự hỗ trợ mạnh mẽ từ Kotlin. Với “Kotlin với competitive programming,” chúng ta sẽ đàm phán về cách Kotlin không chỉ là một ngôn ngữ lập trình đa năng cho Android mà còn là một công cụ hiệu quả cho những người đam mê lập trình cạnh tranh. Hãy cùng nhau tìm hiểu về lợi ích và mẹo hữu ích khi sử dụng Kotlin để giải quyết những thách thức hấp dẫn trong lập trình!”
Hướng dẫn này được thiết kế cho cả những lập trình viên cạnh tranh chưa sử dụng Kotlin trước đây và những nhà phát triển Kotlin chưa tham gia bất kỳ sự kiện lập trình cạnh tranh nào trước đó. Nó giả định về kỹ năng lập trình tương ứng.
Lập trình cạnh tranh là một môn thể thao tinh thần nơi các thí sinh viết chương trình để giải quyết các vấn đề thuật toán được chỉ định một cách chính xác trong các ràng buộc nghiêm ngặt. Các vấn đề có thể từ đơn giản, có thể được giải quyết bởi bất kỳ nhà phát triển phần mềm nào và yêu cầu ít mã nguồn để đạt được một giải pháp đúng, đến những vấn đề phức tạp yêu cầu kiến thức về các thuật toán đặc biệt, cấu trúc dữ liệu và nhiều thực hành. Mặc dù không được thiết kế đặc biệt cho lập trình cạnh tranh trong thi đấu, Kotlin tình cờ phù hợp tốt trong lĩnh vực này, giảm lượng mã mẫu điển hình mà một lập trình viên cần phải viết và đọc khi làm việc với mã nguồn gần như đến mức mà ngôn ngữ kịch bản được định kiểu động cung cấp, trong khi vẫn giữ các công cụ và hiệu suất của một ngôn ngữ định kiểu tĩnh.
Xem Bắt đầu với Kotlin/JVM để biết cách thiết lập môi trường phát triển cho Kotlin. Trong lập trình cạnh tranh, thường chỉ tạo một dự án và mỗi giải pháp cho một vấn đề được viết trong một tệp nguồn duy nhất.
Nội dung chính
1. Ví dụ đơn giản: Vấn đề Các số có thể đạt được
Hãy xem xét một ví dụ cụ thể.
Dùng cho Vòng thi Codeforces Round 555 diễn ra vào ngày 26 tháng 4, điều này có nghĩa là nó có những vấn đề phù hợp cho bất kỳ nhà phát triển nào thử sức. Bạn có thể sử dụng liên kết này để đọc về các vấn đề. Vấn đề đơn giản nhất trong bộ là Vấn đề A: Các số có thể đạt được. Nó yêu cầu triển khai một thuật toán đơn giản được mô tả trong tuyên bố vấn đề.
Chúng ta sẽ bắt đầu giải quyết nó bằng cách tạo một tệp nguồn Kotlin với tên tùy ý. A.kt. Trước hết, bạn cần triển khai một hàm được chỉ định trong vấn đề như sau:
Hãy ký hiệu một hàm f(x) như sau: chúng ta thêm 1 vào x, sau đó, khi có ít nhất một số 0 dư sau cùng trong số nhận được, chúng ta loại bỏ số 0 đó.
Kotlin là một ngôn ngữ thực tế và không định kiến, hỗ trợ cả các kiểu lập trình chủ nghĩa và lập trình hàm mà không forced nhà phát triển về bất kỳ kiểu nào. Bạn có thể triển khai hàm f theo kiểu hàm, sử dụng những tính năng Kotlin như đệ quy đuôi:
tailrec fun removeZeroes(x: Int): Int =
if (x % 10 == 0) removeZeroes(x / 10) else x
fun f(x: Int) = removeZeroes(x + 1)Hoặc, bạn có thể viết một phiên bản thực thi của hàm f theo kiểu chủ nghĩa, sử dụng vòng lặp while truyền thống và biến có thể thay đổi được được ký hiệu trong Kotlin bằng var:
fun f(x: Int): Int {
var cur = x + 1
while (cur % 10 == 0) cur /= 10
return cur
}Trong Kotlin, kiểu là tùy chọn ở nhiều nơi do việc sử dụng rộng rãi của suy luận kiểu, nhưng mọi khai báo vẫn có một kiểu tĩnh định được xác định tại thời điểm biên dịch.
Bây giờ, chỉ còn việc viết hàm chính đọc đầu vào và triển khai phần còn lại của thuật toán theo yêu cầu của đề bài – tính số nguyên khác nhau được tạo ra khi áp dụng liên tục hàm f vào số nguyên ban đầu n được cung cấp trong đầu vào tiêu chuẩn(hoặc console).
Mặc định, Kotlin chạy trên JVM và cung cấp trực tiếp quyền truy cập vào một thư viện bộ sưu tập phong phú và hiệu quả với các cấu trúc dữ liệu tổng quát như mảng có kích thước động (ArrayList), bản đồ và tập hợp dựa trên hash (HashMap/HashSet), bản đồ và tập hợp có thứ tự dựa trên cây (TreeMap/TreeSet). Sử dụng một hash-set của số nguyên để theo dõi các giá trị đã đạt được khi áp dụng hàm f, phiên bản chủ nghĩa cơ bản của giải pháp cho vấn đề có thể được viết như sau:
fun main() {
var n = readln().toInt() // read integer from the input
val reached = HashSet() // a mutable hash set
while (reached.add(n)) n = f(n) // iterate function f
println(reached.size) // print answer to the output
}Không cần xử lý trường hợp đầu vào bị định dạng sai trong lập trình cạnh tranh. Định dạng đầu vào luôn được chỉ định một cách chính xác trong lập trình cạnh tranh, và đầu vào thực tế không thể lệch khỏi đặc tả đầu vào trong đề bài. Đó là lý do tại sao bạn có thể sử dụng readln() của Kotlin. Nó khẳng định rằng chuỗi đầu vào tồn tại và ném ra một ngoại lệ nếu không. Tương tự, String.toInt() ném ra một ngoại lệ nếu chuỗi đầu vào không phải là số nguyên.
fun main() {
var n = readLine()!!.toInt() // read integer from the input
val reached = HashSet() // a mutable hash set
while (reached.add(n)) n = f(n) // iterate function f
println(reached.size) // print answer to the output
}Lưu ý việc sử dụng toán tử phủ định null !! sau lời gọi hàm readLine(). Hàm readLine() của Kotlin được định nghĩa để trả về một kiểu có thể là nullString? và trả về null khi kết thúc đầu vào, điều này một cách rõ ràng buộc nhà phát triển phải xử lý trường hợp thiếu đầu vào.
Không cần xử lý trường hợp đầu vào bị định dạng sai trong lập trình cạnh tranh. Trong lập trình cạnh tranh, định dạng đầu vào luôn được chỉ định chính xác và đầu vào thực tế không thể chệch khỏi đặc tả đầu vào trong đề bài. Đó là lý do tại sao toán tử phủ định null !! cơ bản thực hiện điều này – khẳng định rằng chuỗi đầu vào tồn tại và ném ra một ngoại lệ nếu không. Tương tự, String.toInt().
Tất cả các sự kiện lập trình cạnh tranh trực tuyến đều cho phép việc sử dụng mã đã viết trước, do đó, bạn có thể định nghĩa thư viện của riêng mình các hàm tiện ích được thiết kế cho lập trình cạnh tranh để làm cho mã giải quyết thực tế của bạn trở nên dễ đọc và viết hơn một chút. Sau đó, bạn có thể sử dụng mã này như là một mẫu cho các giải pháp của bạn. Ví dụ, bạn có thể định nghĩa các hàm trợ giúp sau để đọc đầu vào trong lập trình cạnh tranh:
private fun readStr() = readln() // string line
private fun readInt() = readStr().toInt() // single int
// similar for other types you'd use in your solutions
private fun readStr() = readLine()!! // string line
private fun readInt() = readStr().toInt() // single int
// similar for other types you'd use in your solutionsLưu ý việc sử dụng private bộ điều chỉnh truy cập ở đây. Mặc dù khái niệm về bộ điều chỉnh try cập không liên quan đến lập trình cạnh tranh, nó cho phép bạn đặt nhiều tệp giải pháp dựa trên cùng một mẫu mà không gặp lỗi do các khai báo công khai xung đột trong cùng một gói.
2. Ví dụ về toán tử hàm: Vấn đề Số Dài
Đối với những vấn đề phức tạp hơn, thư viện rộng lớn về các hoạt động hàm trên bộ sưu tập của Kotlin trở nên hữu ích để giảm mã mẫu và chuyển đổi mã thành một đường ống biến đổi dữ liệu tuyến tính từ trên xuống dưới và từ trái sang phải. Ví dụ, vấn đề Bài toán B: Số Dài sử dụng một thuật toán tham lam đơn giản để triển khai và có thể được viết bằng cách này mà không cần một biến có thể thay đổi nào:
fun main() {
// read input
val n = readln().toInt()
val s = readln()
val fl = readln().split(" ").map { it.toInt() }
// define local function f
fun f(c: Char) = '0' + fl[c - '1']
// greedily find first and last indices
val i = s.indexOfFirst { c -> f(c) > c }
.takeIf { it >= 0 } ?: s.length
val j = s.withIndex().indexOfFirst { (j, c) -> j > i && f(c) < c }
.takeIf { it >= 0 } ?: s.length
// compose and write the answer
val ans =
s.substring(0, i) +
s.substring(i, j).map { c -> f(c) }.joinToString("") +
s.substring(j)
println(ans)
}fun main() {
// read input
val n = readLine()!!.toInt()
val s = readLine()!!
val fl = readLine()!!.split(" ").map { it.toInt() }
// define local function f
fun f(c: Char) = '0' + fl[c - '1']
// greedily find first and last indices
val i = s.indexOfFirst { c -> f(c) > c }
.takeIf { it >= 0 } ?: s.length
val j = s.withIndex().indexOfFirst { (j, c) -> j > i && f(c) < c }
.takeIf { it >= 0 } ?: s.length
// compose and write the answer
val ans =
s.substring(0, i) +
s.substring(i, j).map { c -> f(c) }.joinToString("") +
s.substring(j)
println(ans)
}
Trong đoạn mã dày đặc này, ngoài các biến đổi bộ sưu tập, bạn cũng có thể thấy những tính năng tiện lợi của Kotlin như các hàm cục bộ và toán tử Elvis ?:, cho phép diễn đạt các kiểu như “lấy giá trị nếu nó là số dương hoặc sử dụng độ dài nếu không” với các biểu thức ngắn gọn và đọc được như .takeIf { it >= 0 } ?: s.length, nhưng với Kotlin, cũng hoàn toàn tốt để tạo các biến có thể thay đổi bổ sung và diễn đạt cùng mã theo kiểu chủ nghĩa.
Để làm cho việc đọc đầu vào trong các nhiệm vụ lập trình cạnh tranh như thế này ngắn gọn hơn, bạn có thể có danh sách các hàm đọc đầu vào hữu ích sau:
private fun readStr() = readln() // string line
private fun readInt() = readStr().toInt() // single int
private fun readStrings() = readStr().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of intsprivate fun readStr() = readLine()!! // string line
private fun readInt() = readStr().toInt() // single int
private fun readStrings() = readStr().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints
Với những hàm trợ giúp này, phần mã để đọc đầu vào trở nên đơn giản hơn, theo dõi chặt chẽ đặc tả đầu vào trong câu chuyện vấn đề từng dòng:
// read input
val n = readInt()
val s = readStr()
val fl = readInts()Lưu ý rằng trong lập trình cạnh tranh, thường quy ước sử dụng tên ngắn gọn hơn cho biến so với quy tắc thông thường trong thực hành lập trình công nghiệp, vì mã nguồn chỉ được viết một lần và không được hỗ trợ sau đó. Tuy nhiên, những tên này thường vẫn có ý nghĩa — a cho mảng, i, j, và các biến khác cho chỉ số, r và c cho số dòng và số cột trong bảng, x và y cho tọa độ, và như vậy. Việc giữ nguyên tên cho dữ liệu đầu vào như đã cho trong đề bài là dễ dàng hơn. Tuy nhiên, vấn đề phức tạp hơn đòi hỏi nhiều mã nguồn hơn, dẫn đến việc sử dụng tên biến và hàm dài giải thích hơn.
3. Một số mẹo và thủ thuật
Các vấn đề lập trình cạnh tranh thường có đầu vào như sau:
Dòng đầu tiên của đầu vào chứa hai số nguyên n và k
Trong Kotlin, dòng này có thể được phân tích một cách ngắn gọn với câu lệnh sau sử dụng khai báo hủy từ một danh sách số nguyên:
val (n, k) = readInts()Có thể muốn sử dụng lớp java.util.Scanner của JVM để phân tích định dạng đầu vào ít cấu trúc hơn. Kotlin được thiết kế để tương tác tốt với các thư viện JVM, vì vậy việc sử dụng chúng cảm thấy tự nhiên trong Kotlin. Tuy nhiên, cần lưu ý rằng java.util.Scanner rất chậm. Thực tế, phân tích 105 số nguyên trở lên với nó có thể không vừa với giới hạn thời gian 2 giây điển hình, trong khi một cách đơn giản của Kotlin split(" ").map { it.toInt() } có thể xử lý.
Việc viết đầu ra trong Kotlin thường là đơn giản với việc gọi println(…) và sử dụng chuỗi mẫu của Kotlin. Tuy nhiên, cần chú ý khi đầu ra chứa khoảng 105 dòng trở lên. Phát ra quá nhiều cuộc gọi println quá chậm, vì đầu ra trong Kotlin tự động đưa ra sau mỗi dòng. Một cách nhanh hơn để viết nhiều dòng từ một mảng hoặc danh sách là sử dụng hàm joinToString() với "\n" làm phân tách, như sau:
println(a.joinToString("\n")) // each element of array/list of a separate line4. Học Kotlin
Kotlin dễ học, đặc biệt là đối với những người đã biết Java. Một giới thiệu ngắn về cú pháp cơ bản của Kotlin cho những nhà phát triển phần mềm có thể được tìm thấy trực tiếp trong phần tham khảo của trang web bắt đầu từ cú pháp cơ bản.
IDEA có bộ chuyển đổi Java sang Kotlin tích hợp sẵn. Nó có thể được sử dụng bởi những người quen thuộc với Java để học các cú pháp tương ứng của Kotlin, nhưng nó không hoàn hảo và vẫn đáng để làm quen với Kotlin và học qua series của Kotlin.
Một nguồn tài nguyên tuyệt vời để nghiên cứu cú pháp Kotlin và API của thư viện tiêu chuẩn Kotlin là Series Kotlin Free.
-> Kho tài liệu Free học Kotlin từ A->Z
Chúc mừng độc giả Cafedev đã thăm qua bài chia sẻ của chúng tôi về “Kotlin for competitive programming”! Hy vọng rằng bạn đã tìm thấy những thông tin hữu ích và động lực mới để khám phá thế giới lập trình cạnh tranh với sự hỗ trợ mạnh mẽ từ Kotlin. Đừng ngần ngại đặt câu hỏi và chia sẻ ý kiến tại Cafedev để cùng nhau xây dựng một cộng đồng lập trình đầy sôi động và sáng tạo. Hãy tiếp tục đồng hành cùng Cafedev, nơi kết nối niềm đam mê và kiến thức lập trình!”
Các nguồn kiến thức MIỄN PHÍ VÔ GIÁ từ cafedev tại đây
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của Cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
