toi

TOI19 jewelry - สร้อยอัญมณี (Jewelry Necklace)

🏠 รวมเฉลย TOI19

💎 problem.pdf

🎉 solution.cpp

🤢 Math!!!

ข้อนี้ถ้าสังเกตุคือ ให้หาว่าในช่วง str[l..r] มี 'T' ติดกันมากสุดกี่ตัว

จาก ovservation แรกคือ ยิ่ง string ยาวขึ้น จำนวน T ที่ได้ก็ยิ่งมากขึ้น

• max_T(str[l..r]) <= max_T(str[l..r+1])
• max_T(str[l..r]) <= max_T(str[l-1..r])

ซึ่งการหา max_T ก็สมารถใช้แนวคิดแบบ Maximum Subarray (Kadane's Algorithm) แก้ได้ใน O(n)

Kadane max_subarray(arr[0..i]) = arr[i] + max(0, max_subarray(arr[0..i-1]))

แต่ในที่นี้จำนวน T มันจะต่างกันทีละ 1 ขั้นเท่านั้น เพราะเป็นจำนวนนับ

โดยที่เราจะแก้แบบทำสมการหาผลต่างแทน

• max_T(str[0..r]) <= max_T(str[0..r+1])
• max_T(str[0..r]) = max_T(str[0..r+1]) + K?

ว่าค่า K เป็นสมการที่มีหน้าตาอย่างไร

ลองดูตัวอย่างแรก

0
0
0
   F T T F T (sum = 0 + 0 + 0 = 0)

เมื่อ i = 0
เมื่อสนใจในช่วง [0..0]
มีจำนวน T ติดกันมากสุดคือ 0 ตามลำดับ
0
0
0  _
   F T T F T (sum = 0 + 0 + 0 = 0)
  [F] มี T ติดกันมากสุด 0

เมื่อ i = 1
เมื่อสนใจในช่วง [0..1], [1..1]
มีจำนวน T ติดกันมากสุดคือ 1, 1 ตามลำดับ
0
0
2  # #
   F T T F T (sum = 0 + 0 + 2 = 2)
    [T] มี T ติดกันมากสุด 1
  [F T] มี T ติดกันมากสุด 1

   * สังเกตุว่าเราตั้งให้ค่าข้างล่างเป็น 3 เลยเพราะรู้ว่าถ้าทำจนครบแล้ว มันจะมีค่าเป็น 3 แน่ๆ
   แปลว่าเวลาทำเราต้องรู้ว่ากลุ่ม T ตัวนี้ จริงๆแล้วมีทั้งหมดกี่ตัวกันแน่

เมื่อ i = 2
เมื่อสนใจในช่วง [0..2], [1..2], [2..2]
มีจำนวน T ติดกันมากสุดคือ 2, 2, 1 ตามลำดับ
0
2  # #
3  # # #
   F T T F T (sum = 0 + 2 + 3 = 5)
      [T] มี T ติดกันมากสุด 1
    [T T] มี T ติดกันมากสุด 2
  [F T T] มี T ติดกันมากสุด 2

   * เมื่อทำครบทุก T ในชุดนั้นแล้ว ค่าก็จะถูกต้อง ตรงตามค่าที่ทดไว้ฝั่งซ้าย

เมื่อ i = 3
เมื่อสนใจในช่วง [0..3], [1..3], [2..3], [3..3]
มีจำนวน T ติดกันมากสุดคือ 2, 2, 1, 0 ตามลำดับ
0
2  # #
3  # # # _
   F T T F T (sum = 0 + 2 + 3 = 5)
   ความหมายของจุดข้างบนคือ
      [T F] มี T ติดกันมากสุด 1
    [T T F] มี T ติดกันมากสุด 2
  [F T T F] มี T ติดกันมากสุด 2

เมื่อ i = 4
เมื่อสนใจในช่วง [0..4], [1..4], [2..4], [3..4], [4..4]
มีจำนวน T ติดกันมากสุดคือ 2, 2, 1, 1, 1 ตามลำดับ
0
2  # #
5  # # # # #
   F T T F T (sum = 0 + 2 + 5 = 7)
          [T] มี T ติดกันมากสุด 1
        [F T] มี T ติดกันมากสุด 1
      [T F T] มี T ติดกันมากสุด 1
    [T T F T] มี T ติดกันมากสุด 2
  [F T T F T] มี T ติดกันมากสุด 2

ans = 0 + 0 + 2 + 5 + 5 + 7 = 19

ถ้าลองทดได้ตามนี้ ก็เขียนโคดไม่ยากแล้ว

แล้วถ้าหากทำไปเรื่อยๆ กราฟควรจะหน้าตาประมาณนี้

แต่ต่อให้นึกภาพออกแต่ว่าเวลาคิด ไม่คิดว่าต้องหา T ทั้งก้อนเพื่อมาบวกกลับหลัง ก็ไม่สามารถแก้โจทย์ข้อนี้ได้

ใช้เวลา O(n) อย่างสวยงาม