programming.in.th · ข้อ 2016

ลำดับ DNA ตัวที่ R: นิยามที่เรียกตัวเอง

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

★★★★☆ dpcountingstring อ่าน 9 นาที เผยแพร่ 7 กันยายน 2026 อัปเดต 20 ตุลาคม 2026

โจทย์ · เติมช่องว่างใน DNA แล้วขอตัวที่ R

สาย DNA เขียนแทนด้วยตัวอักษรสี่ตัวคือ A C G T ตามชื่อนิวคลีโอไทด์สี่ชนิด บางตำแหน่งนักชีววิทยาระบุไม่ได้ว่าเป็นตัวไหน จึงเขียนเป็น N ซึ่งแทนตัวไหนก็ได้ในสี่ตัวนั้น

เราเรียกลำดับที่มี N ว่าลำดับไม่สมบูรณ์ และลำดับที่ไม่มี N เลยว่า ลำดับสมบูรณ์

ลำดับสมบูรณ์ตัวหนึ่ง เข้ากันได้ กับลำดับไม่สมบูรณ์ ถ้ามันเกิดจากการเติม N ทุกตัวด้วยนิวคลีโอไทด์สักตัว เช่น ACCCT เข้ากันได้กับ ACNNT แต่ AGGAT ไม่เข้า

ต่อมาโจทย์นิยามรูปแบบของลำดับ โดยถือว่า A มาก่อน C มาก่อน G มาก่อน T

งานของเราคือ ให้ลำดับไม่สมบูรณ์ยาว M ตัวมา พร้อมเลข K และ R แล้วหาลำดับสมบูรณ์รูปแบบ-K ตัวที่ R ตามลำดับพจนานุกรม ที่เข้ากันได้กับลำดับไม่สมบูรณ์นั้น

อินพุต / ขอบเขต / เอาต์พุต

EXAMPLE
InputOutput
9 3 5
ACANNCNNG		ACAAACCCG
5 4 10
ACANN		ACAGC

ใบ้

นิยามรูปแบบ-K เรียกตัวเอง ลองแทนรูปแบบ-(K−1) ด้วยนิยามของมันเองซ้ำไปเรื่อย ๆ สายรูปแบบ-K หน้าตาเป็นอย่างไร แล้วตัวอักษรคู่ติดกันแบบไหนที่บังคับให้ K ต้องใหญ่ขึ้น

ส่วน R ใหญ่ได้ถึงสองล้านล้าน (2 × 10^12) ไล่เรียงทีละตัวจนถึงตัวที่ R ไม่ทันในหนึ่งวินาทีแน่ ๆ

ถ้าเรานับได้ว่า "ลำดับที่ขึ้นต้นด้วย ACA มีกี่ตัว" จะช่วยอะไรได้บ้าง

ลองเอง · เติมช่องว่างให้ได้ลำดับอันดับที่ขอ

ช่องว่างสองช่อง ลองทุกแบบได้ในเวลาไม่นาน

แพตเทิร์น ACNN · ขอลำดับรูปแบบ-2 อันดับที่ 3 จากทั้งหมด 16 แบบ

กดที่ช่อง N เพื่อวนเปลี่ยนตัวอักษร

สายตอนนี้ เป็นรูปแบบ-2 ตามนิยามของโจทย์

เกมตรวจสายด้วยนิยามในโจทย์ตรง ๆ และบอกแค่ว่าผ่านหรือไม่

ถ้าเดาสุ่มแล้วเหนื่อย ลองตรึงช่อง N ช่องแรกไว้ค่าหนึ่ง แล้วถามว่าจะเหลือสายที่ผ่านกี่แบบ เลขนั้นบอกอะไรกับอันดับที่ขอ

เฉลย · คลี่นิยามที่เรียกตัวเอง

ที่มาของแนวคิดนี้

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

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

