programming.in.th · ข้อ 2016

ลำดับ DNA ตัวที่ R: นิยามที่เรียกตัวเอง ซ่อนการนับง่าย ๆ ไว้ข้างใน

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

★★★★☆ dpcountingstring อ่าน 11 นาที 7 กันยายน 2026

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

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

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

ต่อมาโจทย์นิยาม รูปแบบ ของลำดับ ลำดับเป็นรูปแบบ-1 ถ้าตัวอักษรเรียงจากน้อยไปมาก ตลอดสาย (ตัวไหนก็ต้องน้อยกว่าหรือเท่ากับตัวขวามือของมัน) และเป็นรูปแบบ-j สำหรับ j > 1 ถ้ามันเป็นรูปแบบ-(j−1) อยู่แล้ว หรือเกิดจากเอาลำดับรูปแบบ-(j−1) มาต่อกับลำดับรูปแบบ-1

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

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

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

ใบ้

นิยามของรูปแบบ-K ฟังดูซับซ้อนเพราะมันนิยามแบบเรียกตัวเอง แต่ลองอ่านอีกรอบว่ามันแปลว่า "ตัดสายออกเป็นท่อนได้ไม่เกิน K ท่อน โดยแต่ละท่อนเรียงจากน้อยไปมาก" แล้วถามต่อว่า จุดที่ต้องตัด คือจุดไหนบ้าง

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

แพตเทิร์น ACANNCNNG · ช่อง N คือช่องที่เราเติมได้ อันดับที่ 5 คือ ACAAACCCG · รอยต่อ 1 รอย ผ่าน A C A A A C C C G › ACAAACATG · รอยต่อ 3 รอย เกินเพดาน 2 จึงตก A C A A A C A T G › › › เครื่องหมายระหว่างช่องคือรอยต่อ จุดที่ตัวถัดไปเล็กลง
แพตเทิร์น ACANNCNNG มีช่องว่างให้เติม 4 ช่อง และเพดานรอยต่อคือ 2 รอย แถวบนคือคำตอบอันดับที่ 5 ซึ่งมีรอยต่อ 1 รอย จึงผ่าน แถวล่างคือ ACAAACATG ที่เข้ากันได้กับแพตเทิร์นเหมือนกันแต่มีรอยต่อ 3 รอย จึงตกไป รอยต่อคือจุดที่ตัวถัดไปเล็กลงตามลำดับ A น้อยกว่า C น้อยกว่า G น้อยกว่า T (วาดประกอบโดยผู้เขียน)

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

ช่องว่างสองช่อง พอให้เห็นว่ารอยต่อคืออะไร

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

กดที่ช่อง N เพื่อวนเปลี่ยนตัวอักษร ช่องที่ตัวถัดไปเล็กลงจะถูกทำเครื่องหมายว่าเป็นรอยต่อ

รอยต่อตอนนี้ 0 ตำแหน่ง · เพดานคือ 0

ลำดับรูปแบบ-K คือลำดับที่มีรอยต่อไม่เกิน K ลบหนึ่งตำแหน่ง

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

เฉลย · นิยามที่เรียกตัวเอง แปลเป็นการนับรอยต่อ

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

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

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

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

หลังเขียนเสร็จผมสุ่ม 600 ชุดเทียบกับการไล่สร้างทุกตัวแล้วเรียง ตรงกันหมด สองอย่างที่ต้องระวังตอนออกแบบคือทิศของการเทียบ R ≤ cnt ซึ่งพลาดข้างเดียวก็เลื่อนคำตอบไปหนึ่งตัว กับค่าล้น เพราะจำนวนสายที่เป็นไปได้พุ่งถึงระดับ 4 × 10¹⁸ ได้สบาย

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

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

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

ตรวจตัวอย่างที่โจทย์ยกมา
ลำดับรอยต่อรูปแบบต่ำสุดที่เป็นได้ตรงกับที่โจทย์บอกไหม
AACCGT 0 รูปแบบ-1 เป็นรูปแบบ-1
AACGTC 1 รูปแบบ-2 เป็นรูปแบบ-3
AACCC 0 รูปแบบ-1 เป็นรูปแบบ-1
ACACC 1 รูปแบบ-2 เป็นรูปแบบ-3
ACACA 2 รูปแบบ-3 เป็นรูปแบบ-3
GCACAC 3 รูปแบบ-4 ไม่เป็นรูปแบบ-3
ACACACA 3 รูปแบบ-4 ไม่เป็นรูปแบบ-3
โจทย์บอกว่า AACCGT เป็นรูปแบบ-1 แต่ AACGTC ไม่เป็น และ AACCC ACACC ACACA เป็นรูปแบบ-3 ส่วน GCACAC ACACACA ไม่เป็น คอลัมน์รอยต่ออธิบายได้ครบทุกบรรทัดโดยไม่ต้องแตะนิยามที่เรียกตัวเองอีกเลย

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

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

