วิเคราะห์โจทย์ TOI17 ข้อ Noodle

โจทย์

มีช่องทางจัดจำหน่ายเส้นขนมจีนทั้งหมด $N$ ช่องทาง(ที่ติดกันเป็นเส้นตรง) มีร้านค้าขนมจีนอยู่ทั้งหมด $M$ ร้าน

โดยช่องทางจัดจำหน่ายหมายเลข $i$ จะมีปริมาณขนมจีน $a_i$

ทีนี้แต่ละร้านจะเลือกช่วงของช่องทางจัดจำหน่ายที่ติดกัน เพื่อซื้อขนมจีน

• ร้านที่ 1 ได้ช่องที่ $1$ ถึง $x_1$
• ร้านที่ 2 ได้ช่องที่ $x_1+1$ ถึง $x_2$
• ไปเรื่อยๆ จนถึงร้านที่ $M$ ได้ช่องที่ $x_{M-1}+1$ ถึง $N$

โดยค่า $x_i$ ของแต่ละร้านเนี่ยเรากำหนดเองได้ เพื่อที่จะแบ่งช่องทางให้แต่ละร้าน
หลังจากเลือกแบ่งช่องทางให้แต่ละร้านเสร็จแล้ว แต่ละร้านจะเลือกช่องทางจัดจำหน่ายที่ได้เยอะที่สุดมาทั้งหมด $K$ ช่องทางจากช่องทางในช่วงของร้านนั้นๆเอง เพื่อเลือกรับขนมจีน

ถามว่าถ้าแบ่งช่องทางให้แต่ละร้านให้ดีที่สุดแล้ว ร้านที่มีขนมจีนน้อยที่สุดจะได้ปริมาณเท่าไหร่

โดยนิยามว่าดีที่สุดคือ ต้องการให้ร้านที่ได้รับขนมจีนน้อยที่สุดเนี่ย ได้ปริมาณขนมจีนให้ได้มากที่สุดเท่าที่เป็นไปได้

---

ข้อมูลนำเข้า

บรรทัดที่ 1 เป็นจํานวนเต็ม 3 จํานวน
แต่ละจํานวนถูกคั่นด้วยช่องว่าง ได้แก่ $N, M, K$ แทนจํานวนช่องทางการรับเส้นขนมจีนทั้งหมด จํานวนร้านค้า และจํานวนช่องทางการรับเส้นขนมจีน ที่แต่ละร้านค้าสามารถรับขนมจีนออกมาได้
โดยที่ $5 \leq N \leq 100\,000, 2 \leq M \leq 100, 1\leq K \leq 4\,000$ และ $M \times K \leq N$

อีก $N$ บรรทัดถัดมา แต่ละบรรทัด มีจํานวนเต็ม $a_i$ แทนปริมาณเส้นขนมจีนที่เข้าไปรับได้ของช่องทางที่ $i$ โดยที่ $1 \leq a_i \leq 500\,000$

ข้อมูลส่งออก

มีบรรทัดเดียว แสดงปริมาณรวมของเส้นขนมจีนของร้านที่ได้ขนมจีนไปน้อยที่สุด ถ้าเราจัดแบ่งช่องทางให้ได้ดีที่สุดแล้ว

---

ตัวอย่างข้อมูลนำเข้าและข้อมูลส่งออก

คำอธิบายตัวอย่างแรก:

แบ่งช่องทางการรับขนมจีนตามนี้:

• ร้านที่ 1: ช่องที่ 1 ถึง 6
• ร้านที่ 2: ช่องที่ 7 ถึง 9
• ร้านที่ 3: ช่องที่ 10 ถึง 12

ทำให้ร้านที่ 1 จะเลือกจาก ช่องทางที่ 2, 4, และ 6 เลยได้รวมเป็น 21 ที่น้อยกว่าอีก 2 ร้านที่ได้ 22 และ 27 ตามลำดับ

---

วิเคราะห์โจทย์

ก่อนอื่นเลย เราจะมาคิดในแบบที่มีแค่ 1 ร้านก่อน

ถ้ามีแค่ร้านเดียวมันก็ง่ายอ่ะเนอะ เราก็แค่เก็บค่ามากที่สุด $K$ ลำดับแรก แล้วเอามารวมกันเป็นคำตอบได้เลย

แต่ถ้ามีมากกว่า 1 ร้าน จะแบ่งช่องทางให้แต่ละร้านยังไงล่ะ?

พอจะแบ่งช่องทางให้แต่ละร้านมันก็ต้องมาเริ่มคิดละว่า แบ่งแค่ไหนเยอะหรือน้อยไปไหม เพราะถ้าเราไปโฟกัสกับร้านที่ได้น้อยที่สุดแล้วพยายามเพิ่มช่องทางให้เยอะๆ ร้านถัดมาก็อาจจะได้น้อยลงจนกลายเป็นร้านที่ได้น้อยที่สุดไปอีก แล้วแถมในโจทย์มีร้านต้องแบ่งตั้ง 100 ร้านก็จะวุ่นวายไปกันใหญ่

โจทย์เดิมในอีกมุมมอง

สมมติเปลี่ยนเป็นถามว่า ถ้าเราแบ่งให้แต่ละร้านได้ดีที่สุดแล้ว ร้านที่ได้ขนมจีนน้อยที่สุดยังได้ไม่น้อยกว่า $P$ รึเปล่า โดยที่ $P$ เป็นค่าที่เราสมมติขึ้นมาเอง

พอคิดแบบนี้เรื่องการแบ่งช่องทางก็จะง่ายขึ้น เพราะเราจะพยายามให้แต่ละร้านได้ความยาวช่วงที่สั้นที่สุดในขณะที่ผลรวมค่ามากที่สุด $K$ ลำดับแรกยังไม่น้อยกว่า $P$