ตัวอย่างในโจทย์ใช้ตรวจว่าเราตีความนิยามถูกหรือไม่ได้ ตั้งแต่ก่อนเขียนโค้ดบรรทัดแรก

คลี่นิยามทีละชั้น: รูปแบบ-2 คือสายรูปแบบ-1 หนึ่งหรือสองสายต่อกัน รูปแบบ-3 คือไม่เกินสามสาย และต่อไปเรื่อย ๆ

ดังนั้นรูปแบบ-K คือสายที่ตัดเป็นท่อนเรียงขึ้นได้ไม่เกิน K ท่อน คำถามต่อไปคือต้องตัดตรงไหนบ้าง

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

ตัดตรงรอยต่อทุกจุดก็ได้ท่อนที่เรียงขึ้นทุกท่อน และตัดน้อยกว่านั้นไม่ได้ จำนวนท่อนที่น้อยที่สุดคือจำนวนรอยต่อบวกหนึ่ง

ลำดับเป็นรูปแบบ-K ก็ต่อเมื่อมีรอยต่อ (ตำแหน่งที่ตัวถัดไปเล็กลง) ไม่เกิน K − 1 ตำแหน่ง

แพตเทิร์น ACANNCNNG · K = 3 · ช่อง N คือช่องที่เราเติมได้ อันดับที่ 5 คือ ACAAACCCG · รอยต่อ 1 รอย ผ่าน A C A A A C C C G › ACAAACATG · รอยต่อ 3 รอย ไม่ผ่าน A C A A A C A T G › › › เครื่องหมายระหว่างช่องคือรอยต่อ จุดที่ตัวถัดไปเล็กลง
แถวบนคือคำตอบของตัวอย่างแรก ACAAACCCG มีรอยต่อ 1 รอย (C→A) แถวล่าง ACAAACATG เข้ากันได้กับแพตเทิร์นเดียวกัน แต่มีรอยต่อ 3 รอย (C→A, C→A, T→G) ช่องที่ระบายสีคือช่อง N ที่เติมเอง (วาดประกอบโดยผู้เขียน)
ตรวจตัวอย่างที่โจทย์ยกมา
ลำดับรอยต่อรูปแบบต่ำสุดที่เป็นได้โจทย์บอกว่า
AACCGT 0 รูปแบบ-1 เป็นรูปแบบ-1 ตรง
AACGTC 1 รูปแบบ-2 ไม่เป็นรูปแบบ-1 ตรง
AACCC 0 รูปแบบ-1 เป็นรูปแบบ-3 ตรง
ACACC 1 รูปแบบ-2 เป็นรูปแบบ-3 ตรง
ACACA 2 รูปแบบ-3 เป็นรูปแบบ-3 ตรง
GCACAC 3 รูปแบบ-4 ไม่เป็นรูปแบบ-3 ตรง
ACACACA 3 รูปแบบ-4 ไม่เป็นรูปแบบ-3 ตรง
สายจากนิยามในโจทย์ทั้งเจ็ดสาย นับรอยต่อแล้วได้ผลตรงกับที่โจทย์บอกทุกบรรทัด

นับก่อน แล้วค่อยเดิน

ระหว่างเติมจากซ้ายไปขวา ต้องจำแค่สองอย่าง

  • ตัวอักษรก่อนหน้าคือตัวไหน เพื่อรู้ว่าตัวถัดไปจะเป็นรอยต่อหรือไม่
  • ยังขึ้นท่อนใหม่ได้อีกกี่ท่อน

ตารางนับ f

  • f[i][c][d] = จำนวนวิธีเติมตำแหน่ง i ถึง M − 1 (นับตำแหน่งจาก 0) เมื่อตัวก่อนหน้าคือ c และยังมีสิทธิ์ใช้อีก d ท่อน นับรวมท่อนที่กำลังเดินอยู่
  • c = 0 ถึง 3 แทน A C G T ส่วน c = 4 แปลว่ายังไม่มีตัวก่อนหน้า
  • สถานะเริ่มคือ i = 0, c = 4, d = K และจำนวนลำดับที่ผ่านทั้งหมดคือ f[0][4][K]
