neizod's speculation

insufficient data for meaningful answer

Code Jam 2013 รอบ 1A

Saturday, April 27, 2013, 11:17 AM

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

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

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

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

ก็จะได้ว่า

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


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

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

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