รอบ 1A ติดเดินทางพอดีเลยไม่ได้เล่น (แถมพอกลับมาอ่านโจทย์แล้วมึนตึบไปไม่เป็นอีก) เพราะงั้นขอข้ามไปรอบอื่นๆ เลยละกัน

Steed 2: Cruise Control

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

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

พอได้แนวคิดที่แจ่มแจ้งโปร่งใสแล้ว ที่เหลือก็เพียงแค่โค้ดสั้นๆ เท่านี้

def arrive_time(dest, init, speed):
    return (dest-init) / speed

def cruise_speed(dest, horses):
    return dest / max(arrive_time(dest, *horse) for horse in horses)

def main():
    for case in range(int(input())):
        dest, n_horses = [int(n) for n in input().split()]
        horses = [tuple(int(n) for n in input().split()) for _ in range(n_horses)]
        print('Case #{}: {}'.format(case+1, cruise_speed(dest, horses)))

if __name__ == '__main__':
    main()

Stable Neigh-bors

ข้อสองรอบ 1B อ่านรอบแรกแล้วอาจคิดว่ายากมาก แต่จริงๆ แล้วก็ง่ายไม่แพ้ข้อแรกเลย ลองพิจารณาแบบเล็กที่มียูนิคอร์นแค่สามสีก่อน เริ่มแรกเราจะใส่ยูนิคอร์นที่มีสีซ้ำมากสุดเรียงกันไว้ในคอกนั้น แล้วสับหว่างด้วยยูนิคอร์นสีซ้ำกันรองๆ ลงมาจากทางด้านซ้ายและขวาตามลำดับ

\[B \rlap{ \overbrace{ \phantom{R\;BRY\;BR} }^{Red} } R\;BR \underbrace{Y\;BRY\;BY\;BY}_{Yellow}\]

การจัดคอกเมื่อมียูนิคอร์นสีแดง 3 ตัว สีเหลือง 4 ตัว และสีน้ำเงิน 5 ตัว

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

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

\[B \overbrace{\scriptstyle OBOB}^{Orange} R \overbrace{\scriptstyle GRGRGR}^{Green} \;BRY \overbrace{\scriptstyle VYVYVYVY\!}^{Violet} \;BRY\;BY\;BY\]

การจัดคอกเมื่อมียูนิคอร์นเพิ่มจากตัวอย่างข้างบน ได้แก่ สีน้ำเงินและสีส้มอย่างละ 2 ตัว สีแดงและสีเขียวอย่างละ 3 ตัว สีเหลืองและสีม่วงอย่างละ 4 ตัว

เสียดายที่ข้อนี้ลืมไปว่า str.replace ใน Python มันทำงานกับทุก pattern ที่เจอบน string (ชินไปหน่อยกับ vi ที่ :s/old/new มันทำแค่ครั้งแรก) แถมตอนนั้นลนๆ เวลาใกล้จะหมดไม่ได้ดูละเอียด เลยอดได้คะแนนเพราะความสะเพร่าอย่างไม่น่าเชื่ออีกแล้ว … ดังนั้นก็ขอละการโชว์โค้ดข้อนี้ละกัน :p

ส่วนข้อสามในรอบ 1B นี้อ่านโจทย์แล้วข้ามเลย อันที่จริงก็ต้องโทษตัวเองเนี่ยแหละที่นิสัยเสียไม่ยอมฝึกเขียนโปรแกรมสำหรับแก้ปัญหาบนกราฟซักที เฮ้อ

Ample Syrup

ข้อแรกรอบ 1C จะเห็นว่าทริคอยู่ตรงที่เราคำนวณพื้นที่ผิววงกลมแค่ครั้งเดียวของแพนเค้กอันใหญ่ที่สุดที่อยู่ด้านล่าง แล้วค่อยคำนวณพื้นที่ผิวด้านข้างแบบทรงกระบอกของแพนเค้กทุกอันที่เหลือ โดยมีวิธีการเลือกแพนเค้ก $K$ ชิ้นดังนี้

1. เลือกแพนเค้กชิ้นแรกที่มีขนาดพื้นที่วงกลมใหญ่สุด ($R$ ใหญ่สุด) ถ้ามีหลายชิ้นขนาดเท่ากัน ให้เลือกชิ้นที่มีความสูงมากสุด ($H$ ใหญ่สุด)
2. เลือกแพนเค้กอีก $K-1$ ชิ้น โดยเลือกเรียงลำดับจากพื้นที่ผิวด้านข้างมากที่สุด ($R \times H$ ใหญ่สุด)

