สรุปสาระสำคัญ

• มี Array 1 มิติ ค่า $\ge 0$ แทนเป็นจุดสะสมแต้ม เดินผ่านแต้มเพิ่ม (ไม่เกี่ยวกับเงิน) ส่วนค่า $\lt 0$ เป็นร้านค้า เดินผ่านเงินลด
• มี $m$ คำถาม แต่ละคำถามเริ่มที่ตำแหน่ง $x_j$ และมีเงิน $h_j$ จากนั้นเดินต่อไปเรื่อย ๆ จนกว่าเงินจะหมด นั่นคือหากเจอร้านใดแล้วทำให้เงินในกระเป๋าหมด ในที่นี้หากเหลือ 0 ก็ถือว่าหมด ก็จบเกมออกจากตลาดไป
• จะได้แต้มสะสมทั้งหมดรวมเท่าไหร่ นั่นคือผลรวมของแต้มสะสมที่ได้ตั้งแต่ต้นยันออกจากตลาด

หมายเหตุ สำหรับโค้ดด้านล่าง จะมีการละส่วนของการรับค่า $n, m$ และ $a$ ไว้

int n, m;
cin >> n >> m;

for (int i = 0; i < n; i++) {
    cin >> a[i];
}

ปัญหาย่อย 1 (13 คะแนน) $n \le 1\,000$ และ $m \le 1\,000$

เราสามารถทำตรง ๆ ได้เลย หรือก็คือเขียนตรง ๆ ตามที่โจทย์เล่ามา

for (int i = 0; i < m; i++) {
    int x, h;
    cin >> x >> h;

    int points = 0;

    for (int p = x; p < n; p++) {
        if (a[p] < 0) {
            h += a[p];
        } else {
            points += a[p];
        }

        if (h <= 0) break;
    }

    cout << points << "\n";
}

Time Complexity: $\mathcal{O}(nm)$

ปัญหาย่อย 2 (8 คะแนน) ไม่มี $a_i$ ที่ติดลบ

ในปัญหาย่อยนี้ เราสามารถสังเกตได้ว่าหลังจากเข้าตลาดแล้ว จะไม่มีร้านค้าอยู่เลย ดังนั้นเงินเราก็ไม่มีทางหมด จะออกตลาดที่ร้านสุดท้ายเสมอ ดังนั้นสิ่งที่เราต้องหาคือ $\sum_{i=x_j}^{n-1} a_i$ โดยสามารถทำเร็ว ๆ ได้โดยใช้ Quick Sum

qs[n - 1] = a[n - 1];
for (int i = n - 2; i >= 0; i--) {
    qs[i] = a[i] + qs[i + 1];
}

for (int i = 0; i < m; i++) {
    int x, h;
    cin >> x >> h;

    cout << qs[x] << "\n";
}

Time Complexity: $\mathcal{O}(n+m)$

ปัญหาย่อย 3 (21 คะแนน) $h_j = 1$

ใน Subtask นี้สังเกตว่าหากเราเดินไปเจอร้านค้าเมื่อไหร่ ก็คือจบเกมทันที (recap: หากเงินเป็น 0 ก็ถือว่าต้องออกทันทีเช่นกัน ไม่ต้องรอเงินติดลบ)

สิ่งที่เราต้องหาคือ Quick Sum ตั้งแต่ $x_j$ จนถึง $X$ เมื่อ $X$ เป็นร้านค้าร้านแรกที่มีพิกัด $\ge x_j$

สำหรับโค้ดที่จะมาแสดงนี้ใช้วิธี Quick Sum ย้อนกลับโดยจะบวกจากด้านหลัง และรีเซ็ทค่ากลับเป็น $0$ เมื่อเจอร้านค้า $(a_i \lt 0)$ ซึ่งวิธีนี้จะครอบคลุม Subtask 2 ด้วย

qs[n - 1] = max(0, a[n - 1]);
for (int i = n - 2; i >= 0; i--) {
    if (a[i] < 0)
        qs[i] = 0;
    else
        qs[i] = a[i] + qs[i + 1];
}

for (int i = 0; i < m; i++) {
    int x, h;
    cin >> x >> h;

    cout << qs[x] << "\n";
}

Time Complexity: $\mathcal{O}(n+m)$

ปัญหาย่อย 4 (17 คะแนน) $x_j = 0$

เนื่องจาก $x_j = 0$ นั่นหมายถึงจุดเริ่มจะถูก fix ไว้เสมอโดยแต่ละคำถามต่างแค่ค่า $h_j$ ดังนั้นสิ่งที่เราต้องทำคือหาว่าเงิน $h_j$ นี้จะสามารถไปได้ไกลถึงร้านค้าร้านไหน (สมมติเป็น $X$) และเราก็จะตอบค่าผลรวมของแหล่งสะสมแต้มที่ตั้งอยู่ตั้งแต่ $0$ ถึง $X$ $(\sum_{i=x_j}^{X} a_i\ if\ a_i \ge 0\ else\ 0)$ ซึ่งในส่วนแรกจะใช้ Binary Search และในส่วนหลังใช้ Quick Sum

