เฉลยโจทย์แข่ง

ICPC 2026 ไทย รอบย่อย: สรุปโจทย์ + เฉลยแบบเข้าใจง่าย

รวมโจทย์ 7 ข้อ (เพียงบางส่วน) จากรอบคัดเลือกย่อย ICPC 2026 Thailand ชุดวันอาทิตย์ที่ 19 ก.ค. ที่ผมนั่งไล่แกะทีละข้อ ตั้งใจเล่าแบบ "เพื่อนเล่าให้ฟัง" ไม่ต้องอ่านโจทย์ต้นฉบับก็ตามได้ แต่ละข้อจะให้ คำใบ้และไอเดียก่อน แล้วเก็บ เฉลยโค้ดไว้ในกล่องพับ (กดเองเมื่อพร้อม) จะได้ลองคิดก่อนแอบดู

หมายเหตุ: เส้นทางแยกเป็น 2 สาย สายในประเทศคือ "รอบย่อย" (sub-regional) กระจายตามภาค งานที่ ม.ช. คือสนามภาคเหนือ ผ่านแล้วไปต่อ "รอบระดับประเทศ" (National Contest) คือ ICPC Thailand National Contest 2026 ที่ ม.เกษตรศาสตร์ (มก.) จัด 5-6 ก.ย. ที่กรุงเทพฯ ส่วนการจะไป World Finals เป็นคนละสาย ต้องไปลุ้นผ่าน "รอบภูมิภาค" (regional) โดยทีมไปสมัครแข่งกับสนามต่างประเทศที่เขาจัดประจำเอง แล้วจึงไปรอบชิงแชมป์เอเชียแปซิฟิก เท่าที่ทราบไทยเว้นการจัด regional ในบ้านมาหลายปีและกำลังค่อย ๆ ฟื้นกลับมา ทีมที่อยากไปจึงต้องไปสมัครแข่งที่สนามต่างประเทศเอง

echo "7 1 2 1 1 3 2 2 4 1 2 5 1 4 6 2 5 7 7" | python solution.py

@"
7
1 2 1
1 3 2
2 4 1
2 5 1
4 6 2
5 7 7
"@ | python solution.py

python solution.py < in.txt

A · Holy Circle Talisman: ไม้หมุนเป็นวง

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

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

* ตัวอย่างสมมติเพื่อประกอบความเข้าใจ

