programming.in.th · ข้อ 2033

POI: ค่าของโจทย์ตั้งโดยคนที่ทำไม่ได้

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

★☆☆☆☆ simulationcounting อ่าน 8 นาที 11 กันยายน 2026

โจทย์ · โอลิมปิกที่ค่าของข้อตั้งหลังแข่งจบ

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

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

ตารางอันดับเรียงคะแนนจากมากไปน้อย ถ้าคะแนนเสมอ คนที่ทำได้มากข้อกว่าอยู่ก่อน ถ้ายังเสมออีก คนที่เลขประจำตัวน้อยกว่าอยู่ก่อน Philip มีเลขประจำตัว P เขางงกับกติกานี้ และอยากรู้แค่สองอย่าง คือตัวเองได้กี่คะแนน กับอยู่อันดับที่เท่าไร

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

EXAMPLE
InputOutput
5 3 2
0 0 1
1 1 0
1 0 0
1 1 0
1 1 0
 3 2

ตัวอย่างนี้มีห้าคน สามข้อ Philip คือคนที่ 2 แถวที่สองของตาราง (1 1 0) จึงบอกว่าเขาทำข้อไหนได้บ้าง เอาต์พุตตัวแรกคือคะแนน ตัวที่สองคืออันดับ

ใบ้

ลองถามว่าตอนอ่านแถวของคนที่ 1 จบ เรารู้คะแนนของเขาหรือยัง ค่าของข้อที่ 1 ขึ้นกับใครบ้าง แล้วเราต้องอ่านไปถึงไหนถึงจะรู้

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

ลองเอง · จัดตารางอันดับด้วยมือ

ห้าคนสามข้อจากตัวอย่างในโจทย์ Philip คือคนที่ 2 เริ่มจากคิดค่าของแต่ละข้อก่อน แล้วค่อยเรียงคน

คนที่ ข้อ 1ข้อ 2ข้อ 3 อันดับ
001  
110  
100  
110  
110  
ค่าข้อ ???  

ยังไม่ได้วางใคร

กดเลขประจำตัวทีละคน เริ่มจากคนที่ควรอยู่อันดับ 1 ลงไปจนครบ

ค่าของแต่ละข้อยังซ่อนอยู่ ลองคิดเองก่อน ถ้าติดค่อยกดเปิดค่าข้อ

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

เฉลย ตอนที่ 1 · ค่าของข้อต้องรอให้อ่านครบทุกคน

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

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

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

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

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

ข้อ 1ข้อ 2ข้อ 3 คะแนน คนที่ 1 คนที่ 2 Philip คนที่ 3 คนที่ 4 คนที่ 5 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 41 + 2 = 311 + 2 = 31 + 2 = 3 ค่าข้อ 1 2 4
ตัวอย่างในโจทย์ ค่าของแต่ละข้อคือจำนวนช่องที่เป็น 0 ในแนวตั้งนั้น ได้ 1, 2, 4 ตามลำดับ Philip (คนที่ 2) ทำได้ข้อที่ค่า 1 กับ 2 จึงได้ 3 คะแนน ส่วนคนที่ 1 ทำได้ข้อเดียว แต่เป็นข้อที่ค่าสูงสุด จึงได้คะแนนมากที่สุด

สังเกตคนที่ 1 ในภาพ เขาทำได้แค่ข้อเดียว แต่ข้อนั้นมีคนทำไม่ได้ 4 คนจาก 5 คะแนนของเขาจึงชนะทุกคนที่ทำได้สองข้อ ในเกมชุดสุดท้ายข้างบน Philip ก็ได้อานิสงส์แบบเดียวกัน จัดตามจำนวนข้อเขาจะอยู่อันดับ 5 แต่อันดับจริงคือ 2

เฉลย ตอนที่ 2 · ไม่ต้องเรียงทั้งตาราง นับแค่คนที่อยู่เหนือ

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

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

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

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

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

ตัวเทียบสามชั้น 
// คนที่ i ต้องอยู่เหนือ Philip (คนที่ me) ไหม
bool ahead(int i, int me){
    if(score[i] != score[me]) return score[i] > score[me];    // ชั้นที่ 1 คะแนน
    if(solved[i] != solved[me]) return solved[i] > solved[me]; // ชั้นที่ 2 จำนวนข้อ
    return i < me;                                              // ชั้นที่ 3 เลขประจำตัว
}

