neizod's speculation

insufficient data for meaningful answer

TechJam 2018

Wednesday, October 10, 2018, 08:34 AM

ช่วงนี้เบื่อๆ เลยหาจังหวะเขียนโค้ดเล่น ก็บังเอิญกับที่ @taneekpet ส่งข่าวมาบอกว่า KBTG กำลังจัดแข่ง TechJam พอดี เลยมองซ้ายมองขวาคว้ามือ @ipats มาสมัครแข่งขันอย่างไม่คาดหวังอะไร 555

ก็บังเอิญว่าผ่านเข้ารอบภาคกลาง เลยมานั่งจดวิธีคิดและคำตอบไว้ซักหน่อย เห็นว่าโจทย์มีความท้าทายดี (ขอชมทีมออกโจทย์มา ณ ที่นี้ด้วย) แต่เฉลยได้ไม่ครบทุกข้อนะเพราะจำ+ทำได้ไม่หมด … พร้อมหมายเหตุตัวโตๆ ว่าโค้ดที่แปะนี่คือทำความสะอาดมาเรียบร้อยแล้ว ตอนแข่งจริงโค้ดไม่ได้สวยงามขนาดนี้ 😅

รอบคัดเลือก

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

ข้อเล็กๆ ถามสั้นตอบไว

ในกติกาให้คำแนะนำมาว่า ข้อเล็กๆ พวกนี้ควรเห็นโจทย์ปุ๊ปก็ตอบได้เลย ไม่ควรใช้เวลาเกินหนึ่งนาที ก็สงสัยว่าจะร้างราจากการแก้โจทย์แนวนี้มานาน ซัดไปข้อละห้าถึงสิบนาทีได้มั้ง … เอาจริงๆ จะให้ตอบหลักวินาทีเลยก็คงได้ แต่ความมั่นใจว่าจะถูกนี่ลดลงเหลือแค่ $1-\delta$ นะ 😝

สุ่มจากเหรียญลำเอียงให้ไม่ลำเอียง

โจทย์ให้เหรียญมาเหรียญหนึ่งซึ่งลำเอียงไปออกก้อย 51% และอยากได้วิธีที่จะเลียนแบบเหรียญที่ไม่ลำเอียง จึงขอให้เรียงความน่าจะเป็นที่วิธีทั้ง 4 นี้จะให้คำตอบลำเอียงน้อยสุดไปหามากสุด

  1. โยนเหรียญไปร้อยครั้ง ถ้านับว่าออกหัวน้อยกว่า 49 ครั้งก็ตอบหัว มากกว่า 49 ครั้งก็ตอบก้อย
  2. โยนเหรียญไปเรื่อยๆ จนกว่าจะออกก้อย หลังจากนั้นโยนเหรียญอีกหนึ่งครั้งแล้วตอบตามหน้าที่ออก
  3. โยนเหรียญสองครั้ง ถ้าออกหัวทั้งคู่ก็ตอบหัว ออกก้อยทั้งคู่ก็ตอบก้อย
  4. โยนเหรียญสองครั้ง ถ้าออกหัวแล้วก้อยให้ตอบหัว ถ้าออกก้อยแล้วหัวให้ตอบก้อย

ทั้งสี่วิธีข้างต้น ถ้าทำตามแล้วยังหาคำตอบไม่ได้ ก็ให้วนทำซ้ำไปเรื่อยๆ จนกว่าจะพบคำตอบ

ซึ่งถ้ามาวิเคราะห์ดู จะพบว่า

  1. คิดจากผลรวมของการแจกแจงทวินาม $\Pr[X=r] = {100 \choose r}(0.49)^r(0.51)^{100-r}$ โดยโอกาสออกหัวคือ $\Pr[0 \le X \le 48] \approx 0.4605 $ และโอกาสออกก้อยคือ $\Pr[50 \le X \le 100] \approx 0.4599$ พอเอามาคิดเป็นอัตราส่วนแล้วได้ประมาณ 50.03 ต่อ 49.97
  2. การสุ่มแต่ละครั้งเป็นอิสระต่อกัน แม้จะสุ่มมาเรื่อยๆ จนออกก้อยแล้ว ก็ไม่ได้รับประกันว่าครั้งต่อไปจะออกหัวเพิ่มขึ้นแต่อย่างใด ดังนั้นอัตราส่วนจึงเป็น 49 ต่อ 51 เท่าเดิม
  3. หัวทั้งคู่แล้วตอบหัวคือ $(0.49)^2 \approx 0.24$ ก้อยทั้งคู่แล้วตอบก้อยคือ $(0.51)^2 \approx 0.26$ ดังนั้นอัตราส่วนจะกลายเป็นประมาณ 48 ต่อ 52
  4. เนื่องจากโอกาสออกหัวแล้วก้อยกับก้อยแล้วหัวมีค่าเท่ากัน และโอกาสที่หัวจะไปออกครั้งแรกหรือครั้งหลังก็เท่ากัน ดังนั้นวิธีนี้จึงแฟร์ที่สุด ให้อัตราส่วนเป็น 50 ต่อ 50 พอดีเป๊ะเลย