สังเกตว่า ถ้าแบ่งช่องทางให้ร้านแรกได้ 3 ช่องเลย จะทำให้ร้านหลังๆ ได้ช่องทางที่เหลือไม่พอ เพราะร้านแรกเลือกช่องทางที่มีค่าขนมจีนสูงไปแล้ว ทำให้ร้านหลังๆ เลือกได้แค่ช่องทางที่เหลือที่มีค่าขนมจีนต่ำกว่า $P$
ทั้งๆที่ ร้านแรกสามารถเลือกช่องน้อยกว่านั้นได้

สาเหตุที่วิธีแบ่งช่วงแบบนี้ทำได้ดีที่สุดเพราะ ถ้าร้านแรกๆ เลือกใช้ช่องทางน้อย ร้านหลังๆ ก็จะมีโอกาสเลือกช่องที่มีค่าขนมจีนสูงได้มากขึ้น

การเพิ่ม/ลดค่า P

จริงๆ แล้วการเลือกค่า $P$ มีผลต่อความยาวช่องของแต่ละร้านที่เลือก

• ถ้าค่า $P$ น้อยจะทำให้แต่ละร้านเลือกช่วงสั้นๆ และเหลือช่วงให้ร้านสุดท้ายเยอะเกินความจำเป็น
• ถ้าค่า $P$ เยอะจะทำให้แต่ละร้านต้องเลือกช่วงยาวๆ เพื่อให้ได้มากให้ครบค่า $P$ ทำให้ร้านท้ายๆ มีช่องเลือกได้ไม่พอ

การเลือกค่า $P$ น้อยๆ จะทำให้ร้านแรกๆ เลือกช่วงสั้นๆ ทำให้ร้านหลังๆ เลือกได้ช่องทางที่เหลือเยอะเกินความจำเป็น แต่อย่างน้อยก็ยังแบ่งช่องทางให้ร้านสุดท้ายได้ แค่ค่าของร้านแรกๆ จะได้น้อยเกินกว่าที่โจทย์ต้องการ

แต่ถ้าลองใหม่ด้วยการเลือกค่า $P$ ที่สูงขึ้นล่ะ

พอค่า $P$ สูงเกินไป ร้านแรกๆ ก็จะเลือกช่วงยาวขึ้น แต่ทำให้ร้านหลังๆ เลือกได้ช่องทางที่เหลือน้อยลง แถมบางร้านไม่พอเลือกช่องทางเลยด้วยซ้ำ

พอคิดได้แบบนี้เราก็แค่ต้องหาค่า $P$ ที่มากที่สุดเพื่อเอาไปตอบคำถามในโจทย์เริ่มต้น

แต่ปัญหามันติดอยู่ที่ว่า ค่าขนมจีนแต่ละช่องมันสูงไปหน่อย(ตั้ง 500,000) ทำให้ถ้าจะลองเพิ่มค่า $P$ ทดลองไปเรื่อยๆตรงๆ เช่นลองเพิ่มทีละ 1 จะใช้เวลาในการคำนวณมากเกินไป

คำนวณค่าผลรวม K ตัวในช่วงยังไง

มีหลายวิธีให้เลือกแหละ แต่วิธีง่ายสุดก็คงเป็นการใช้ Multiset มาเก็บค่าที่มากที่สุดทั้ง $K$ ตัวไว้ แล้วพอมีค่าใหม่ก็เอาไปเทียบกับค่าในนั้นว่าค่าใหม่มากกว่าอะไรไหม

ถ้ามากกว่าก็ดึงค่าที่น้อยที่สุดใน Multiset ออกมา แล้วก็ทำแบบเดิมไปเรื่อยๆ

การเลือกค่า P

เราจะ Binary search ค่า $P$ และเอาค่า $P$ ที่ว่า ไปแบ่งช่วงต่อโดยให้แต่ละร้านได้ความยาวช่วงสั้นที่สุด แล้วดูว่าเกิดอะไรขึ้นบ้าง

• ถ้ายังแบ่งได้ทุกร้าน เราจะเพิ่มค่า $P$ เพื่อให้พยายามใช้ทุกช่องทางให้คุ้ม แล้วเก็บค่า $P$ ที่ทำได้ไว้
• ถ้าแบ่งไม่ได้ ด้วยเหตุผลว่าเลือกมากที่สุด $K$ ลำดับแล้วยังค่าไม่ถึง หรือแบ่งได้ไม่ถึงร้านสุดท้าย เราจะลดค่า $P$ เพื่อให้แบ่งให้ร้านหลังๆ ได้

หลังจากทำขั้นตอนนี้เสร็จแล้ว เราก็จะเอาค่า $P$ ที่มากที่สุดมาตอบได้เลย

และด้วยความว่าเราแค่ Binary search บนค่าผลรวมของขนมจีน ทำให้ต้องเช็กค่า $P$ จริงๆแค่ $\cal{}$$\mathcal{O}(\log(500\,000K))$ ครั้งก็พอ

Time Complexity: $\mathcal{O}(N\log(500\,000K)\log(K))$

Memory Complexity: $\mathcal{O}(N)$

Extra Challenge

1. ถ้าแต่ละร้านมีค่า $K$ เป็นของตัวเอง จะคิดแตกต่างจากวิธีเดิมยังไงบ้าง
2. ถ้าเปลี่ยนค่า $K$ เป็นตั้งแต่ 1 ถึง $K$ แล้วให้ตอบทุกค่า $K$ จะคิดแตกต่างจากวิธีเดิมยังไงบ้าง

ลิงก์

โจทย์ TOI17 ข้อ Noodle

https://programming.in.th/tasks/toi17_noodle