สูตรของตาราง f 
f[M][c][d] = 1                     เมื่อ d ≥ 1 (เติมครบแล้ว)
f[i][c][d] = ผลรวมของ f[i+1][x][nd]  ทุก x ใน A C G T ที่แพตเทิร์นตำแหน่ง i ยอม
    nd = d − 1   ถ้า c < 4 และ x < c   (เกิดรอยต่อ ขึ้นท่อนใหม่)
    nd = d       ถ้าไม่ใช่กรณีนั้น
    ข้าม x ที่ทำให้ nd < 1              (ท่อนหมด)

ลองคิดหนึ่งช่องบนตัวอย่างแรก

ตัวอย่างแรกมี M = 9 แถว f[9] ทุกช่องที่ d ≥ 1 เป็น 1

ช่อง f[7][C][1] คือเติมตำแหน่ง 7 ถึง 8 โดยตัวก่อนหน้าเป็น C และเหลือท่อนเดียว ตำแหน่ง 7 เป็น N ส่วนตำแหน่ง 8 เป็น G

  • x = A: A เล็กกว่า C ต้องขึ้นท่อนใหม่ แต่ไม่มีท่อนเหลือ ข้าม
  • x = C: อ่าน f[8][C][1] = 1
  • x = G: อ่าน f[8][G][1] = 1
  • x = T: อ่าน f[8][T][1] = 0 เพราะตำแหน่ง 8 ต้องเป็น G ซึ่งเล็กกว่า T และไม่มีท่อนเหลือ

รวมได้ f[7][C][1] = 2 คือสาย CG กับ GG

ตารางมี (M + 1) × 5 × (K + 1) ช่อง แต่ช่องที่ต้องคำนวณด้วยสูตรคือแถว i = 0 ถึง M − 1 ที่ d ≥ 1 รวม M × 5 × K ช่อง ที่ขอบเขตเต็มคือ 2,500,000 ช่อง ช่องละลองสี่ตัวอักษร รวม 10,000,000 ครั้ง

ช่องที่ใหญ่เกิน 64 บิต

โจทย์รับประกันว่าลำดับที่ผ่านมีไม่เกิน 4 × 10^18 ตัว คำรับประกันนี้ครอบคลุมเฉพาะช่องที่เดินถึง คือช่องที่มีคำนำหน้าจริงพาไปถึง แต่ตารางคำนวณทุกช่อง

ตัวอย่าง แพตเทิร์น TA ตามด้วย N อีก n ตัว และ K = 2 หลัง TA ใช้ไปแล้วสองท่อน ช่อง f[2][A][2] (ยังเหลือสองท่อน) จึงไม่มีคำนำหน้าไหนพาไปถึง

ช่องนั้นนับสายยาว n ที่มีรอยต่อไม่เกินหนึ่งรอย และเกินค่ามากที่สุดของ long long (ราว 9.22 × 10^18) ตั้งแต่ n = 1,727 ขณะที่ลำดับที่ผ่านจริงตอนนั้นมีแค่ 861,456,960 ตัว

ช่องที่เดินถึงอ่านแต่ช่องที่เดินถึง เพราะต่อตัวอักษรที่ใช้ได้อีกหนึ่งตัวท้ายคำนำหน้าที่เดินถึง ก็ยังได้คำนำหน้าที่เดินถึง ค่าที่ล้นไม่มีทางไหลมาถึงคำตอบ

ถึงอย่างนั้น long long เป็นจำนวนเต็มแบบมีเครื่องหมาย และการล้นของมันเป็น undefined behavior คือมาตรฐาน C++ ไม่กำหนดว่าผลจะออกมาเป็นอะไร

โค้ดเต็มเก็บค่าเป็น unsigned long long (จำนวนเต็ม 64 บิตที่ไม่มีค่าติดลบ) และบวกแบบมีเพดาน ผลรวมที่เกิน 4 × 10^18 เก็บเป็น 4 × 10^18

