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

3 thoughts on “Google Code Jam 2013 – Qualification Round 1C”

  1. จริงๆ แล้ว การนับ substring น่าจะไม่ยาก คือ นับไปก่อนว่ามีตัวอักษรที่ติดกันกี่ตัว ดูว่ายาวกว่าหรือเท่ากับ n มั้ย และถ้าใช่ก็ Total Substring = (l-n+1) + (l-(n+1)+1) + (l-(n+2)+1) + … + (l-l+1) เพราะว่า substring ความยาว l จะมี substring ความยาว n อยู่ l-n+1 แบบ

    1. ลองแทนๆ ดูแล้วเหมือนว่าจะใช้สูตรนี้ได้แฮะ เพิ่งเคยเห็นสูตรนี้เหมือนกัน

Comments are closed.