คำนวณ f[i][c][d] ถอยหลังจากท้ายมาหน้า แปลว่า ถ้ายืนที่ตำแหน่ง i โดยตัวก่อนหน้าเป็น c และเหลือท่อนได้ d จะเติมส่วนที่เหลือได้กี่แบบ ขนาดตารางคือ M × 5 × (K + 1) ซึ่งเต็มขอบเขตก็แค่ 2,750,000 ช่อง

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

หัวใจของทั้งข้อ 
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;                        // ตัวที่ตามหาอยู่หลังก้อนนี้ ข้ามไปทั้งก้อน
    }
}

ไล่การเดินหาตัวที่ 5 ของตัวอย่างแรก

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

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

เดินหาตัวที่ 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 มีตัวเลือกเดียว จึงไม่มีการหักค่า ส่วนตำแหน่งที่เป็น N จะเห็นว่า 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 คะแนน และที่สำคัญกว่านั้นคือ มันเป็นตัวตรวจสอบที่ตรงไปตรงมาที่สุดสำหรับเวอร์ชันเต็ม ผมสุ่มแพตเทิร์นสั้น ๆ ที่มี N ปนบ้าง 600 ชุด แล้วสุ่ม R ในช่วงที่ถูกต้อง เทียบสองโปรแกรม ตรงกันหมด

กับดักที่เจอบ่อยในโจทย์ตระกูล "ตัวที่ R" มีสองอัน อันแรกคือเผลอเทียบเป็น R < cnt แทน R ≤ cnt ซึ่งจะเลื่อนคำตอบไปหนึ่งช่องเสมอ อันที่สองคือค่าล้น เพราะจำนวนลำดับใหญ่ได้ถึง 4 × 10^18 ซึ่งชนเพดานของจำนวนเต็ม 64 บิตแบบมีเครื่องหมายพอดี โค้ดเต็มจึงบวกแบบมีเพดานกันไว้

บิลค่าใช้จ่าย · เทียบสองทางด้วยหน่วยเดียวกัน
ทางขอบเขตที่มันไหวงานคร่าว ๆ
ไล่สร้างทุกลำดับ M ไม่เกิน 10 1,048,576 ลำดับ
นับก่อนแล้วเดิน M ถึง 50,000 200,000 ครั้ง
แถวบนต้องสร้างของจริงทุกตัวก่อนจะหยิบตัวที่ต้องการ แถวล่างไม่สร้างของเลยแม้ตัวเดียว มันแตะแค่สี่ตัวเลือกต่อหนึ่งตำแหน่ง ต่างกันตรงที่แถวบนโตแบบทวีคูณตามความยาว ส่วนแถวล่างโตแบบเชิงเส้น นั่นคือเหตุผลเดียวที่ขอบเขตเต็มเป็นไปได้

โค้ด C++

ตาราง f เก็บเป็น unsigned long long ขนาด (M + 1) × 5 × (K + 1) เต็มขอบเขตคือราว 21 เมกะไบต์ อยู่ในลิมิต 128 เมกะไบต์

ดูโค้ดเต็ม
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());
}

เวลาที่วัดได้บนเครื่องผม แพตเทิร์นยาว 50,000 ตัวที่มี N ปนอยู่ราวหนึ่งในห้า และ K เท่ากับ 10 ใช้เวลา 59 มิลลิวินาที จากลิมิตหนึ่งวินาที

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

ท่าที่ติดมือกลับไป

ท่าของข้อนี้คือนับก่อนแล้วค่อยเดิน ซึ่งใช้กับโจทย์ "ขอตัวที่ R" ได้ทุกข้อที่นับได้ และสิ่งที่เรานับคือจำนวนสตริง (string แปลว่าสายอักขระ คือลำดับของตัวอักษรที่เรียงต่อกัน) ที่เติมช่องว่างได้ตามเงื่อนไข โดยไม่ต้องสร้างสตริงพวกนั้นขึ้นมาจริงแม้ตัวเดียว

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

สรุปบรรทัดเดียว

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

แหล่งที่มา

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