ช่องที่เดินถึงไม่เกินเพดานนี้อยู่แล้ว ส่วน R ไม่เกิน 2 × 10^12 การเทียบ R กับช่องที่ชนเพดานให้ผลเหมือนใช้ค่าจริง

ตารางพร้อมแล้วก็เดินหาตัวที่ R ทีละตำแหน่ง ไล่ตัวอักษรตามลำดับพจนานุกรม แล้วถามทีละตัวว่า "ถ้าเลือกตัวนี้ จะมีลำดับตามมาได้กี่แบบ" เรียกจำนวนนั้นว่า cnt

การเดินหาตัวที่ R 
เริ่ม c = 4, d = K
ทุกตำแหน่ง i จาก 0 ถึง M − 1:
    ไล่ x = A, C, G, T ที่แพตเทิร์นยอม (คำนวณ nd แบบเดียวกับข้างบน ข้าม nd < 1)
        cnt = f[i+1][x][nd]
        ถ้า R ≤ cnt: เลือก x ตั้ง c = x, d = nd แล้วไปตำแหน่งถัดไป
        ไม่อย่างนั้น: R = R − cnt แล้วลอง x ตัวถัดไป
เดินหาตัวที่ R (ส่วนเดียวกันในโค้ด C++) 
string out; int c = 4, d = D;            // c = ตัวก่อนหน้า (4 คือยังไม่มี), d = ท่อนที่เหลือใช้ได้
for (int i = 0; i < M; i++) {
    for (int x = 0; x < 4; x++) {        // ไล่ A C G T ตามลำดับพจนานุกรม
        if (s[i] != 'N' && s[i] != AL[x]) continue;
        int nd = (c < 4 && x < c) ? d - 1 : d;   // ตัวนี้เล็กกว่าตัวก่อน แปลว่าขึ้นท่อนใหม่
        if (nd < 1) continue;
        ull cnt = f[i + 1][x][nd];       // ถ้าเลือกตัวนี้ จะมีลำดับตามมาได้กี่แบบ
        if (R <= cnt) { out.push_back(AL[x]); c = x; d = nd; break; }
        R -= cnt;                        // ตัวที่ตามหาอยู่หลังก้อนนี้ ข้ามไปทั้งก้อน
    }
}

ตัวอย่างแรก · ไล่ทีละตำแหน่ง

เจ็ดตัวแรกที่โปรแกรมสร้างได้คือ ACAAACAAG, ACAAACACG, ACAAACAGG, ACAAACCAG, ACAAACCCG, ACAAACCGG, ACAAACCTG ตรงกับในโจทย์ทุกตัว ตัวที่ 5 คือ ACAAACCCG

ตารางข้างล่างนับตำแหน่งจาก 1 เมื่อเลือกตัวที่ตำแหน่ง p แล้ว ส่วนที่ยังต้องเติมคือ index p ถึง M − 1 (นับจาก 0) จำนวนที่ตามมาจึงอ่านจาก f[p][x][nd]

กดถัดไปเพื่อเดินทีละตำแหน่ง

เดินหาตัวที่ 5 ทีละตำแหน่ง
ตำแหน่งR ที่เหลือ ไล่ตัวเลือก (ตัว: จำนวนที่ตามมา)เลือก
1 5 A:81 <- A
2 5 C:81 <- C
3 5 A:81 <- A
4 5 A:36 <- A
5 5 A:15 <- A
6 5 C:15 <- C
7 2 A:3 C:4 <- C
8 1 A:1 C:1 <- C
9 1 G:1 <- G

ตำแหน่งที่แพตเทิร์นกำหนดตัวอักษรไว้มีตัวเลือกเดียว จึงไม่มีการหักค่า ส่วนช่อง N ลองจาก A ขึ้นไป และหัก R เฉพาะตัวที่จำนวนตามมาน้อยกว่า R