จุดที่พลาดง่ายคือชั้นที่สองกับสาม ถ้านับเฉพาะคนที่คะแนนมากกว่า Philip คนที่คะแนนเท่าเขาจะหายไปจากการนับทั้งหมด ในเกมชุดที่สอง Philip เสมอคะแนนกับอีก 2 คน ท่าที่นับแค่คะแนนจะให้อันดับ 4 ขณะที่อันดับจริงคือ 6

ไล่ตัวอย่างทีละคน

เทียบทุกคนกับ Philip (คนที่ 2) ในตัวอย่างของโจทย์ ค่าข้อคือ 1, 2, 4

ตัวอย่างในโจทย์ เทียบกับ Philip
คนที่ทำได้ข้อคะแนนจำนวนข้อ เทียบกับ Philipอยู่เหนือ (สะสม)
1 3 4 1 คะแนนมากกว่า 1
2 1, 2 3 2 Philip เอง 1
3 1 1 1 คะแนนน้อยกว่า 1
4 1, 2 3 2 เสมอทั้งคู่ เลขมากกว่า 1
5 1, 2 3 2 เสมอทั้งคู่ เลขมากกว่า 1

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

โค้ด

ดูโค้ดเต็ม
poi.cpp 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, t, p;
    if(scanf("%d %d %d", &n, &t, &p) != 3) return 0;
    // เก็บตารางทั้งหมดไว้ก่อน เพราะค่าของข้อจะรู้ก็ต่อเมื่ออ่านครบทุกคน
    vector<vector<char>> a(n, vector<char>(t));
    vector<int> value(t, 0);   // ค่าของข้อ j = จำนวนคนที่ทำข้อนั้นไม่ได้
    for(int i = 0; i < n; i++)
        for(int j = 0; j < t; j++){
            int x; scanf("%d", &x);
            a[i][j] = (char)x;
            if(x == 0) value[j]++;
        }
    // รอบสอง ตอนนี้รู้ค่าของทุกข้อแล้ว จึงคิดคะแนนของแต่ละคนได้
    vector<long long> score(n, 0);
    vector<int> solved(n, 0);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < t; j++)
            if(a[i][j]){ score[i] += value[j]; solved[i]++; }
    int me = p - 1;
    int ahead = 0;   // จำนวนคนที่ต้องอยู่เหนือ Philip ในตาราง
    for(int i = 0; i < n; i++){
        if(i == me) continue;
        if(score[i] != score[me]){
            if(score[i] > score[me]) ahead++;
        } else if(solved[i] != solved[me]){
            if(solved[i] > solved[me]) ahead++;
        } else if(i < me) ahead++;   // เสมอทั้งสองอย่าง เลขประจำตัวน้อยกว่าได้อยู่ก่อน
    }
    printf("%lld %d\n", score[me], ahead + 1);
}

ตารางเก็บเป็น char ช่องละไบต์ สี่ล้านช่องจึงใช้ราว 4 เมกะไบต์ ถ้าเก็บเป็น int จะเป็น 16 เมกะไบต์ ซึ่งก็ยังไม่เกิน 64 แต่ไม่มีเหตุให้เปลือง คะแนนสูงสุดที่เป็นไปได้คือ 2,000 ข้อคูณค่าข้อละไม่ถึง 2,000 ราวสี่ล้าน ใส่ int ได้สบาย ผมใช้ long long ไว้เผื่อเฉย ๆ