ดังนั้นข้อนี้ตอบ 4, 1, 2, 3

สร้างรูปจากสี่เหลี่ยม

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

ตัวอย่างการสร้างรูปที่ถูกกฏ (สีน้ำเงิน) และผิด (สีแดง)

ข้อนี้ @ipats สังเกตอย่างรวดเร็วได้ว่า วิธีการที่จะเติมรูปสี่เหลี่ยมจัตุรัสลงไปเพื่อสร้างรูปทรงใหม่ สามารถตัดทอนรายละเอียดลงมาได้เหลือเพียง 2 วิธีเท่านั้น คือ

การต่อเติมรูปโดยไม่ขัดกฏ วิธีสีเขียวทางซ้ายจะเพิ่มครั้งละ 4 ส่วนวิธีสีน้ำเงินทางขวาเพิ่มครั้งละ 3

จึงได้สูตรของพื้นที่ที่เป็นไปว่า $5+4s_G+3s_B$ เมื่อ $s_G, s_B$ เป็นจำนวนครั้งที่ทำวิธีสีเขียวและน้ำเงินตามลำดับ หรือวาดออกมาเป็นแผนภาพได้ว่า

แผนภาพความเป็นไปได้ของพื้นที่ที่สร้างได้

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

เราจึงเหลือแค่กรณีแรกๆ ให้พิจารณา ซึ่งไล่ดูด้วยตาก็ตอบได้ว่า พื้นที่ที่ใหญ่สุดที่สร้างไม่ได้คือ 10 หน่วย

เรียงเรียงเรียง

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

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

สมมติว่าอาเรย์ยาว 8 ตัวแล้วเราเลือกเรียง 6 ตัวแรก ตามด้วยเรียง 6 ตัวหลัง แล้วกลับไปเรียง 6 ตัวแรกอีกที จะได้ผลลัพธ์หลังการเรียงแต่ละครั้ง ดังนี้

0: 7 6 5 4 3 2 1 0
1: 2 3 4 5 6 7 1 0
2: 2 3 0 1 4 5 6 7
3: 0 1 2 3 4 5 6 7

นั่นก็คือ แม้การเรียงครั้งแรกจะไม่รับประกันเลยว่ามีสมาชิกตัวไหนในอาเรย์ที่อยู่ถูกตำแหน่ง แต่ถ้าดูส่วนที่ซ้อนทับกันระหว่างการเรียงครั้งแรกกับครั้งที่สองแล้ว จะพบว่าสมาชิก 4 ตัวตรงกลางก่อนการเรียงครั้งที่สองจะไปอยู่ตำแหน่งที่ถูกต้องแน่นอนหลังการเรียงครั้งที่สอง และเมื่อเรียงครั้งที่สามก็จะได้อาเรย์ที่เรียงลำดับเรียบร้อยทั้งอาเรย์พอดี

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

นับกิ่งก้านใบ

โจทย์ให้โครงสร้างข้อมูลต้นไม้ทวิภาคที่สมบูรณ์มา ซึ่งหมายความว่าสำหรับโหนดใดๆ ถ้าโหนดนั้นไม่ใช่ใบ (มีลูกเท่ากับ 0) ก็ต้องเป็นกิ่งที่มีลูกทั้งซ้ายและขวาเท่านั้น (มีลูกเท่ากับ 2) ถามว่าจะนับจำนวนโหนดทั้งหมดในต้นไม้ด้วยฟังก์ชันนิรนามได้อย่างไร?

from collections import namedtuple

Node = namedtuple('Node', 'value left right')
Node.__new__.__defaults__ = (None, None, None)

def compute(tree, f, g):
    if tree.left is None and tree.right is None:
        return f(tree)
    else:
        return g(compute(tree.left, f, g), compute(tree.right, f, g), tree.value)

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

compute(tree, lambda _: 1, lambda lt, rt, _: lt + rt + 1)

แต่เนื่องจากเป็นโจทย์ชอยส์ (ที่จะบอกว่ากวนตีนก็ได้ 555) เลยไม่มีคำตอบนี้ให้เลือก! ติดสตันท์กันไปแป๊ปนึง @ipats ก็เตือนความจำว่า ต้นไม้มันเป็นแบบสมบูรณ์ ดังนั้นแม้จะรู้แค่จำนวนใบ ก็สามารถย้อนกลับไปคำนวณโหนดได้ ซึ่งมีสูตรคือ $|V| = 2|T| - 1$ เมื่อ $V, T$ คือโหนดและใบของต้นไม้ตามลำดับ

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

ดังนั้นข้อนี้จึงตอบ

compute(tree, lambda _: 1, lambda lt, rt, _: lt + rt) * 2 - 1

เลขสวยงาม