อีกมุมหนึ่ง: ไล่สร้างทุกตัวเลย (ชุดทดสอบย่อย M ≤ 10)

เมื่อ M ไม่เกิน 10 ลำดับที่เข้ากันได้มีมากที่สุด 4^10 = 1,048,576 ตัว สร้างทั้งหมดแล้วหยิบตัวที่ R ได้สบาย

ถ้าเรียกซ้ำโดยไล่ A C G T ตามลำดับ ผลที่ได้ก็เรียงตามพจนานุกรมมาเอง ไม่ต้องเรียงทีหลัง

ดูโค้ดของชุดทดสอบย่อย
dna_sub.cpp 
// เฉลยชุดทดสอบย่อย M ไม่เกิน 10 (20 คะแนน)
// สร้างลำดับที่เข้ากันได้ทุกอันตรง ๆ แล้วหยิบตัวที่ R ออกมา
#include <bits/stdc++.h>
using namespace std;
int M, K; long long R;
string pat, cur;
vector<string> all;
const char* AL = "ACGT";

void rec(int i) {
    if (i == M) {
        int drop = 0;                                      // จำนวนตำแหน่งที่ตัวถัดไปเล็กลง คือรอยต่อของท่อน
        for (int j = 0; j + 1 < M; j++) if (cur[j] > cur[j + 1]) drop++;
        if (drop <= K - 1) all.push_back(cur);
        return;
    }
    for (int x = 0; x < 4; x++) {
        if (pat[i] != 'N' && pat[i] != AL[x]) continue;
        cur.push_back(AL[x]); rec(i + 1); cur.pop_back();
    }
}

int main() {
    scanf("%d %d %lld", &M, &K, &R);
    char buf[64]; scanf("%s", buf); pat = buf;
    rec(0);                                                // การเรียกซ้ำไล่เรียงตามพจนานุกรมอยู่แล้ว
    printf("%s\n", all[R - 1].c_str());
}

วิธีนี้ได้ 20 คะแนน และใช้ตรวจตารางกับการเดินของเวอร์ชันเต็มได้ เพราะมันไม่มีตาราง f แต่มันนับรอยต่อแบบเดียวกัน การนับรอยต่อต้องตรวจกับนิยามเรียกซ้ำแยกอีกชั้น

บั๊กที่ง่ายที่สุดในการเดินคือเขียน R < cnt แทน R ≤ cnt ซึ่งเท่ากับเดินแบบนับอันดับจาก 0 ทั้งที่ R นับจาก 1 ผลคือได้ตัวที่ R + 1

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

การ์ดข้างล่างนับรอบของลูปในสุดตามโค้ดของแต่ละวิธี

วิธีที่ 1

ไล่สร้างทุกลำดับ

(4^M − 1)/3 × 4 + 4^M × (M − 1) รอบ

นับกรณี N ทั้งสาย: (4^M − 1)/3 คือจุดที่การเรียกซ้ำยังเติมไม่ครบ จุดละวนสี่ตัวอักษร ส่วน 4^M คือสายที่เติมครบ สายละเทียบตัวติดกัน M − 1 คู่

ที่ M = 10 ได้ 10,835,284 รอบ ถ้า K = 10 ทุกสายผ่าน ต้องเก็บ 1,048,576 สาย สายละ 32 ไบต์ รวม 33.6 MB

ที่ M = 50,000 N ทั้งสายยังเป็นอินพุตที่ถูกต้องเมื่อ K = 1 (สายที่ผ่านมีราว 2.1 × 10^13 สาย) แต่สายที่ต้องสร้างมีราว 10^30103 สาย

ได้ชุด 20 คะแนน

วิธีเต็ม

นับก่อนแล้วเดิน

M × 5 × K × 4 + 4M รอบ