ดูตัวตรวจที่ใช้เทียบ
brute_poi.cpp 
// ตัวตรวจ คิดทุกอย่างจากนิยามตรง ๆ ไม่นับค่าข้อไว้ล่วงหน้า และเรียงทั้งตารางจริง
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, t, p;
    if(scanf("%d %d %d", &n, &t, &p) != 3) return 0;
    vector<vector<int>> a(n, vector<int>(t));
    for(auto &row : a) for(int &x : row) scanf("%d", &x);
    vector<long long> score(n, 0);
    vector<int> solved(n, 0);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < t; j++) if(a[i][j]){
            solved[i]++;
            // นับคนที่ทำข้อนี้ไม่ได้ใหม่ทุกครั้ง ช้าแต่ตรงตามนิยาม
            for(int k = 0; k < n; k++) if(!a[k][j]) score[i]++;
        }
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    // เรียงทั้งตาราง คะแนนมากก่อน ทำได้มากข้อก่อน เลขประจำตัวน้อยก่อน
    sort(order.begin(), order.end(), [&](int x, int y){
        return make_tuple(-score[x], -solved[x], x) < make_tuple(-score[y], -solved[y], y);
    });
    int rank = int(find(order.begin(), order.end(), p - 1) - order.begin()) + 1;
    printf("%lld %d\n", score[p - 1], rank);
}

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

ท่าที่ลืมกติกาตอนเสมอ ผ่านตัวอย่างแต่ผิด
poi_wrong.cpp (ท่อนที่ต่าง) 
int me = p - 1, ahead = 0;
for(int i = 0; i < n; i++)
    if(score[i] > score[me]) ahead++;   // ผิดตรงนี้ ลืมกติกาตัดสินตอนคะแนนเสมอ
printf("%lld %d\n", score[me], ahead + 1);

ท่านี้คิดคะแนนถูกทุกอย่าง แค่ตอนหาอันดับนับเฉพาะคนที่คะแนนมากกว่า ผมคอมไพล์ลองแล้ว มันตอบตัวอย่างในโจทย์ได้ถูก เพราะคนที่เสมอ Philip ในตัวอย่างนั้น (คนที่ 4, 5) บังเอิญมีเลขประจำตัวมากกว่าเขาทุกคน จึงอยู่ใต้เขาอยู่แล้ว

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

EXAMPLE
Inputคำตอบจริงท่าที่ผิดตอบ
2 1 2
0
0
 0 2 0 1

เวลาที่วัดได้บนเครื่องผม ตาราง 2,000 x 2,000 ที่สุ่มเลข 1 ครึ่งหนึ่ง ใช้ 0.69 วินาที และตารางที่ทุกคนทำได้ทุกข้อ (ทุกคนได้ศูนย์ อันดับตัดสินด้วยเลขประจำตัวล้วน) ใช้ 0.68 วินาที จากลิมิต 2 วินาที เวลาเกือบทั้งหมดคือการอ่านเลขสี่ล้านตัวด้วย scanf ส่วนการคิดจริงแทบไม่กินเวลา

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

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

บิลค่าใช้จ่าย
ทางงานคร่าว ๆ ที่ N = T = 2,000สูตร
ทุกช่องที่ทำได้ นับคนที่ทำข้อนั้นไม่ได้ใหม่8,000,000,000N x T x N
นับค่าของทุกข้อก่อน แล้วค่อยรวมคะแนน8,000,000สองรอบ รอบละ N x T
หาอันดับด้วยการเรียงทุกคนราว 22,000N x log N การเทียบ
หาอันดับด้วยการนับคนที่อยู่เหนือ Philip1,999N - 1 การเทียบ
สองแถวบนนับการแตะช่องในตาราง สองแถวล่างนับการเทียบคนสองคน ส่วนที่แพงจริงของข้อนี้คือการคิดคะแนน การหาอันดับจะเลือกทางไหนก็เร็วพอ

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

อ่านทั้งตาราง นับเลข 0 ในแต่ละแนวตั้งเป็นค่าของข้อ รวมคะแนนอีกรอบ แล้วนับคนที่อยู่เหนือ Philip ด้วยการเทียบสามชั้น คะแนน จำนวนข้อ เลขประจำตัว อันดับคือจำนวนนั้นบวกหนึ่ง

แหล่งที่มา

  1. โจทย์ POI บน programming.in.th ข้อ 2033 programming.in.th/tasks/2033 (สืบค้น 11 กันยายน 2026)
  2. ต้นฉบับคือโจทย์ POI วันแรกของ International Olympiad in Informatics ครั้งที่ 21 (IOI 2009, ประเทศบัลแกเรีย) ตามที่ระบุไว้ท้ายโจทย์บน programming.in.th