ปีนี้ประมาทไปเยอะครับ คือตอนแรกตั้งใจว่าจะถ่างตามาเริ่มเล่นตั้งแต่ปล่อยโจทย์ตอน 6 โมงเช้าเลย แต่สุดท้ายก็เผลอหลับไปตอนตี 4 ตื่นมารู้ตัวอีกทีก็บ่ายแล้ว เลยพักสมองออกเล่นบอร์ดเกมกะ @tamwb และ @aibig ตามนัดปาร์ตี้สงกรานต์ แถมกลับมาก็ยังไม่มีสมาธิแก้โจทย์มัวแต่ดู MV เกาหลีอีก กว่าได้เริ่มทำแข่งจริงจังก็เหลือเวลาไม่กี่ชั่วโมงแล้ว
ตอนอ่านโจทย์ผ่านๆ ทุกข้อนี่คิดว่าง่าย ปีนี้ได้แก้มือเก็บคะแนนเต็มแน่ๆ ... ที่ไหนได้ bug ซ่อนเร้น 1 ข้อ แล้วก็ตีความโจทย์อีก 1 ข้อ สุดท้ายแก้ไม่ทัน ได้ส่งแค่ 2 ข้อ ดีแค่ไหนแล้วที่ยังไม่ตกรอบ 555
ข้อแรกง่ายฮะ แต่ถ้ายังอ่านโจทย์แล้วไม่อินขอให้ดูคลิปนี้ตอนนาทีที่ 7:05 และ 7:23 (เรียบร้อยแล้วก็กลับไปดูตั้งแต่ต้นด้วยจะดีมาก) :P
ส่วน code ก็ประมาณ
import Text.Printf (printf)
import Data.List.Split (splitOn)
invites audience =
let aux [] _ _ inv = inv
aux (p:ps) shy acc inv = aux ps (shy+1) (acc+p+more) (inv+more)
where more = max 0 (shy-acc)
in aux audience 0 0 0
test t = do
it <- getLine
let [_, ps] = splitOn " " it
printf "Case #%d: %d\n" t $ invites [read [p] :: Integer | p <- ps]
main = do
loop <- getLine
sequence_ [test t | t <- [1..read loop :: Integer]]
(อย่างไรก็ตาม เท่าที่เคยไปคอนเสิร์ตหลายครั้ง รู้สึกว่าคนไทยจะมีค่าความอายเป็น infinity นะ)ข้อสองข้ามไปนะฮะ ทำไม่ได้ (ข้อสี่ด้วย)
ส่วนข้อสามนี่สนุกดี ถ้ายังจำเนื้อหาม.ปลายได้ เราจะมีเลขมหัศจรรย์ตัวนึงเรียกว่า
i ซึ่งมีนิยามที่สวยงามเรียบง่าย คือi^2 = -1สังเกตเพิ่มอีกหน่อยก็จะเห็นว่า
i^4 = 1 (multiplicative identity)โจทย์เพิ่มความสนุกโดยให้ตัวเลขมหัศจรรย์
j และ k มาด้วย ทั้งสองตัวที่เพิ่มเข้ามานี้ มีนิยามแบบเดียวกันกะ i เด๊ะๆ เลย เพียงแต่มันไม่ใช่ i เพราะเรานิยามการคูณระหว่างตัวเลขเหล่านี้ว่าij = k jk = i ki = jความซับซ้อนของตัวเลขชุดนี้ยังเพิ่มขึ้นไปอีก เมื่อเรานิยามให้มันไม่มีสมบัติสลับที่ด้วย ซึ่งในที่นี้คือ
ji = -k kj = -i ik = -jเพื่อความสะดวก สมมติชื่อให้เลขชุดนี้ว่า
ℍu ละกันครับ โชคดีที่อย่างน้อยในเซ็ต ℍu = {1, i, j, k} มันยังมี- สมบัติปิดบนการคูณ คือ ถ้าใช้การคูณอย่างเดียวบนสมาชิกของเซ็ต
ℍuผลลัพธ์ที่ได้ก็จะเป็นสมาชิกของเซ็ตℍuด้วย - สมบัติจัดกลุ่มการคูณ คือ
a(bc) = (ab)cสำหรับทุกa, b, c ∈ ℍu
จาก
X, LS ที่โจทย์ให้ การแก้ปัญหาแบบตรงๆ ก็คือวิ่งผ่านชุดตัวเลข LS เป็นจำนวน X ครั้ง โดยเลขแต่ละตัวเลข s ∈ LS ที่วิ่งผ่าน ก็จัดการคูณเก็บไว้ในใจไปเรื่อยๆ ถ้าเจอตัวเลขครบทั้ง i, j, k และหางที่เหลือคูณกันออกมาเป็น 1 ก็ตอบว่าถูกได้เลยถ้าอ่านมาจนถึงตรงนี้แล้วยังงงไม่หาย ลองดูการทำงานตามขั้นตอนวิธีด้วยตัวอย่างนี้
X = 10 LS = ji sequence: ji ji ji ji ji ji ji ji ji ji running: --->--->-------->-----------> found: i j k 1โจทย์ข้อนี้ฉลาดตรงที่เอาตัวเลข
Xขนาดใหญ่มากๆ มาขู่ ทั้งที่เราสามารถ modulo มันทิ้งให้เหลือแค่หลักสิบได้ (ซึ่งก็คือ คำถามชุดใหญ่จะมีความยากแทบไม่ต่างกับคำถามชุดเล็กเลย)การลดขนาด
X ทำได้โดยใช้ข้อสังเกตที่ว่า i^4 = j^4 = k^4 = 1 ซึ่งบอกเป็นนัยอยู่ 2 อย่างคือ- ถ้าวิ่งคูณหา
i, j, kแต่ละตัวเกิน 4 รอบแล้วยังไม่เจอ ไม่ต้องวิ่งต่อ เพราะแต่ละรอบที่วิ่งเพิ่ม จะไม่ได้ผลลัพธ์ใหม่แล้ว - หลังจากหา
i, j, kได้ครบแล้ว หางที่เหลือสามารถ mod 4 ได้
i, j, k) โดยแต่ละครั้งวิ่งไม่เกิน 4 รอบ ซึ่งก็เท่ากับวิ่ง 12 รอบ แล้วรอบที่เหลือก็จับ mod 4 ได้เลยหรือพูดจาภาษา code ก็คือ
def correct_misspelling(ijks, x):
x = min(x, 12+(x%4))
accumulate = Quaternion('+1')
searching = [Quaternion(it) for it in 'kji']
for _ in range(x):
for it in ijks:
accumulate *= Quaternion(it)
if searching and searching[-1] == accumulate:
accumulate = Quaternion('+1')
searching.pop()
return not searching and accumulate == Quaternion('+1')
for case in range(int(input())):
_, x = [int(n) for n in input().split()]
ijks = input().strip()
ans = 'YES' if correct_misspelling(ijks, x) else 'NO'
print('Case #{}: {}'.format(case+1, ans))
ข้อนี้ถ้าจะ optimize เพิ่มก็ยังทำได้อีก (code จริงที่เอาไปส่งก็เขียนสวยน้อยกว่านี้เพราะมัวแต่ optimize มากเกินไป) โดยเรามีข้อสังเกตดังนี้aba = bสำหรับทุกa, b ∈ ℍu- เราสามารถทดเก็บค่าสุดท้ายที่ได้จากการวิ่งผ่านเพื่อหาผลคูณของทุกตัวใน
LSไว้ได้ แล้วพอจะวิ่งผ่านLSอีกรอบก็ใช้ค่าที่ทดไว้ได้เลย - ในการทดลองจริง จำนวน
Xที่จำเป็นต่อการคำนวณไม่เคยมีค่าเกิน 8 เลย ซึ่งก็คือx = min(x, 4+(x%4))
