วงแหวนเว็บ

neizod's speculation

insufficient data for meaningful answer

Code Jam 2013 รอบ 1A

Saturday, April 27, 2013, 11:17 AM

รอบนี้ตอนแรกว่าจะปล่อยผ่านเพราะอุตสาห์มากทม.ทั้งที อยากไปร่วมฟาร์มเสา 8 กับเหล่า agent ทั้งหลายเสียหน่อย … แต่คิดไปคิดมา คราวก่อนก็วืดเพราะมัวแต่ไปคาราโอเกะ เลยคิดว่าควรให้ความสำคัญและลงพลังกับการแข่งให้มากที่สุดจะดีกว่า

Bullseye

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

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

\[\begin{align} F(n) &= (2r+1) + (2r+1 + 4) + (2r+1 + 8) + \cdots + (2r+1 + 4(n-1)) \\ &= \sum_{k=0}^{n-1} \left( 2r+1 + 4k \right) \\ &= n(2r+1) + 4 \sum_{k=0}^{n-1} k \\ &= n(2r+1) + \frac{4n(n-1)}{2} \\ &= n(2r+1) + 2n(n-1) \end{align}\]

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

\[\begin{align} 0 &= n(2r+1) + 2n(n-1) - t \\ &= 2n^2 - (2r-1)n - t \end{align}\]

ก็จะได้ว่า

\[\begin{align} a &= 2 \\ b &= 2r - 1 \\ c &= -t \\ n &= \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \end{align}\]

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


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

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

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

neizod

author