Google Codejam 2013 – 1B

รอบนี้รู้สึกว่าเป็นรอบที่ทำได้มากที่สุดแล้วครับ

# Osmos

ข้อนี้เอากฎมาจากเกม [Osmos](http://www.hemispheregames.com/osmos/) ก็คือเราเป็นตัวที่มีขนาดนึง และต้องกินตัวที่มีขนาดน้อยกว่าเราเท่านั้น จากนั้นเราจะมีขนาดใหญ่ขึ้นตามขนาดตัวที่เรากินเข้าไป ถามว่า จากตัวอื่นๆ ให้มา และขนาดของเรา ต้องเพิ่มลบตัวอื่นๆ กี่ครั้งจึงจะสามารถกินได้ทุกตัว

เป็นครั้งแรกครับที่ใช้ OOP แก้โจทย์แข่งขัน ตอนแรกจะใช้ closure แบบ JavaScript แต่เมาๆ กับมันเลยไม่ได้

ทีแรกผมใช้วิธีว่าถ้ากินไม่ได้ ให้หาตัวเล็กที่สุดแล้วลองกินตัวขนาด(ตัวเอง-1) เข้าไปดูว่าจะกินตัวนั้นได้มั้ย ถ้าไม่ได้ก็ให้ลบทุกตัวที่เหลือออกให้หมด ซึ่งแก้ test case ตัวอย่างได้ แต่ test case จริงผิด (เป็นความต่างระหว่างรอบคัดเลือกเลยที่รอบคัดเลือก test case มักจะเก็บกรณีให้ครบทุกกรณี แต่เหมือนปีนี้จะไม่เป็นแบบนี้แล้วแฮะ)

ก็เกือบจะยอมแล้วครับเพราะปกติผิดปุ๊บจะโยนทิ้งเลย แต่ไปนึกได้ว่าจริงๆ แล้วเราสามารถกิน(ตัวเอง-1) รัวๆ จนกว่าจะกินตัวต่อไปได้ เมื่อกินแล้วก็ไปกินตัวใหญ่ตัวถัดไปเรื่อยๆ ได้อีกได้ ก็เลยเพิ่มกรณีเข้าไปแล้วก็สามารถแก้ test case ได้สำเร็จ

ผลปรากฏว่า เหมือนจะมีบั๊กอีก A-large ผิด :'(

ข้อนี้นี่ผมรู้สึกเลยว่าถ้าเป็นปีที่แล้วหรือปีก่อนๆ อาจจะทำไม่ได้ อาจจะล้มเลิกไปเสียก่อน

# Falling Diamonds

ผมไม่ถนัดโจทย์แนวความน่าจะเป็น ถามว่ามีโอกาสเท่าไรปุ๊บผมไม่อ่านต่อแล้ว ปีแรกเคยพยายาม GoroSort อ่านจบนั่งนึกยังไงก็คิดอะไรไม่ออกเลย

# Garbled

ข้อนี้ทำ*เหมือนจะ*ได้ครับ คือให้ dictionary มา ถามว่าประโยคที่ให้มาพิมพ์ผิดอย่างน้อยกี่ตัว โดยที่ประโยคจะเป็นคำหลายๆ คำใน dictionary มาเรียงกันโดยไม่มีเว้นวรรค

ผมใช้วิธีคล้ายๆ treasure คือไล่จับคู่คำไปเรื่อยๆ จนครบ dictionary แล้วก็มีทางลัดให้มันออกเร็วๆ นิดหน่อย ถ้าถูกทุกคำก็สามารถหาคำต่างๆ ที่ประกอบกันได้ใน 30 วินาที แต่พอถึง cxdejax มันใช้เวลารัน 5 นาทีถึงจะออก แล้วโปรแกรมก็ค้างไปเลย

(ส่วนถ้าใช้ dictionary test ซึ่งใส่แต่คำที่ใช้ไว้ใน test case ทดสอบนั้นแป๊บเดียวออกเลยครับ)