เลขสวยงามคือเลขที่เมื่อเขียนด้วยสตริงในฐาน 10 และแบ่งพาร์ทิชันแล้ว มีบางพาร์ทิชันที่ทุกซับสตริงเป็นจำนวนเฉพาะที่ไม่ขึ้นต้นด้วยเลขศูนย์ เช่น

  • 863 เป็นเลขสวยงาม เพราะ 863 เป็นจำนวนเฉพาะ
  • 357 เป็นเลขสวยงาม แม้ว่า 357 จะไม่เป็นจำนวนเฉพาะ แต่เราสามารถแบ่งพาร์ทิชัน 3|5|7 ที่ทำให้ทุกๆ ซับสตริงเป็นจำนวนเฉพาะได้
  • 202 ไม่เป็นเลขสวยงาม แม้ 2 จะเป็นจำนวนเฉพาะ แต่การแบ่งพาร์ทิชัน 2|02 นั้นผิดกฎที่ห้ามมีเลขศูนย์นำหน้า (และการแบ่งพาร์ทิชันแบบอื่นๆ เช่น 20|2 ก็มีบางเลขที่ไม่ใช่จำนวนเฉพาะ)

คำถามคือ สำหรับตัวเลขทุกตัวที่เขียนได้ด้วยสตริงขนาด 5 ตัวอักษร มีเลขสวยงามทั้งหมดเท่าไหร่?

จำได้ว่าเคยเขียนอะไรแบบนี้ใน Project Euler มาแล้ว (หรืออาจจะไม่เคย แต่โจทย์คุ้นมาก) ก็เลยได้โค้ดนี้ออกมาอย่างรวดเร็ว

from collections import deque
from mathapi import prime       # github.com/neizod/mathapi

def partition(s):
    if s.startswith('0'):
        return
    if not s:
        yield deque()
    for i in range(1, len(s)+1):
        head = deque([s[:i]])
        for rest in partition(s[i:]):
            yield head + rest

def is_beautiful(n):
    for par in partition(str(n)):
        if all(int(s) in prime for s in par):
            return True
    return False

print(sum(is_beautiful(n) for n in range(10000, 100000)))

รันไป 5 วินาทีก็ได้คำตอบว่ามีเลขสวยงามอยู่ทั้งหมด 24,920 ตัว

ข้อใหญ่ๆ แก้โจทย์สนใจ Big-O

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

ช่วยกันเก็บแอปเปิล

โจทย์ให้สวนแอปเปิล $A$ ที่มีแผนผังเป็นอาเรย์หนึ่งมิติมา โดยมีคนงาน 2 คนคือ Alice และ Bob ที่เก็บแอปเปิลจากต้นไม้ที่ติดกันได้ $K$ และ $L$ ต้นตามลำดับ ถ้าไม่ให้ Alice และ Bob เก็บแอปเปิลจากต้นซ้ำกัน ทั้งคู่จะเก็บแอปเปิลได้รวมกันมากที่สุดเท่าไหร่?

ข้อนี้ @ipats ตอบมาด้วยความรวดเร็วว่าแค่ sliding window ไปก็เสร็จแล้ว แต่คิดเทสเคสไปมาแล้วเจอบั๊ก เลยข้ามไปทำข้ออื่นก่อน (เพิ่งรู้ว่ามันข้ามไปทำข้ออื่นได้) แล้วกลับมาดีบั๊กต่อจนเสร็จครับ

โดยวิธีคิดเริ่มจากให้ Alice เป็นคนเริ่มเลือกเก็บแอปเปิลจากต้นไม้ $K$ ต้นติดกันเป็นคนแรก หาก Alice โลภ (greedy) และเลือกเก็บจาก $K$ ต้นที่ให้แอปเปิลสูงสุด อาจส่งผลเสียให้ Bob เหลือแอปเปิลบนต้นไม้ที่ติดกัน $L$ ต้นให้เก็บน้อยก็ได้ (ตัวอย่าง: $K=L=2$ และ $A=[1,2,23,42,3,1]$)

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

ซึ่งเราจะมองว่า หลังจาก Alice เลือกช่วงต้นไม้ที่จะเก็บแอปเปิลไปแล้ว สวนจะถูกแบ่งออกเป็น 2 ฝาก ซึ่ง Bob จะเข้าไปเก็บแอปเปิลในสวนใดสวนหนึ่งที่ให้ผลลัพธ์สูงสุด หากเราสามารถหาว่า Bob ต้องเก็บแอปเปิลที่ต้นไหน เราก็จะสามารถแก้โจทย์ข้อนี้ได้

การจะทำเช่นนั้นได้ เราเริ่มให้ Bob ทดไว้ว่าถ้าเลือกแอปเปิลจากต้นที่ $1$ ถึง $L$ จะได้แอปเปิลได้จำนวนเท่าไหร่ และ Alice ทดไว้ว่าถ้าเลือกเก็บแอปเปิลจากต้น $L+1$ ถึง $L+K$ ได้เท่าไหร่ … ตรงนี้เราจะเห็นว่า Bob เลือกเก็บแอปเปิลที่เป็นไปได้มากที่สุดแล้วในสวนฝั่งซ้ายมือ ดังนั้นผลรวมแอปเปิลที่มากที่สุด เมื่อ Alice เลือกเก็บที่ตำแหน่งนี้คือ การเลือกเก็บตั้งแต่ต้น $1$ ถึง $L+K$

  maxL
|------|
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 ...
|------| |---------|
    L         K

