Google Code Jam 2013 – Qualification Round 1C

ตกรอบทั้งแผ่นดิน :\ rank 2691

รอบนี้เหมือนจะง่ายเลยครับ ก็

# Consonants

ข้อนี้ให้ string มา แล้วจะมีพยัญชนะติดกันหลายๆ ตัว ถามว่ามี substring ที่มีพยัญชนะติดกันมากกว่า n ตัวกี่ substring

(substring คือส่วนใดส่วนหนึ่งของ string ตั้งแต่ 1 ตัวข้ึนไป และ substring เขียนเหมือนกันแต่เป็นคนละตัวได้ถ้าตัดมาจากคนละท่อนกัน คือจุดเริ่มต้นหรือจุดสิ้นสุดเป็นคนละจุด)

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

ข้อนี้ large ไม่ทันครับ ไฟล์มัน 4MB มีข้อดัก 5 ข้อที่ string น่าจะหลายล้านตัว (เปิดไฟล์มา sublime ผมค้าง หน้าจอมีแต่ rrrrrrrrrrrrrr)

# Pogo

ผมคิดว่ามันง่ายนะ แต่ผมไม่รู้เรื่องนี้

ให้หาเส้นทางจาก (0,0) ไปจุดที่กำหนด (อาจจะตำแหน่งติดลบได้) เดินทะแยงไม่ได้ โดยเดินครั้งแรกจะไปในทิศทางนั้น 1 จุด ครั้งที่ 2 ไป 2 จุด ฯลฯ ห้ามเกิน 500 ก้าว และข้อใหญ่ต้องตอบวิธีที่สั้นที่สุดเท่านั้น

# The Great Wall

ข้อนี้นี่อ่านแล้วยาวแต่สนุกดีครับ

กำแพงเมืองจีนยาวในแนวแกน x จาก -อนันต์ – +อนันต์ ถูกเผ่าต่างๆ โจมตีเข้ามาในแต่ละวัน โดยมีการกำหนดค่าเผ่าดังนี้

– วันแรกที่เข้าโจมตี
– จำนวนครั้งที่เข้าตี
– ตำแหน่งที่เข้าตี (range)
– ความแรงของการโจมตี
– วันต่อๆ ไปที่เข้าตี (จะเข้าโจมตีทุกๆ n วัน ตามค่านี้ จนกว่าจะครบจำนวนครั้ง)
– ระยะทางที่เผ่าเคลื่อนที่ไปในการโจมตีครั้งต่อๆ ไป
– ความแรงในการโจมตีครั้งต่อๆ ไป (จะลดหรือเพิ่มตามค่านี้ตลอดทุกการโจมตี)

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

ข้อนี้กลับมาได้ใช้ class อีกแล้วครับ ผมไม่แน่ใจว่า x position มันติดลบได้มั้ย เลยเขียน class ที่รองรับตำแหน่งติดลบได้ด้วย แล้วก็ยังมีระบบ rebuild queue อีกด้วย

ตอนแรกผมเขียน generator (function `__iter__`) ไว้สร้างการเข้าตีทั้งหมด แต่ผมพบว่าเวลาจะโค้ดผมน่าจะไล่ไปดูว่าวันนี้ใครจะตีบ้าง ก็ควรจะ generate ของแต่ละวันมาน่าจะดีกว่า เลยเขียน `atk_day` ซึ่งก็ต้องบวกลบเลขกันนิดนึง

สิ่งที่พลาดนานที่สุดในข้อนี้คือ range ครับ ผมนึกว่ามันคือ [0, 2] แต่จริงๆ มันคือ [0, 2) (ตำแหน่งที่ 2 ไม่มีการเข้าตี) แล้วก็มี test case ตัวอย่างที่ผิดด้วย แต่คำตอบมันถูก ทำผมเสียเวลา debug แต่พอแก้ได้ปุ๊บก็ทำถูกได้ก่อนเค้าประกาศแก้ไขโจทย์

เช่นเดียวกัน ข้อ large ข้อนี้รันไม่ทัน นั่งเช็คๆ ดูเหมือนว่าแค่ generate attack for tribes on everyday ก็ไม่ทันกินแล้ว :3

on Google Code Jam Qualification Round 2012

ผ่านไปแล้วนะครับ กับรอบคัดเลือก 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 อีก น่าจะทัน ปรากฎว่าคิดไม่ทันเสร็จครับผลลัพท์มันออกมาแล้ว ผมแทบไม่เชื่อสายตา รีบส่งคำตอบไปซึ่งผลออกมาว่าถูก เลยต้องหันไปขอบคุณปาฎิหาริย์จากมาโดกะเลย

ใครว่าการมีความหวังน่ะเป็นสิ่งที่ผิด ฉันจะตอบกลับไปว่าไม่ใช่เลย

— Kaname Madoka

————-

มาถึงข้อสุดท้ายครับคือ 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 แต่พอยกเลิกการใช้เทมเพลทรู้สึกว่าจะเขียนได้ไวขึ้นอีก