หรือในโค้ดที่จะยกตัวอย่างด้านล่างนี้จะใช้อีกวิธีหนึ่ง โดยจะ Insert Breakpoint เข้าไปใน map ทุกครั้งที่เจอร้านค้าร้านแรก หลังจากเจอร้านสะสมแต้ม

int points = 0;
int costs = 0;
map<int, int> money;
for (int i = 0; i < n; i++) {
    if (i > 0 && a[i] < 0 && a[i - 1] >= 0) {
        money.insert({costs + 1, points});
    }

    if (a[i] >= 0) {
        points += a[i];
    } else {
        costs -= a[i];
    }
}
money.insert({costs + 1, points});

for (int i = 0; i < m; i++) {
    int x, h;
    cin >> x >> h;

    auto ptr = money.upper_bound(h);
    if (ptr == money.begin()) {
        cout << "0\n";
    } else {
        cout << (--ptr)->second << "\n";
    }
}

Time Complexity (ของโค้ดด้านบน): $\mathcal{O}(n\log n+m\log n)$

ปัญหาย่อย 5 (41 คะแนน) ไม่มีข้อกำหนดอื่นใด

เราสามารถต่อยอดจาก Subtask 4 เพื่อนำสู่ General Solution (หรือที่เรียกกันว่า Sol 100) ได้

โดยวิธีทำจะคล้ายกับ Subtask 4 ที่ได้กล่าวไปมาก โดยสรุปจากที่เรา Observe กันมาทั้งหมด 4 ปัญหาย่อย วิธีการที่เราจะแก้โจทย์นี้คือ

• หาว่าเงินหมดที่จุดไหน
• ตอบผลรวมแต้มของแหล่งสะสมแต้มตั้งแต่จุดเริ่ม ยันจุดที่เงินหมด

สำหรับ General Constraint ที่ $x_j$ เป็นอะไรก็ได้ เราก็เพียงแค่บวกเงินของร้านค้าก่อนหน้า (หรือจะใช้วิธีอื่นก็ได้) เพื่อให้ง่ายต่อการหาว่า "เงินจะหมดที่ร้านไหน" แล้วเราก็จะสามารถใช้ Quick Sum แก้ปัญหาส่วนหลังได้

qscost[0] = max(0, -a[0]);
qspoints[0] = max(0, a[0]);
for (int i = 1; i < n; i++) {
    if (a[i] >= 0) {
        qspoints[i] = qspoints[i - 1] + a[i];
        qscost[i] = qscost[i - 1];
    } else {
        qscost[i] = qscost[i - 1] - a[i];
        qspoints[i] = qspoints[i - 1];
    }
}

for (int i = 0; i < m; i++) {
    int x, h;
    cin >> x >> h;

    h += (x > 0 ? qscost[x - 1] : 0);
    int l = x, r = n - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (qscost[mid] >= h) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    cout << qspoints[l] - (x > 0 ? qspoints[x - 1] : 0) << "\n";
}

Time Complexity: $\mathcal{O}(n+m\log n)$

ฝากเทคนิคสุดท้าย

• สำหรับโจทย์ TOI18 ในปีนี้ แนวโจทย์ได้เปลี่ยนไปทาง IOI/สสวท นั่นคือเน้นเก็บ Subtask ดังนั้น Strategy ในการทำโจทย์ก็ควรจะเปลี่ยนไปเช่นกัน
• ผมแนะนำว่าหากใครคิด sol 100 ไม่ออก ก็ควรที่จะหันมาเก็บ Subtask สำหรับโจทย์ข้อนี้ การแบ่ง Subtask ในข้อนี้นั้นถือว่าใจดีมาก โดยข้อจำกัดของแต่ละปัญหาย่อย ออกแบบมาเพื่อช่วยชี้นำเรา (ใบ้) ให้คิด sol 100 ออก ในการทำโจทย์ข้อนี้ ตอนแรกผมก็คิด sol 100 ไม่ออก แต่หลังจากเก็บ Subtask ไปเรื่อย ๆ มันช่วยชี้นำผมให้สามารถคิด sol 100 ได้ หรือต่อให้ใครคิดไม่ได้ อย่างน้อยก็มีคะแนนติดตัวไว้บ้าง ดีกว่าพยายามแก้ทีเดียวให้ออกแล้วสุดท้ายก็ได้ 0