ในรอบถัดมา ให้ Alice เลื่อนไปเริ่มเก็บแอปเปิลที่ต้นถัดไป (ต้นที่ $L+2$ ถึง $L+K+1$) และให้ Bob เลื่อนไปเริ่มเก็บที่ต้นถัดไป (ต้นที่ $2$ ถึง $L+1$) เช่นกัน คราวนี้เราจะเปรียบเทียบว่า Bob เก็บของใหม่ได้ดีกว่าของเดิมหรือไม่ หากเก็บได้มากกว่าก็จะอัพเดทค่าสูงสุดของ Bob ที่เก็บได้ในสวนฝั่งซ้ายมือ แล้วหาค่าผลรวมแอปเปิลจากตำแหน่งปัจจุบันที่ Alice เลือกเก็บและจากค่าสูงสุดของ Bob

     maxL
   |------|
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 ...
   |------| |---------|
       L         K

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

        maxL
      |------|
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 ...
            |------| |-----------|
                L          K

อย่างไรก็ตาม การเก็บแอปเปิลตามวิธีข้างต้นนั้น เราสนใจแต่การให้ Bob เก็บแอปเปิลให้ได้มากที่สุดในสวนฝั่งซ้ายอย่างเดียว เพื่อให้ผลลัพธ์ที่สมบูรณ์ เราต้องวิ่งจากด้านขวาของสวนกลับมาด้านซ้ายด้วย หรือก็คือทำกระบวนการข้างต้นอีกครั้งโดยกลับอาเรย์ $A$ นั่นเอง

เพราะเราวิ่งผ่านอาเรย์แค่ 2 รอบ เวลาที่ใช้จึงเป็น $O(n)$

def aux(A, K, L):
    ck = sum(A[L:K+L])
    cl = sum(A[:L])
    ml = max(0, cl)
    ans = cl + ck
    for i in range(K+L, len(A)):
        ck += A[i] - A[i-K]
        cl += A[i-K] - A[i-K-L]
        ml = max(ml, cl)
        ans = max(ans, ck + ml)
    return ans

def solution(A, K, L):
    if K + L > len(A):
        return -1
    return max(aux(A, K, L), aux(A[::-1], K, L))

อินเดียน่า โจนส์ กับเลเซอร์ตุ๊กตากระจก

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

ข้อนี้ง่ายมาก ใช้แค่ความรู้คณิตศาสตร์พื้นฐานเท่านั้น และถ้ารู้จักโครงสร้างข้อมูลที่เหมาะสมก็ไม่ต้องพึ่งอัลกอริทึมยากๆ เลย

เนื่องจากเรายืนอยู่ที่จุด $(0,0)$ และมองเห็นตุ๊กตาตัวที่ $i$ ที่ตำแหน่ง $(x_i,y_i)$ ถ้าตุ๊กตาตัวที่ $i$ และ $j$ อยู่ในเส้นสายตาเดียวกัน (โดยไม่เสียนัยทั่วไป หมายถึงเราสามารถยิงเลเซอร์ไปยัง $(x_i,y_i)$ และทะลุไปหา $(x_j,y_j)$ ได้) นั่นหมายความว่าตุ๊กตาตัวที่ $i$ และ $j$ อยู่บนเส้นความชันเดียวกัน หรือก็คือสามารถหาค่า $s$ และ $t$ บางค่าที่ทำให้สมการนี้เป็นจริง ซึ่งมีคำตอบคือ $s = 1/\gcd(x_i,y_i)$ และ $t = 1/\gcd(x_j,y_j)$

สำหรับฟังก์ชัน $\gcd$ เป็นฟังก์ชันที่คำนวณหาค่าห.ร.ม.ของตัวเลขจำนวนเต็มสองตัว เมื่อนำไปหาค่า $s,t$ ตามข้างต้น จะทำให้พิกัดของตุ๊กตาที่ได้มีค่าเป็นเศษส่วนอย่างต่ำเสมอ หรือก็คือ ตุ๊กตาสองตัวที่อยู่ในแนวเส้นสายตาเดียวกัน เมื่อหารด้วยห.ร.ม.แล้ว จะมีพิกัดเดียวกัน

เราสามารถนับเฉพาะตุ๊กตาที่แปลงพิกัดเป็นเศษส่วนขั้นต่ำแล้วเพื่อบอกว่าต้องยิงเลเซอร์กี่ลำแสงได้เลย

แต่เพราะ $\gcd$ สามารถคืนค่าได้ทั้งบวกและลบ ทำให้การแปลงเศษส่วนขั้นต่ำด้วยการหารค่า $\gcd$ ตรงๆ ของ $(x_i,y_i)$ และ $(-x_i,-y_i)$ คืนค่าเป็นพิกัดเดียวกัน แต่โจทย์ข้อนี้บังคับให้ใช้เลเซอร์สองเส้นเพื่อยิงในทิศทางตรงข้ามกัน ดังนั้นจึงต้องเปลี่ยนไปหารด้วยค่าสัมบูรณ์ของ $\gcd$ แทน เพื่อไม่ให้เสียข้อมูลพิกัดควอแดรนท์ตั้งต้นของตุ๊กตาแต่ละตัว