M × 5 × K คือช่องของตารางที่คำนวณ (ตำแหน่ง × ตัวก่อนหน้า × ท่อนที่เหลือ) ช่องละลองสี่ตัวอักษร ส่วน 4M คือการเดิน ตำแหน่งละไม่เกินสี่ตัว

ที่ K = 10: M = 10 ได้ 2,040 รอบ และ M = 50,000 ได้ 10,200,000 รอบ ตารางใช้ 22.0 MB จากลิมิต 128 MB

ได้ทุกชุด

วิธีไหนได้คะแนนชุดไหน
วิธีชุด 20 คะแนน (M ≤ 10)ชุดที่เหลือ (M ถึง 50,000)
ไล่สร้างทุกลำดับได้ไม่ทัน
นับก่อนแล้วเดินได้ได้
ที่ M = 10 วิธีแรกใช้ 10,835,284 รอบ ยังทันสบาย แต่มันโตแบบทวีคูณตามจำนวน N ส่วนวิธีเต็มโตแบบเชิงเส้นตาม M

โค้ด C++

ตาราง f เก็บเป็น unsigned long long ช่องละ 8 ไบต์ และโค้ดจองช่อง d ไว้ 11 ช่องเสมอ ขนาดคือ (M + 1) × 5 × 11 ช่อง เต็มขอบเขต 22.0 MB จากลิมิต 128 MB

ดูโค้ดเต็ม
dna.cpp 
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
static const ull CAP = 4000000000000000000ULL;   // เพดานกันล้น ช่องที่เดินถึงไม่มีทางเกินนี้ (โจทย์รับประกัน)
static inline ull addc(ull a, ull b){ ull s=a+b; return (s>CAP||s<a)?CAP:s; }
const char* AL="ACGT";
int main(){
    int M,K; unsigned long long R;
    if(scanf("%d %d %llu",&M,&K,&R)!=3) return 0;
    static char buf[50005]; scanf("%s",buf); string s=buf;
    int D=K;                                   // จำนวน "ท่อน" ที่ยังเหลือใช้ได้ 1..K
    // f[i][c][d] = จำนวนวิธีเติมตำแหน่ง i..M-1 เมื่อตัวก่อนหน้าเป็น c และเหลือท่อนได้อีก d
    // c = 0..3 คือตัวอักษรก่อนหน้า, c = 4 คือยังไม่มีตัวก่อนหน้า (ตำแหน่งแรก)
    vector<array<array<ull,11>,5>> f(M+1);
    for(int c=0;c<5;c++) for(int d=0;d<=D;d++) f[M][c][d]= d>=1 ? 1 : 0;
    for(int i=M-1;i>=0;i--)
        for(int c=0;c<5;c++)
            for(int d=0;d<=D;d++){
                ull v=0;
                if(d>=1) for(int x=0;x<4;x++){
                    if(s[i]!='N' && s[i]!=AL[x]) continue;
                    int nd = (c<4 && x<c) ? d-1 : d;      // ลดลงเมื่อ "ตก" คือเริ่มท่อนใหม่
                    if(nd<1) continue;
                    v=addc(v,f[i+1][x][nd]);
                }
                f[i][c][d]=v;
            }
    string out; int c=4,d=D;
    for(int i=0;i<M;i++){
        for(int x=0;x<4;x++){
            if(s[i]!='N' && s[i]!=AL[x]) continue;
            int nd = (c<4 && x<c) ? d-1 : d;
            if(nd<1) continue;
            ull cnt=f[i+1][x][nd];
            if(R<=cnt){ out.push_back(AL[x]); c=x; d=nd; break; }
            R-=cnt;
        }
    }
    printf("%s\n",out.c_str());
}
โค้ดส่วนไหนทำขั้นไหน
ส่วนในโค้ดทำอะไร
CAP, addcบวกแบบมีเพดาน ผลรวมที่เกิน CAP เก็บเป็น CAP
f[M][c][d]จุดเริ่ม: เติมครบแล้วมีหนึ่งวิธีเมื่อ d ≥ 1
ลูป i จาก M − 1 ลงมาเติมตาราง f จากท้ายมาหน้า
nd = (c<4 && x<c) ? d-1 : dx เล็กกว่าตัวก่อนหน้า คือรอยต่อ ใช้ท่อนเพิ่มหนึ่งท่อน
if(nd<1) continueท่อนหมดแล้ว ทางนี้ใช้ไม่ได้
ลูปท้ายที่สร้าง outเดินหาตัวที่ R: ไม่เกิน cnt ก็เลือก มากกว่าก็หัก cnt

