Code Jam 2013 รอบ 1A

รอบนี้ตอนแรกว่าจะปล่อยผ่านเพราะอุตสาห์มากทม.ทั้งที อยากไปร่วมฟาร์มเสา 8 กับเหล่า agent ทั้งหลายด้วย

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

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

เราเริ่มจากสังเกตว่าวงกลมแรกจะใช้สีระบายไป 2r + 1 วงกลมถัดๆ มาใช้ 2r + 1 + 4 และ 2r + 1 + 8 ดังนั้นจะตั้งเป็นสมการได้ว่า

used_color(n) = (2r+1) + (2r+1 + 4) + (2r+1 + 8) + ... + (2r+1 + 4(n-1))
              = summation (2r+1 + 4k) for k in [0 .. n-1]
              = n(2r+1) + 4 * summation k for k in [0 .. n-1]
              = n(2r+1) + 4n(n-1)/2
              = n(2r+1) + 2n(n-1)

แต่เนื่องจากสิ่งที่เรารู้คือ t = used_color(n) และต้องการคำนวณกลับเพื่อหา n ดังนั้น

0 = n(2r+1) + 2n(n-1) - t
  = 2n^2 - (2r-1)n - t

ก็จะได้ว่า

a = 2
b = 2r - 1
c = -t
n = (-b ± sqrt(b^2 - 4ac)) / 2a

ถึงตอนนี้ก็แค่แก้สมการข้างบน ได้คำตอบมา 2 อันก็เลือกเอาคำตอบที่มากกว่า 0 แล้วปัดเศษทิ้งครับ

---

ข้อสองคิดวิธี optimize ไม่ออก เลยเขียน recursive ไป (loop ใหญ่สุดของแบบเล็กคือ 60 ล้าน ก็ยัง brute-force ออกในเวลาที่รับได้) แต่เสียดายที่คิดผิด debug ไม่ทัน

ส่วนข้อสามแนวคิดคือหาตัวคูณร่วมน้อยของเลขทั้ง set ที่เค้าให้ แล้วก็แยกตัวประกอบมันออกมาเป็น list นึง ทีนี้ถ้า list มันใหญ่กว่าขนาดของการ์ดทั้งหมดก็ merge ตัวเลขใน list นี้ด้วยการคูณจนกว่ามันจะมีขนาดเท่ากับการ์ด เท่านี้เอง (อันนี้ออกแค่ข้อเล็ก)

อันดับระหว่างแข่งคือ 18xx พอจบรอบตรวจคะแนนจริงก็เด้งกลับมาที่ 1377 เพราะข้อที่ส่งไปถูกหมด (แต่ก็ยังไม่เพียงพอสำหรับผ่านเข้ารอบต่อไปอยู่ดี) ... ไม่เป็นไรรอบหน้าเอาใหม่ เนอะ ^^)v