เนื่องจากการหา $\gcd(x,y)$ แต่ละครั้งกินเวลา $O(\log xy)$ เวลารวมทั้งหมดจึงเป็น $O(n \log xy)$

from fractions import gcd

def irreducible(point):
    denom = abs(gcd(point.x, point.y))
    return (point.x//denom, point.y//denom)

def solution(A):
    return len({irreducible(point) for point in A})

ช่วงที่ขนาดใหญ่สุดที่ได้ผลรวมตามที่ต้องการ

โจทย์ให้อาเรย์ $A$ ที่มีแต่ตัวเลข $\{-1, 0, 1\}$ และผลรวม $S$ ที่ต้องการมา แล้วถามว่าซับอาเรย์ที่มีผลรวมเป็นค่าที่ต้องการมีขนาดใหญ่ที่สุดเป็นเท่าไหร่?

คิดในเวลาไม่ออก เลยเขียนแบบถึกส่งแบบ $O(n^2)$ ไป จนได้ฟังเฉลยจากการพูดคุยกับทีมอื่นๆ ที่ผ่านเข้ารอบชิงภาคกลาง ซึ่งแก้ปัญหาดังกล่าวด้วยกำหนดการพลวัต ด้วยแนวคิดดังนี้

สร้างตารางจดค่า prefix และ postfix ของผลรวมตั้งแต่ช่องแรกไปจนถึงตำแหน่งใดๆ ในอาเรย์ หลังจากนั้นดูว่าแต่ละค่า $C$ ที่สร้างได้ในตาราง postfix เมื่อนำไปลบกับค่า $S$ ที่ต้องการแล้วมีอยู่ในตาราง prefix หรือไม่ ถ้ามีก็แปลว่าเราสามารถสร้างผลรวม $S$ นั้นได้ โดยมีความยาวมากสุดจากตำแหน่งของ $C$ ใน postfix ลบกับตำแหน่งของ $C-S$ ใน prefix นั่นเอง

def make_prefix(A):
    count = 0
    table = {}
    for idx, val in enumerate(A):
        count += val
        if count not in table:
            table[count] = idx
    return table

def make_postfix(A):
    count = 0
    table = {}
    for idx, val in enumerate(A):
        count += val
        table[count] = idx
    return table

def solution(A, S):
    prefix = make_prefix(A)
    postfix = make_postfix(A)
    print(max({postfix[C]-prefix[C-S] for C in postfix if C-S in prefix}))

เปลี่ยนอัลกอริทึมแล้วความเร็วเพิ่มเป็น $O(n)$ กราบๆๆ

รอบชิงภาคกลาง

เนื่องจาก TechJam ไม่ได้เปิดเผยรายชื่อผู้เข้ารอบเป็นข้อมูลสาธารณะ พอถึงหน้างานเลยเพิ่งรู้ว่านี่มันงานรวมญาติสสวท.คอมพิวเตอร์โอลิมปิกนี่หน่า! รู้สึกว่ามาผิดงานซะเหลือเกิน 5555 มองไปทางไหนก็เจอแต่คนใส่เสื้อ Google Code Jam เต็มไปหมด (ส่วนเรานี่สาย Open Source เลยใส่เสื้อ Hacktoberfest ไป) เดินไปเดินมาซักพักก็เจอ @haxxpop กับ @dtinth เลยนั่งคุยสัพเพเหระกันระหว่างรอแข่ง

กติการการแข่งขัน TechJam รอบนี้มีโครงสร้างเหมือนรอบคัดเลือกเลย คือ แบ่งคำถามออกเป็นข้อเล็กและใหญ่ บางช่วงมีลักษณะออกแนววาไรตี้เกมโชว์ที่ต้องชิงกันตอบ ไม่ได้กะให้นั่งซีเรียสยาวๆ หลายชั่วโมงเพื่อเขียนอัลกอริทึมโหดๆ แก้ปัญหาเหมือนพวก ACM-ICPC, Google Code Jam เพียงอย่างเดียว ก็ถือว่าหลากหลายแปลกใหม่สร้างสรรค์ดี เป็นอีกทางเลือกที่ดูตื่นเต้นสนุกสนานไม่แพ้การแข่งกินเบียร์ระหว่างโค้ดที่เคยไปร่วมเมื่อหลายปีก่อนเลย 🍻

ข้อเล็กๆ ถามสั้นตอบไว

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

ลึกและกว้าง

โจทย์ให้พรีออเดอร์ (NLR) จากการทำ DFS บนต้นไม้ค้นหาแบบทวิภาคมา แล้วถามว่าการท่องต้นไม้แบบ BFS สามารถทำได้แตกต่างกันทั้งหมดกี่แบบ

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

ตัวอย่างต้นไม้ค้นหาแบบทวิภาค ที่มีโหนดที่มีลูกสองตัวอยู่ 4 โหนด

ผมนับรอบแรกแล้วผิด จนได้ @ipats มาสะกิดวินาทีสุดท้ายว่ามันต้องคูณ 2 เข้าไปทุกโหนดที่มีลูกสองตัวนะ ไม่ใช่แค่ที่โหนดที่มีสองใบ ดังนั้นตอบ 16 แบบ

นับพื้นที่สามเหลี่ยม

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

มาวาดรูปทีหลังแล้วลืมใส่จุด … จินตนาการเอาว่าที่ทุกๆ มุมสามเหลี่ยมเล็กมันมีจุดอยู่ละกันนะ 😅

ให้ทดลองลากเส้นแล้วยืนนับคงตอบไม่ทันใน 30 วินาที … กรรมการเฉลยว่าข้อนี้ต้องมองให้ออกว่าพื้นที่ที่มากที่สุดสร้างได้ สามารถคำนวณได้จากจำนวนจุดลบด้วย 2 (พอมองออกแล้วพิสูจน์อุปนัยจะง่ายมาก)

วิธีนับจุดเร็วๆ ก็ขอไอเดียได้จากเกาส์ ซึ่งจะได้ว่าจุดทั้งหมดมี $T_{10}+3T_3 = 73$ จุด ดังนั้นจึงได้พื้นที่เป็น 71 สามเหลี่ยมเล็ก

ครอบครัวนักคำนวณ

ให้ครอบครัวนักคำนวณซึ่งประกอบไปด้วย Hilbert, Shannon, Dijkstra, Lovelace, Neumann และมีความสัมพันธ์ดังนี้

  1. Hilbert อายุน้อยกว่า Shannon
  2. Dijkstra อายุน้อยกว่า Lovelace
  3. Shannon อายุน้อยกว่า Neumann
  4. Hilbert อายุน้อยกว่า Dijkstra
  5. Lovelace อายุน้อยกว่า Shannon
  6. Shannon อายุน้อยกว่า Dijkstra
  7. Neumann อายุน้อยกว่า Lovelace

ถามว่าในความสัมพันธ์นี้มีข้อใด (เพียงข้อเดียว) ที่ผิด? และเมื่อลบความสัมพันธ์ที่ผิดนั้นออกแล้ว ใครจะมีอายุมากที่สุด?

ข้อนี้ @ipats ตอบได้อย่างรวดเร็ว เพียงแค่เอาความสัมพันธ์ข้างต้นมาเขียนเป็นกราฟแล้วจะเห็นว่ามีความสัมพันธ์ L<S ที่ทำให้กราฟมีวงจร พอตัดเส้นนี้ทิ้งเพียงเส้นเดียวแล้วกราฟก็จะกลายเป็นต้นไม้ทันที และได้ว่าครอบครัวนี้มี Lovelace เป็นพี่ใหญ่

จัดกลุ่มตัวเลขที่ผลคูณต่างกันน้อยสุด

โจทย์ให้เซ็ต $A=\{1,2,3,\dots,12\}$ มา ถามว่าการแบ่งพาร์ทิชันเซ็ตนี้เป็นสองเซตย่อย แล้วผลต่างของผลคูณของแต่ละเซ็ตย่อยที่มีค่าน้อยสุดเป็นเท่าไหร่?

ขอบคุณ Python ที่มี itertools.combinations เลยเขียนข้อนี้ทันอย่างฉิวเฉียด

from itertools import combinations
from functools import reduce
from operator import mul

prod = lambda ls: reduce(mul, ls)

ls = set(range(1, 13))
ans = set()
for i in range(1, 12):
    for rs in combinations(ls, i):
        rs = set(rs)
        ans |= {abs(prod(rs) - prod(ls-rs))}
print(min(ans))

รันโปรแกรมแล้วตอบว่าผลต่างที่น้อยที่สุดคือ 576

ยกกำลังด้วยการคูณน้อยที่สุด

โจทย์ถามว่า $x^{125}$ สามารถเขียนด้วยผลคูณที่สร้างจากการคูณกันของพจน์ที่อยู่ในฟอร์ม $x^k$ ที่แตกต่างกันอย่างน้อยที่สุดกี่พจน์?

ข้อนี้จะเขียนโปรแกรมคิดแบบการยกกำลังด้วยกำลังสองก็ได้ … ซึ่งจะผิด ส่วน @ipats ทำด้วยมือด้วยการสร้าง $x^2, x^4, x^8,\dots$ ไปเรื่อยๆ จนได้คำตอบว่า 11 … ซึ่งก็ผิดอีกเช่นกัน เพราะจริงๆ แล้วข้อนี้จะออกแนวปัญหาเชาวน์ที่ต้องมองให้ออกว่าการสร้างเลขที่เป็น $x^{5k}$ สามารถใช้พจน์อย่างประหยัดที่สุดคือ $x^{2k} \cdot x^{2k} \cdot x^k$ ดังนั้นคำตอบจะกลายเป็น

คือทำได้ใน 9 ครั้ง (โดนโจทย์ดักจนตอบผิดกันหมดทุกทีม 555)

นับรูปแบบพิซซ่า

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

ข้อนี้ตอนทำจริงเขียนไม่ทันเพราะอ่อนซ้อมจนลืมไปว่ามี itertools.product ให้ใช้ (ไม่ได้ใช้บ่อยเท่าตัว combinations) เลยมัวแต่บั๊กที่เขียนฟังก์ชันนี้เอง … พอแข่งเสร็จกลับมาตั้งสติแล้วเขียนดีๆ ก็เหลือแค่นี้

from itertools import product as cartesian_product

rotate = lambda pizza, i: pizza[i:] + pizza[:i]
minimum = lambda pizza: min(sorted(rotate(pizza, i) for i in range(8)))

print(len({minimum(pizza) for pizza in cartesian_product('012', repeat=8)}))

รันโปรแกรมแล้วตอบ 834 แบบ

ข้อใหญ่ๆ แก้โจทย์สนใจ Big-O

โจทย์ทำแบบเดียวกับ Google Code Jam คือมีเทสเคสทั้งแบบง่าย (เขียนถึกๆ ไปก็น่าจะออก) และแบบยาก (ต้องใช้อัลกอริทึมที่เหมาะสม) … ซึ่งเละครับ ไม่ได้ซ้อมมา มีโจทย์ 3 ข้อทำได้แค่เทสเคสง่าย 2 ข้อเท่านั้น ก็ขอจดเฉลยแค่แบบง่าย (ที่ทำทันตอนแข่ง) ละกัน ส่วนเฉลยเทสเคสยากนั้นน่าจะมีคนอยากอธิบายอยู่แล้วนะ ไปฟังจากคนที่เก่งกว่าเราตรงๆ เลยดีกว่า 😉

สลับสายโพลิเมอร์

ให้โพลิเมอร์ $K$ ซึ่งเป็นสตริงที่มีความยาว $N$ โดยนับตำแหน่งเริ่มต้นที่เลขศูนย์ และให้ข้อมูลตำแหน่ง $p$ ที่ต้องการทำงานมาอีก $M$ ครั้ง โดยแต่ละครั้งที่ทำงาน จะกลับซับสตริงฝั่งซ้ายของ $K_p$ และกลับซับสตริงฝั่งขวาของ $K_p$ ดังตัวอย่างต่อไปนี้

Input Polymer: ASDFGHJKL
p = 3             ^
Intermediate:  DSAFLKJHG
p = 6                ^
Intermediate:  KLFASDJGH
p = 0          ^
Final Output:  KHGJDSAFL

ให้เขียนโปรแกรมที่ตอบผลลัพธ์ของการทำงานสลับสตริงดังกล่าว โดยเทสเคสง่าย $1 \le N \le 300$ และ $0 \le M \le 30\text{k}$ ส่วนเทสเคสยาก $1 \le N \le 300\text{k}$ และ $0 \le M \le 300\text{k}$

ซึ่งโค้ดที่พอจะผ่านเทสเคสง่ายก็เขียนเพียงเท่านี้

n, m = [int(n) for n in input().split()]
polymer = list(input().strip())
for _ in range(m):
    p = int(input())
    polymer = polymer[:p][::-1] + polymer[p:p+1] + polymer[p+1:][::-1]
print(''.join(polymer))

จะเห็นว่ามันเสียเวลาหนักๆ ตรงที่ต้องสร้างสตริงใหม่ทุกครั้ง … ซึ่งตอนแข่งก็พอจะนึกถึงโครงสร้างข้อมูลที่แก้ปัญหาตรงนี้ได้แล้ว แต่เขียนไม่ทันอยู่ดี 555

ลดค่าผ่านทางหลวง

ให้กราฟมีทิศทางที่แต่ละโหนดแทนเมืองและเส้นเชื่อมแทนทางหลวงที่มีการเก็บค่าผ่านทาง ซึ่งปัจจุบันมีเส้นทางที่ถูกที่สุดที่เป็นทางผ่านจากเมือง $1 \to N$ อยู่แล้ว อยากสร้างเส้นทางถูกที่สุดอีกอย่างน้อยหนึ่งเส้นทาง ซึ่งทำได้โดยลดค่าผ่านทางหลวงได้หนึ่งเส้น โดยการลดค่าผ่านทางนี้ต้องไม่กระทบกับเส้นทางที่ถูกที่สุดที่มีอยู่ และไม่สามารถลดค่าผ่านทางจนติดลบได้ ถามว่าต้องลดค่าผ่านทางอย่างน้อยสุดเป็นเงินเท่าไหร่?

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

ข้อจำกัดของเทสเคสง่ายคือ $3 \le N \le 50$ และ $1 \le M \le 2\text{k}$ ส่วนเทสเคสยากนั้น $3 \le N \le 100\text{k}$ และ $1 \le M \le 200\text{k}$

ข้อนี้ @ipats น่าจะคิดเกือบออกแล้ว เสียดายที่เราไม่ถนัดอัลกอริทึมบนกราฟ แค่จะเขียนโค้ดมาทดลองตามยังทำไม่ได้เลย 😭 (ส่วน @ipats ดันก็ถนัดแต่ PHP ซึ่งการแข่งขันนี้เป็นแบบส่งโค้ดและไม่รองรับ ถถถ)

แข่งเสร็จมาคุยกับทีมอื่นๆ ก็ได้แนวคิดสำหรับแก้โจทย์ว่า เริ่มจากหาเส้นทางที่สั้นที่สุด จาก $1 \to N$ เก็บเป็น prefix แล้วสลับทิศทางของกราฟมาหาเส้นทางที่สั้นที่สุดจาก $N \to 1$ เก็บเป็น postfix หลังจากนั้นพิจารณาทางหลวงที่เชื่อมเมือง $u \to v$ ใดๆ คำนวณค่าผ่านทางจาก $1 \to u \to v \to N$ (ซึ่งทำได้เร็วโดยดูจากค่าใน prefix และ postfix บวกกันได้เลย) แล้วทดลองลดค่าผ่านทาง $u \to v$ ว่าจะสามารถทำให้ค่าผ่านทางรวมเท่ากับค่าผ่านทางที่ถูกที่สุดได้มั้ย ทำไปเรื่อยๆ ให้ครบทุกเส้นทางเพื่อหาการลดค่าผ่านทางที่ถูกที่สุด

หรือนำไอเดียข้างต้นมาเขียนโค้ดคร่าวๆ ก็น่าจะได้ประมาณนี้

from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(graph, root):
    dist = {u: 0 if u == root else 1e400 for u in graph}
    queue = [(dist[root], root)]
    while queue:
        best, u = heappop(queue)
        for v, cost in graph[u].items():
            dist[v] = min(dist[v], best+cost)
            heappush(queue, (dist[v], v))
    return dist

def exceed_shortest(n, graph, prefix, postfix, avoid=set()):
    best = prefix[n]
    exceed = defaultdict(set)
    for u, edges in graph.items():
        for v, cost in edges.items():
            if (u, v) not in avoid:
                value = prefix[u] + postfix[v] + cost - best
                if value < cost:
                    exceed[value] |= {(u, v)}
    return exceed

def solve(n, direct, invert):
    prefix, postfix = dijkstra(direct, 1), dijkstra(invert, n)
    exceed = exceed_shortest(n, direct, prefix, postfix)
    exceed = exceed_shortest(n, direct, prefix, postfix, exceed[0])
    return min(exceed) if exceed else 0

def main():
    n, m = [int(n) for n in input().split()]
    direct = {u: {} for u in range(1, n+1)}
    invert = {v: {} for v in range(1, n+1)}
    for _ in range(m):
        u, v, c = [int(n) for n in input().split()]
        direct[u][v] = invert[v][u] = c
    print(solve(n, direct, invert))

if __name__ == '__main__':
    main()

ขุดสมบัติ

มีลายแทงสมบัติในแนวดิ่งเป็นตารางขนาด $R \times C$ โดยแต่ละช่องอาจมีสมบัติที่มีราคาติดลบได้ เราต้องการขุดสมบัติลึกลงไปเรื่อยๆ ให้ได้มูลค่ารวมมากที่สุด โดยในขณะที่ขุดไปจนถึงความลึกหนึ่งๆ เราอาจเลือกได้ว่าจะเลี้ยวซ้ายหรือขวาหนึ่งครั้งไปไกลสุด $K$ ช่องแล้วขุดลงชั้นถัดไป (หรือจะหยุดขุดก็ได้) แต่เครื่องขุดสมบัติจะขุดถอยหลังหรือขุดย้อนขึ้นด้านบนไม่ได้ ถามว่าเราสามารถขุดหาสมบัติได้มากที่สุดเป็นมูลค่าเท่าไหร่?

ตัวอย่างแผนที่สมบัติ และการขุดที่ให้มูลค่ามากที่สุดที่ 5 หน่วย

เทสเคสง่ายน่าจะให้ $1 \le R, C \le 200$ และเทสเคสยาก $1 \le R \times C \le 2\text{M}$ โดยทั้งสองเคส $K \le C$

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

def sign(n):
    return +1 if n > 0 else -1 if n < 0 else 0

def possible(layer, i, kp, below):
    out = {0}
    acc = 0
    for j in range(0, kp, sign(kp)):
        if not 0 <= i+j < len(layer):
            break
        acc += layer[i+j]
        out |= {acc + below[i+j]}
    return out

def max_cell(layer, i, k, below):
    left = possible(layer, i, -k-1, below)
    right = possible(layer, i, k+1, below)
    return max(left | right)

def solve(grid, r, c, k):
    best = [0 for _ in range(c)]
    while grid:
        layer = grid.pop()
        best = [max_cell(layer, i, k, best) for i in range(c)]
    return max(best)

def main():
    r, c, k = [int(n) for n in input().split()]
    grid = [[int(n) for n in input().split()] for _ in range(r)]
    print(solve(grid, r, c, k))

if __name__ == '__main__':
    main()

แต่ความโหดคือการที่โจทย์ยอมให้หัวเจาะเลี้ยวได้ไกลถึง $K \le C$ นั่นหมายความว่าอัลกอริทึมข้างต้นที่กินเวลา $O(RC^2)$ จะทำงานเทสเคสยากไม่ทันนั่นเอง (ยอม คิดไม่ออกแล้ว)

สรุป

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

สุดท้ายนี้ต้องขอบคุณ @ipats มากๆ ที่สละเวลามาร่วมสนุกกัน แล้วไว้ปีหน้า (ถ้ายังฟิตอยู่) จะมาใหม่นะ 😉