ตรวจอะไรไปแล้วบ้าง

  • การนับรอยต่อ: เทียบกับนิยามเรียกซ้ำของโจทย์คำต่อคำ และกับการแบ่งท่อนแบบลองทุกจุดตัด ทุกสายยาว 1 ถึง 7 กับ K = 1 ถึง 8 รวม 174,752 คู่ ตรงทุกคู่
  • 500 ชุด (ตัวอย่างสองชุดในโจทย์กับชุดสุ่ม M 1 ถึง 8): คำตอบอ้างอิงมาจากไล่ทุกสาย เรียงด้วย sorted แล้วกรองด้วยการแบ่งท่อน โดยไม่ใช้รอยต่อ โค้ดเต็มและโค้ดชุดย่อยตรงทุกชุด
  • 200 ชุดสุ่ม M 9 ถึง 10: โค้ดเต็มตรงกับโค้ดชุดย่อยทุกชุด
  • รุ่น R < cnt บนทั้ง 700 ชุดข้างบน: ผลตรงกับที่อธิบายในหัวข้อไล่สร้างทุกชุด
  • ขอบเขตเต็ม: วัดบนสามชุดที่ M = 50,000 และอยู่ในเงื่อนไขของโจทย์ (K = 10 มี N 30 ตัว · N ทั้งสาย K = 1 · TA ตามด้วย N K = 2)
  • เวลาของสามชุดนั้นราว 30 มิลลิวินาที หน่วยความจำสูงสุด 25.8 MB เทียบลิมิต 1 วินาที 128 MB
  • โค้ดชุดย่อยที่ M = 10 เป็น N ทั้งสาย K = 10: 0.05 วินาที 37.3 MB
  • รุ่นที่ใช้ long long บวกตรง ๆ ไม่มีเพดาน: ตอบตรงกันทั้งสามชุด แต่ -fsanitize=undefined ฟ้องการล้นในชุด TA

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

ทดสอบตัวเองและอ่านต่อ

สาย CATGA เป็นรูปแบบ-K ได้ตั้งแต่ K เท่าไร

รอยต่ออยู่ที่ C→A, T→G, G→A รวม 3 รอย ต้องใช้อย่างน้อย 4 ท่อน คือเป็นรูปแบบ-4 ขึ้นไป

ถ้าเผลอเขียน R < cnt ตัวอย่างแรกจะตอบอะไร

ACAAACCGG ซึ่งเป็นตัวที่ 6 ในเจ็ดตัวแรกที่โจทย์ยกมา

โจทย์รับประกันว่าจำนวนไม่เกิน 4 × 10^18 แล้วทำไมโค้ดยังต้องมีเพดาน

คำรับประกันครอบคลุมแค่ช่องที่เดินถึง ส่วนตารางคำนวณทุกช่อง และช่องที่เดินไม่ถึง (เช่นยังเหลือสองท่อนหลัง TA) เกิน long long ได้

การนับก่อนแล้วเดินมีบทเต็มพร้อมโจทย์ฝึกที่ นับก่อน แล้วค่อยเดินไปหาตัวที่ต้องการ

แหล่งที่มา

  1. โจทย์ DNA บน programming.in.th ข้อ 2016 programming.in.th/tasks/2016 (สืบค้น 6 กันยายน 2026)
  2. ต้นทางของโจทย์คือ Asia-Pacific Informatics Olympiad 2008