แต่ว่าเราจะไม่ทำการเลือกตามข้างต้นเพียงรอบเดียว เพราะถ้าเกิดชิ้นที่เป็นฐาน ($R$ ใหญ่สุด) มีความสูงแค่นิดเดียว อาจมีชิ้นอื่นที่ไม่ได้ถูกเลือก แต่มีความสูงเยอะจนสุดท้ายแล้วมีพื้นที่ผิวรวมมากกว่าก็เป็นได้ ดังนั้นเราจะค่อยๆ เอาแพนเค้กที่เคยเป็นฐานทิ้งไปทีละชิ้นแล้วเลือกแพนเค้กตามกระบวนการข้างต้นใหม่เรื่อยๆ จนไม่เหลือแพนเค้กให้เลือกนั่นเอง

และนี่คือโค้ด

from math import pi

def calc_surface(pancakes):
    circle = pancakes[-1][0]**2
    cylinder = 2 * sum(pancake[0] * pancake[1] for pancake in pancakes)
    return pi * (circle + cylinder)

def max_syrup(k, pancakes):
    surfaces = []
    while len(pancakes) >= k:
        pancakes.sort()
        bottom = pancakes.pop()
        pancakes.sort(key=lambda x: x[0]*x[1], reverse=True)
        selected = pancakes[:k-1] + [bottom]
        surfaces += [calc_surface(selected)]
    return max(surfaces)

def main():
    for case in range(int(input())):
        n, k = [int(n) for n in input().split()]
        pancakes = [[int(n) for n in input().split()] for _ in range(n)]
        answer = max_syrup(k, pancakes)
        print('Case #{}: {}'.format(case+1, answer))

if __name__ == '__main__':
    main()

Core Training

ข้อสามรอบ 1C ทำได้แค่แบบเล็ก โดยมาจากความรู้เดิมที่ว่า สี่เหลี่ยมผืนผ้าที่โดนจำกัดขนาดของเส้นรอบรูปเอาไว้ให้เท่ากับค่าหนึ่ง มันจะมีพื้นที่มากที่สุดก็ต่อเมื่อด้านกว้างและด้านยาวมีขนาดเท่ากัน ซึ่งก็คือมันจะกลายเป็นสี่เหลี่ยมจัตุรัสนั่นเอง

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

ดูโค้ดเลยดีกว่า

from math import isclose
from operator import mul
from functools import reduce

def next_target(cores, index):
    try:
        return cores[index+1]
    except IndexError:
        return 1.0

def train(power, cores):
    index = 0
    cores.sort()
    while not isclose(power, 0.0):
        target = next_target(cores, index)
        margin = target - cores[index]
        index += 1
        training_power = margin * index
        if training_power <= power:
            cores[:index] = [target] * index
            power -= training_power
        else:
            cores[:index] = [core + power/index for core in cores[:index]]
            power = 0
        if all(isclose(core, 1.0) for core in cores):
            break
    return reduce(mul, cores)

def main():
    for case in range(int(input())):
        _ = [int(n) for n in input().split()]
        power = float(input())
        cores = [float(n) for n in input().split()]
        answer = train(power, cores)
        print('Case #{}: {}'.format(case+1, answer))

if __name__ == '__main__':
    main()

จะว่าไปแล้วข้อนี้มันก็ออกจะปรัชญาชีวิตหน่อยๆ เนอะ ถ้าอยากให้ทีมประสบความสำเร็จสูงสุด ก็ควรฝึกปรือจนสมาชิกแต่ละคนในทีมมีความสามารถทัดเทียมกัน ไม่ใช่ว่าทุ่มเทการฝึกสอนไปที่คนเดียวจนเป็นเลิศ แต่กลับละเลยสมาชิกคนอื่นๆ ที่เหลือ

ส่วนข้อสองรอบ 1C ดันมาเห็นเอาทีหลังว่าแบบเล็กมันเล็กมากๆ จน brute force ออก แต่เหลือเวลา 10 นาที เขียนไม่ทัน (แต่ถึงเขียนทันก็ไม่เข้ารอบอยู่ดี คะแนนไม่พอ … ทั้งๆ ที่ดูเผินๆ น่าจะพอ)

ก็เอาเป็นว่าปีนี้ชวดเข้ารอบ 2 อีกเช่นเคย เหมือนว่า Code Jam มันชักจะยากขึ้นทุกปี ต่อไปคงต้องหวังเก็บคะแนนเต็มจากข้อง่ายสุดและยากสุดละมั้ง? ไม่ใช่เก็บคะแนนเต็มข้อง่ายแล้วข้อที่เหลือทำได้แค่คำถามเล็กแล้วหละ TwT

neizod

author