ผ่านไปแล้วนะครับ กับรอบคัดเลือก Code Jam 2012 ไหนๆ ดองมานานจนลืมแล้วเล่าสักหน่อยดีกว่า
ก็ วันนั้นผมก็ตั้งปลุกตัวเองไว้ว่าตีห้าครึ่ง พอหกโมงเช้าที่เริ่มแข่งแบบว่าง่วงมาก แต่ก็อ่านโจทย์สักหน่อย
เจอข้อแรกไป… Speaking in Tongues โจทย์มีอยู่ว่าให้ข้อความที่ทำการเข้ารหัสแบบ 1:1 แล้ว คือสมมุติว่า a แปลงเป็น z ก็จะเป็น z เสมอ คราวนี้ล่ะผมนอนต่อไม่ได้ละ เลยลงมือเผาๆ ให้เสร็จจะได้นอน
คือ โจทย์จะใช้วิธีประมาณว่าให้ลองเดาจากโจทย์ตัวอย่างดู ซึ่งผมก็ขี้เกียจทำ map table เลยเขียนโปรแกรมให้มันวิเคราะห์โจทย์อัตโนมัติไปเลยโดยเอาข้อตัวอย่างและคำตอบใส่ไป มันก็จะสร้าง map table มา แล้วก็ตอบ ทีนี้ปรากฎว่า**โดนดักควาย** ว่ามันไม่มีตัว q ในโจทย์ แต่กว่าจะรู้ก็ตอนขอ test case แล้ว
ทีนี้ผมก็เดาละ z มันได้ q (ถ้าผมจำไม่ผิดนะ) งั้นผมมั่ว q->z เลยแล้วกัน แล้วก็ใส่ใน map table ไว้ ปรากฎว่าผิด ผมลองดูจาก input มันมีข้อนึงไล่ a-z อยู่แล้ว ก็แค่ดูว่าตัว q มันเป็นตัวลำดับไหน เลยให้มันแทน q ด้วย ! แต่ผมไม่เจอ ! อีกแล้ว… ก็เลยช่างมัน ผ่านแล้วมั้ง ส่ง!
ที่ไหนได้ล่ะครับ ก็ผมเซตไปแล้วไง q->z ผมก็เลยส่งคำตอบไปผิดๆ พอมาไล่อีกที อ้าว map table มันเซตไว้แล้ว ก็เสียค่าโง่ไป
หลังจากนั้นแล้ว… นอนดีกว่า
———–
บ่ายสองผมตื่นมาทำต่อ เริ่มที่ข้อ recycle ที่ดูจะง่ายกว่า dance โจทย์มีอยู่ว่าจำนวน n เนี่ย สามารถตัดตัวเลขจากด้านหลังไปใส่ด้านหน้าได้ จะตัดกี่ตัวก็ได้ เช่นตัวเลข 12345 มันจะได้ 51234, 45123, 34512, 23451 คำถามคือ ในช่วงที่กำหนด มีตัวเลขแบบนี้กี่ชุด ถ้าตัวเลขแรกเป็นตัวเดียวกัน ตัวเลขที่เกิดจากการสลับแล้วซ้ำกันจะไม่นับ
โอเค วิธีคิดผมก็ตามโจทย์เป๊ะ ตัด string จากด้านหลังไป ตั้งแต่ หนึ่งตัว สองตัว ไปเรื่อยๆ จนถึง n-1 แล้วก็วนลูปในช่วงที่กำหนดมา โชคดีว่ากรณีซ้ำไม่นับอยู่ใน example case ผมก็เลยเจอบั๊ก แล้วก็นั่งไล่ดูไปทีละตัวเลขของข้อนั้นเลยว่ามีตรงไหนทำไมนับเกิน ดูไปสักพักค่อยแบบว่า อ้อ ลืมกรณีซ้ำ ฉะนั้นผมก็เลยให้มันเซฟทุก combination ที่เป็นไปได้ทั้งหมดลง array!
ก็ปรากฎว่าข้อเล็กผ่านไปได้ด้วยดีครับ แค่นี้ก็เข้ารอบ แต่ข้อใหญ่นี่สิ ผมรันไปแล้วมันไม่ออกเร็วเท่าข้อเล็ก ก็เริ่มระแวงแล้วว่าน่าจะทำอะไรผิด ก็ไล่ๆ โค้ดดูว่าปรับตรงไหนได้แต่ก็ไม่ได้ปรับ เลยว่างั้นเย็นๆ จะเขียนแบบ cluster ให้มันกระจายงานแต่ละข้อไปทีละเครื่อง แล้วแถมจะได้ multicore processing อีก น่าจะทัน ปรากฎว่าคิดไม่ทันเสร็จครับผลลัพท์มันออกมาแล้ว ผมแทบไม่เชื่อสายตา รีบส่งคำตอบไปซึ่งผลออกมาว่าถูก เลยต้องหันไปขอบคุณปาฎิหาริย์จากมาโดกะเลย
ใครว่าการมีความหวังน่ะเป็นสิ่งที่ผิด ฉันจะตอบกลับไปว่าไม่ใช่เลย
————-
มาถึงข้อสุดท้ายครับคือ Dance โจทย์ประมาณว่ามีกรรมการสามคนให้คะแนน ซึ่งแต่ละคนจะให้คะแนนที่ min,max ห่างกันไม่เกิน 1 แต่จะมีกรณีพิเศษที่ห่างกันไม่เกิน 2 โจทย์ถามว่า มีการแสดงจำนวนครั้งเท่านี้ มีคะแนนรวมของแต่ละคนเท่านี้ และมีจำนวนครั้งที่ได้คะแนนพิเศษเท่านี้ ถามว่า มีกี่ครั้งที่ได้คะแนนเกินที่กำหนด
วิธีคิดข้อนี้ผมใช้ generator คิด โดยไล่กรณีคะแนนที่เป็นไปได้ทั้งหมดจาก 1-10 ซึ่งพบว่าคะแนนของกรรมการคนอื่นจะเป็นดังนี้ (สมมุติว่าได้ 1 คะแนน): [1, 1, 1], [1, 0, 0], [1, 1, 0] และกรณีพิเศษคือ [1, 1, -1], [1, -1, -1], [1, 0, -1]
ผมพบว่าการให้โปรแกรมลองเดา โดยพยายามหลีกเลี่ยงกรณีที่ได้คะแนนกรณีพิเศษเท่าที่เป็นไปได้โปรแกรมก็จะสามารถทำโจทย์ได้อย่างถูกต้องแล้ว แต่พอรันเทสเคสเจอปัญหาคือ กรณี 1 และ 0 มันคิดออกมาเป็นคะแนนติดลบ ก็ต้องแก้โดย hardcode ไปว่าคะแนนรวมได้ 0 ให้ตอบ [0,0,0] 1 ตอบ [1,0,0] เท่านั้น
สำหรับข้อยากอันนี้ใช้เวลารันพอๆ กับข้อง่ายครับ
——————-
ปีนี้ผมไม่ได้ใช้ template ทำโจทย์นะครับ ปีก่อนๆ ผมจะมี template ซึ่งมันจะทำให้เขียนได้ช้ากว่าเพราะต้องคำนึงถึงการส่งข้อมูลด้วย ยิ่งเทมเพลทรุ่นหลังๆ นี่ผมเล่น multiprocessing เลย เวลาส่งข้อมูลต้องระวัง data type แต่พอยกเลิกการใช้เทมเพลทรู้สึกว่าจะเขียนได้ไวขึ้นอีก