import sys
L = int(sys.stdin.read())
# ปักเข็มกลางไม้ พื้นที่น้อยสุด = (L/2)^2 * pi
# โจทย์ให้ตอบเป็นหน่วยของ pi เลยตอบแค่ k = (L//2)**2
print((L // 2) ** 2)

B · Painting: ปั๊มแสตมป์ทำภาพ

การบ้านวิชาศิลปะ: ทำภาพให้ได้มากที่สุด แต่ครูรับเฉพาะภาพที่มีของครบเป๊ะ ๆ ต่อ 1 ภาพ คือ วงกลม 3 รูป, สามเหลี่ยม 1 รูป, สี่เหลี่ยม 2 รูป, เส้น 4 เส้น (ขาดหรือเกินแม้แต่ชิ้นเดียวไม่รับ) เราขี้เกียจเลยใช้แสตมป์ปั๊ม แต่แสตมป์แต่ละแบบใช้ได้จำกัด: วงกลม A ครั้ง, สามเหลี่ยม B ครั้ง, สี่เหลี่ยม C ครั้ง, เส้น D ครั้ง แล้วถามว่าทำภาพครบชุดได้สูงสุดกี่ภาพ

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

import sys
a, b, c, d = map(int, sys.stdin.read().split())
# หารปัดลง (// ใน Python) แล้วเอาตัวที่น้อยสุด = คอขวด
print(min(a // 3, b // 1, c // 2, d // 4))

C · Addition: เพิ่มกำลังทีละเมือง

มีค่าพลังงาน Fₙ สำหรับ N เมือง โดย F₀ = 1, F₁ = 3 และ Fₓ = 3·F₍ₓ₋₁₎ − 2·F₍ₓ₋₂₎ เครื่องเพิ่มกำลังได้ทีละเมือง ค่าใช้จ่ายก้าว x→x+1 คือ F₍ₓ₊₁₎ − Fₓ และมีเครื่องปั่นไฟผลิตได้ K หน่วยต่อก้าว (ต้องเหลือสำรอง ≥ 1) แล้วถามว่าไปได้สูงสุดกี่เมือง

import sys
K = int(sys.stdin.read())
# ก้าว x->x+1 ใช้พลังงาน 2**(x+1) และต้องเหลือสำรอง 1 หน่วย
# ก้าวจะทำได้เมื่อ 2**(x+1) <= K-1 (เดินสะสมจนก้าวถัดไปจ่ายไม่ไหว)
towns = 0
while (1 << (towns + 1)) <= K - 1:
    towns += 1
print(towns)

D · Diamond Glyph: เพชรบนกำแพงหิน

กำแพงสลักด้วย < และ > เต็มไปหมด ตัวอักษรพวกนี้จริง ๆ คือ "ขีดเฉียง" ที่ประกอบกันเป็นเพชรซ้อน ๆ (glyph) โจทย์ถามว่ามี glyph ทั้งหมดกี่อัน โดย glyph tier k คือเพชร (ring) ขนาด 1, 2, …, k ซ้อนศูนย์กลางเดียวกันครบทุกวง

* ตัวอย่างจากโจทย์ · มีเพชรเล็ก (ring ขนาด 1) 5 จุด และหนึ่งในนั้นซ้อนได้ถึง ring ขนาด 2 → 5 + 1 = 6

import sys
data = sys.stdin.read().split()
N, M = int(data[0]), int(data[1])
grid = [data[2 + i] for i in range(N)]

# ขีด 1 ขีดตรงกับตัวอักษรบนกริดไหม (ใช้ตารางเทียบด้านบน)
def ok_seg(x0, yt, kind):
    if not (0 <= x0 < M and 0 <= yt < 2 * N):   # หลุดขอบ = ไม่มีขีด
        return False
    r = yt // 2                      # yt คือครึ่งแถว แถวจริง = yt // 2
    if yt % 2 == 0:                  # yt คู่ = ครึ่งบน
        ch = '>' if kind == '\\' else '<'
    else:                            # yt คี่ = ครึ่งล่าง
        ch = '>' if kind == '/' else '<'
    return grid[r][x0] == ch

# ring ขนาด s รอบศูนย์กลาง (X,Y) มีครบทุกขีดไหม (4 ด้าน ด้านละ s ขีด)
def ring_ok(X, Y, s):
    for i in range(s):
        segs = ((X-s+i, Y-i-1, '/'), (X+i, Y-s+i, '\\'),        # ด้าน A, B
                (X+s-i-1, Y+i, '/'), (X-i-1, Y+s-i-1, '\\'))    # ด้าน C, D
        for (x0, yt, kind) in segs:
            if not ok_seg(x0, yt, kind):
                return False
    return True

ans = 0
for X in range(M + 1):
    for Y in range(2 * N + 1):       # Y ยาว 2N เพราะ 1 ช่อง = 2 ครึ่ง
        s = 1
        while ring_ok(X, Y, s):      # ซ้อนไปเรื่อย ๆ จนวงขาด
            s += 1
        ans += s - 1                 # ซ้อนได้ (s-1) ชั้น = glyph (s-1) อัน
print(ans)

import sys
data = sys.stdin.read().split()
N, M = int(data[0]), int(data[1])
g = [data[2 + i] for i in range(N)]

def at(r, c):                 # นอกกริด = ช่องว่าง (ไม่แมตช์ลายไหนเลย)
    return g[r][c] if 0 <= r < N and 0 <= c < M else '.'

ans = 0
for r in range(N):
    for c in range(M):
        # ---- glyph tier 1 : ring ขนาด 1 มี 2 ลาย ----
        # ลายนอน  <>   (เพชรเล็กคั่นระหว่างสองช่อง)
        if at(r, c) == '<' and at(r, c+1) == '>':
            ans += 1
        # ลายตั้ง  ><    (บล็อก 2x2)
        #          ><
        if at(r, c) == '>' and at(r, c+1) == '<' and at(r+1, c) == '>' and at(r+1, c+1) == '<':
            ans += 1
        # ---- glyph tier 2 : มีลายเดียว ยึด (r,c) ที่ '<' ซ้ายสุดของแถวกลาง ----
        #   . > < .
        #   < < > >
        #   . > < .
        if (at(r, c) == '<' and at(r, c+1) == '<' and at(r, c+2) == '>' and at(r, c+3) == '>'
                and at(r-1, c+1) == '>' and at(r-1, c+2) == '<'
                and at(r+1, c+1) == '>' and at(r+1, c+2) == '<'):
            ans += 1
print(ans)

E · Binary String Creation: สร้างสตริงวงกลม

ให้สตริงเลขฐานสอง A ยาว N ต้องสร้าง สตริงวงกลม B ที่สั้นที่สุด พร้อมลำดับการเดินซ้าย/ขวาบนวง เพื่อให้เดินเก็บตัวอักษรมาต่อกันได้เท่ากับ A

ตัวอย่างจากโจทย์ · มีหลายคำตอบที่ถูกได้ (เช่นโค้ดข้างล่างอาจได้ B=110 เดิน RRR ซึ่งก็ถูก)

import sys
data = sys.stdin.read().split()
n = int(data[0]); A = data[1]
if '0' not in A or '1' not in A:            # มีสัญลักษณ์เดียวล้วน
    print(1); print(A[0]); print('R' * (n - 1))
else:
    s1 = 2 if '11' in A else 1
    s0 = 2 if '00' in A else 1
    # วางบล็อกให้ช่องแรก (index 0) ตรงกับ A[0]
    B = ('1'*s1 + '0'*s0) if A[0] == '1' else ('0'*s0 + '1'*s1)
    M = len(B); pos = 0; moves = []
    for t in range(1, n):
        r, l = (pos + 1) % M, (pos - 1) % M  # เพื่อนบ้านขวา/ซ้าย (วนได้)
        if B[r] == A[t]: pos = r; moves.append('R')  # เดินโลภ ไปฝั่งที่บิตตรง
        else:            pos = l; moves.append('L')
    print(M); print(B); print(''.join(moves))

F · Quantum Counter: ตัวนับควอนตัม

เครื่องนับ alpha เริ่มที่ A, omega เริ่มที่ B ทุกวินาที alpha ลด 1 และ omega เพิ่ม 1 เกิด "wormhole" เมื่อ alpha หารด้วย omega ลงตัว (นับตอนเริ่มต้นด้วย) หยุดเมื่อตัวใดตัวหนึ่งเป็น 0 แล้วถามว่าเกิด wormhole กี่ครั้ง

import sys
A, B = map(int, sys.stdin.read().split())
S = A + B
lo, hi = B, S - 1
cnt, i = 0, 1
while i * i <= S:            # วนหาตัวหารถึงแค่รากของ S ก็พอ
    if S % i == 0:
        j = S // i           # ตัวหารมาเป็นคู่ (i, S//i)
        if lo <= i <= hi: cnt += 1
        if j != i and lo <= j <= hi: cnt += 1   # กันนับซ้ำตอน S เป็นกำลังสองพอดี
    i += 1
print(cnt)

G · Painting the NFTree: ต้นไม้ทาสี

มีต้นไม้ราก 1 แต่ละเส้นมี "สีที่อยากได้" หนึ่งครั้งการทา (operation) เลือกสี c เลือกจุด v แล้วไล่ทาเส้นลงลูก ๆ ที่ยังไม่ทาลงไปเรื่อย ๆ ด้วยสี c เดียวกัน พูดง่าย ๆ คือ ทา "ก้อนเส้นที่ต่อกันเป็นก้อนเดียว สีเดียวกัน" ได้ทีเดียว ถามหาจำนวนครั้งที่น้อยที่สุด

import sys
data = sys.stdin.read().split()
n = int(data[0]); idx = 1
colors = [set() for _ in range(n + 1)]   # colors[v] = เซตสีของเส้นที่ต่อกับจุด v
for _ in range(n - 1):
    u, v, c = int(data[idx]), int(data[idx+1]), int(data[idx+2]); idx += 3
    colors[u].add(c); colors[v].add(c)
# ผลรวมจำนวนสีต่างกันของทุกจุด ลบด้วยจำนวนเส้น (n-1)
print(sum(len(s) for s in colors) - (n - 1))

ปิดท้าย

สังเกตแพตเทิร์นร่วมของโจทย์ชุดนี้ไหมครับ บางข้อเป็นข้อแจกแต้มไว้อุ่นเครื่อง (เช่น A แค่แทนสูตรพื้นที่วงกลม, B แค่หาคอขวด) แต่ข้อที่ดูโหด เกือบทุกข้อ "ก้าวแรก" คือการ ทำสูตรที่ดูยุ่งให้ยุบเป็นของง่าย: recurrence กลายเป็นเลขยกกำลัง (C), เพชรที่ดูเหมือนซ้อนได้ไม่รู้จบกลายเป็นแค่เช็กสองชั้น (D), สตริงวงกลมกลายเป็นบล็อกไม่กี่ตัว (E), เงื่อนไขหารลงตัวกลายเป็นนับตัวหาร (F), การทาสีกลายเป็นนับก้อน (G) พอมองเห็นโครงสร้างที่ซ่อนอยู่ โค้ดที่เหลือก็สั้นนิดเดียว นั่นแหละคือเสน่ห์ของโจทย์แข่งครับ

ขอบคุณทีมออกโจทย์ที่ออกโจทย์ดี ๆ ให้ได้ฝึกคิด และมีเรื่องสนุก ๆ มาเล่าให้ฟังครับ อ้างอิงจาก:

1. ชุดโจทย์: รอบคัดเลือกย่อย ICPC 2026 Thailand (ชุดโจทย์กลาง จัดแข่งพร้อมกันหลายสนาม) · เล่มที่อ้างอิงคือของสนามภาคเหนือ: The 2026 ICPC Thailand Northern Region Contest (Problem Set) โดยเจ้าภาพสนาม ภาควิชาวิทยาการคอมพิวเตอร์ คณะวิทยาศาสตร์ มหาวิทยาลัยเชียงใหม่
2. ทีมออกโจทย์ (ตามที่ระบุในหน้าปกชุดโจทย์): Atittarn Buathep, Borworntat Dendumrongkul, Jessada Thutkawkorapin, Kittipat Pongarunotai, Mattanyu Tangngekkee, Natapong Sriwatanasakdi, Supakorn Kijwattanachai
3. เนื้อหาในบทความ: เรียบเรียงและเฉลยด้วยคำของผู้เขียนเอง ส่วน diagram ทั้งหมดวาดขึ้นใหม่ประกอบบทความ