---
title: 資訊學科能力競賽 心得
date: 2023/11/03
tags:
- C++
- 資訊競賽
- 競程
- 題解
mathjax: true
categories:
- 心得
cover: /img/NHSPC.jpg
---

## 競賽資訊
- 名稱：112 學年度學科能力競賽 複賽 資訊科
- 賽區：國教署負責區第四區（台南）
- 時間：2023/11/2
- 地點：台南女中
- 比賽人數：50 人（資訊科）
- 獲獎人數：1 ~ 5 名進全國賽 再大約取前三分之一的人獲得佳作
- 當天詳細時程：

## 前言
這是我第一次比資訊學科能力競賽 高一時不知道在幹嘛 那時不太關注資訊比賽
南大附中好像也沒什麼人比過資訊能競 所以我跟 @Yudong 不用校內初選就直接進複賽了
南區去年只有選 3 名進全國賽 今年因為去年的南一中有人全國賽一等二等獎 所以新增了 2 個 總共有 5 個名額 ~~賽前猜測沒意外應該都是南一中的~~
我們第一次比賽就遇到主辦方各種出錯 這個留到文章最後再說
此篇文章就是寫我參加此競賽的過程、解題程式碼、心得、和檢討
如果你也是資訊選手或打競程的 那這篇其實可以滑掉不用看了
對你來說可能是一篇廢文 沒什麼參考價值

## 上午場
報到抽籤後 發現只有我們學校沒有領隊...
到了我們學校的座位 被排在最後一排
我跟 Yudong 在猜這座位配置是不是依照學校的得獎次數排的哈哈
我在活動中心其實滿緊張的 雖然前幾個禮拜也有參加比賽：CodeWars、金盾獎 但都是抱持著輕鬆愉快的心情比的
可能是因為這場能競對我來說算是滿重要的比賽 整個狀態有點緊繃
到了電腦教室測試時 主辦就開始出現錯誤了 我先跳過這部分最後再說
來寫一下解題過程

### p1
第 1 題明顯滿難的 我看到就先跳過了

### p2
- 題意

有各不同的分數種類： 50 25 10 5 1 
求總和為 N 分的組合數

- Input

2
11
26

- Output

4
13

- 解題想法

3 層 for 迴圈枚舉每種分數各取幾次
因為取完 前幾種分數 剩餘的都可以用 1 分來湊
看了數字範圍 確認此做法不會超時後開始寫 Code

- <span style="color:green">AC</span> Code

#include <bits/stdc++.h>
using namespace std;
#define ShiYu ios::sync_with_stdio(0),cin.tie(0)
#define FOR(i,n) for(int i=0; i<=n; ++i)

signed main(void)
{
    ShiYu;
    int t; cin >> t;
    int n;
    while(t--)
    {
        cin >> n;
        int ans = 0;
        FOR(i, n / 50)
        {
            FOR(j, (n - i*50) / 25)
            {
                FOR(k, (n - i*50 - j*25) / 10)
                {
                    ans += (n - i*50 - j*25 - k*10) / 5 + 1;
                }
            }
        }
        cout << ans << "\n";
    }
}

### p3 疊蛋餅

- 題意

要疊 n 層圓形蛋餅 最底層的蛋餅半徑是 1
每層的半徑都不能比下面整疊的最大半徑多出 1 以上
求有幾種可能

- 解題想法

一開始就先寫出 1 2 3 4 層的可能性
我用樹狀圖來畫出每層的可能性 然後試著尋找規律
後來觀察出會有重複計算的地方
但就算這樣我還是不知道該如何用程式去計算出所有可能
因為有會重複計算到的數值 所以不能用暴力枚舉的方法 我猜應該是用動態規劃 DP 把算完的東西記下來 不過在賽中我沒有解出來
後來跟新化高中的 Eason 與 Silv 討論
他們也覺得這題很難讀懂題目意思

### p4 最大矩形面積
- 題意

給一張大小為 n x m 且由 0 與 1 所組成的二維陣列
1 是有種樹, 0 是沒樹
求沒種樹的最大面積

- Input

6 7
0010100
0100001
1010000
1100001
0010001
0110101

- Output

12

顯然是找出中間這塊算出面積就好
我在賽中不知道該如何用程式實作出來
聽 Silv 說這是 CSES 的經典題 用**二維前綴和**就能解出來了
但我學會的沒有很多而且練習的題目太少了 不知道能這樣做

### p5
- 題意

有人把一條方程式中的 + 與 * 寫反了
所以給整數 a
求有幾組整數 b , c 
能滿足 a + (b * c) = a * (b + c)
若有無限解 則輸出 -1

- 解題想法
一看就是個數學題
我把式子移項後變成 b * c = a * (b + c -1)
腦中馬上想到了算幾不等式 $\frac{a+b}{2} \ge \sqrt{ab}$ 感覺解法會往這個方向走
但因為題目說可能會有無限解 所以我在賽中想不到如何判斷是否有無限解的方法就沒解出來了

### p6 p7
不在我能力範圍內 跳過

### p8
- 題意

給 n 個整數
若選擇了第 i 個整數 
則 i+1 與 i-1 （前後兩數）都不能選
求最大總和

- 解題想法
我原本用 Greedy 來做 每次都選最大的數字
後來發現如果第 i 個數字最大 我選了 i
但前後兩數加起來比 i 大我卻不能選 這樣就不是最大總和了
所以這題要用 DP 來做 聽說 CSES 也有這種題目
我真的練太紹題目了 連這種簡單經典題都寫不出來

### p9

- 題意

有 n 人要分組
給 i = 0 ~ n-1
ai 為 i 的組員
求每組成員及組數

- Input

6
2 4 3 5 1 0

把輸入做成表格

| 人的編號 | 0 | 1 | 2 | 3 | 4 | 5 |
|:--------------:| --- | --- | --- | --- | --- | --- |
| 他的組員的編號 | 2 | 4 | 3 | 5 | 1 | 0 |

- Output

0 2 3 5
1 4
2

把輸出做成表格
| 組別 | 組員 |
| ------ | ------- |
| 第一組 | 0 2 3 5 |
| 第二組 | 1 4 |

- 解題想法
~~來自 SCIST 總召 Fishhh 的梗~~

- <span style="color:green">AC</span> Code

#include <bits/stdc++.h>
using namespace std;
#define ShiYu ios::sync_with_stdio(0),cin.tie(0)
#define FOR(i,n) for(int i=0; i<n; ++i)

signed main(void)
{
    ShiYu;
    int n; cin >> n;
    int a[n]; FOR(i,n) cin >> a[i];
    vector<vector<int> > v;
    FOR(i,n)
    {
        if(a[i] == -1) continue;
        vector<int> t;
        t.push_back(i);
        int next = a[i], b = i;
        while(a[next] != -1)
        {
            t.push_back(next);
            a[b] = -1;
            b = next;
            next = a[next];
        }
        a[b] = -1;
        v.push_back(t);   
    }
    FOR(i,v.size())
    {
        FOR(j,v[i].size())
        {
            cout << v[i][j] << " ";
        }
        cout << "\n";
    }
    cout << v.size() << "\n";
}

---

## 下午場 2 小時 <span style="color:green">2</span> / 6

### p1
- 題意

每天有 10 小時可以用
給很多組活動的 起始時間 與 結束時間
求如何安排才能在 10 小時中舉辦最多活動

這題感覺很簡單不過一樣的我也沒有寫過類似的題目所以跳過
後來聽 Silv 說只要過濾較多時間的活動
然後依結束時間排序活動 再依開始時間挑選活動就可以了

### p2
我把下午的比賽時間都砸在這題上了

- 題意

給 n 間糖果店
每間不同的店花 1 塊錢可以買到不同的 a 顆糖果
且每間店都會額外贈送 b 顆糖果
有 q 筆操作
分為兩類
1. 把第 x 間店 移動到 第 y 個位置
2. 詢問在 L 與 R 間店中 可以選擇「一間」買糖果 有 x 塊錢可以買 求糖果最大值

- Input

5
2 2
4 5
1 3
3 6
1 7
3
2 2 3 3
1 2 4
2 2 3 3

- Output

17
15

- <span style="color:green">AC</span> Code

#include <bits/stdc++.h>
using namespace std;
#define ShiYu ios::sync_with_stdio(0),cin.tie(0)
#define FOR(i,n) for(int i=0; i<n; ++i)
#define vpii vector<pair<int,int> >

signed main(void)
{
    ShiYu;
    int n; cin >> n;
    vpii v;
    int a,b;
    while(n--)
    {
        cin >> a >> b;
        v.push_back(make_pair(a,b));
    }
    int q; cin >> q;
    int t;
    while(q--)
    {
        cin >> t;
        if(t == 1)
        {
            int x, y; cin >> x >> y;
            vpii vt;
            pair<int,int> p;
            FOR(i,v.size())
            {
                if(i + 1 == x)
                {
                    p = v[i];
                    continue;
                }
                else if(i == y)
                {
                    vt.push_back(p);
                }
                vt.push_back(v[i]);
            }
            v = vt;
        }
        else if(t == 2)
        {
            int l, r, x; cin >> l >> r >> x;
            int maxn = -1;
            for(int i=l-1; i<r; ++i)
            {
                int sum = v[i].first * x + v[i].second;
                if(sum > maxn) maxn = sum;
            }
            cout << maxn << "\n";
        }
    }
}

一開始以為第 1 種操作是交換兩間店的位置
後來才知道是把第 x 間店抽掉後 插入到 第 y 個位置 其餘的順延補上
但寫完還是錯 因為後來這題題目在賽中被主辦方改過題目意思
害我原本照著原題目意思寫的程式碼都要改掉
上面的版本是已經重新寫過而且在最後幾分鐘通過的
原版意思是可以去「任何」糖果店買糖果 後來才改成只能去「一間」買
這個題目意思改動浪費了我超級多時間修改程式碼＝＝
原版程式碼多用了 bool 記錄每間糖果店有沒有去買過
因為我太笨了不太會用 tuple
所以用了很毒的 `vector< pair< pair<int,int>,bool > >`
也判斷了每塊硬幣要去哪間糖果店買才會得到最多糖果
寫完比上面的程式碼還要多了整整 20 行
原版 Code：

#include <bits/stdc++.h>
using namespace std;
#define ShiYu ios::sync_with_stdio(0),cin.tie(0)
#define FOR(i,n) for(int i=0; i<n; ++i)
#define  

signed main(void)
{
    ShiYu;
    int n; cin >> n;
    vector<pair<pair<int,int>,bool> > v;
    int a,b;
    while(n--)
    {
        cin >> a >> b;
        v.push_back(make_pair(make_pair(a,b),true));
    }
    int q; cin >> q;
    int t;
    while(q--)
    {
        cin >> t;
        if(t == 1)
        {
            int x, y; cin >> x >> y;
            vector<pair<pair<int,int>,bool> > vt;
            pair<pair<int,int>,bool> p;
            FOR(i,v.size())
            {
                if(i + 1 == x)
                {
                    p = v[i];
                    continue;
                }
                else if(i == y)
                {
                    vt.push_back(p);
                }
                vt.push_back(v[i]);
            }
            v = vt;
        }
        else if(t == 2)
        {
            int l, r, x; cin >> l >> r >> x;
            int maxn = -1,now=-1,sum = 0;
            while(x--)
            {
                for(int i=l-1; i<r; ++i)
                {
                    if(v[i].second == true)
                    {
                        if(v[i].first.first + v[i].first.second > maxn)
                        {
                            maxn = v[i].first.first + v[i].first.second;
                            now = i;
                        }
                    }
                    else if(v[i].second == false)
                    {
                        if(v[i].first.first > maxn)
                        {
                            maxn = v[i].first.first;
                            now = i;
                        }
                    }
                }
                sum += maxn;
                v[now].second = false;
            }
            cout << sum << "\n";
        }
    }
}

### p3 ~ p5
由於花太多時間在 p2 了 根本來不及想這 3 題要怎麼做

### p6

- 題意
~~這題題目超長 花了一整頁的文字在介紹 2 進制如何進位 根本素養題 所以我直接濃縮成兩句話~~

給 a b 兩正整數
求相乘後的 2 進制與 10 進制

- Input

31
26

- Output

1100100110
806

- 解題想法

先直接 a * b 求 10 進位後用字串的方法換成 2 進位
這題 Eason 用位元左移右移來做 但我太笨了不會那種方法

#include <bits/stdc++.h>
using namespace std;
#define ShiYu ios::sync_with_stdio(0),cin.tie(0)
#define FOR(i,n) for(int i=0; i<n; ++i)

signed main(void)
{
    ShiYu;
    int a, b; cin >> a >> b;
    int n = a * b, t = n;
    string s = "";
    while(t != 0)
    {
        if(t % 2) s = "1" + s;
        else s = "0" + s;
        t /= 2;
    }
    cout << s << "\n" << n << "\n";
}

---

這裡詳細講一下主辦方這次競賽發生的一堆錯誤(抱怨區 可跳過)
1. 賽前測試沒有把系統用好 導致大家上傳測試題的程式碼時都發生 SE（系統錯誤）主辦卻說這不影響正式比賽 延誤了很久才開始
2. 正式開始之後 評測系統又掛掉了 大家都沒辦法登進去提交程式碼 於是主辦就開始做起超荒謬的事：人工評測 我當下是超級傻眼 ~~都 2023 年了還在人工 Judge~~
3. 人工評測只是叫你執行程式然後輸入範例測資看有沒有跟範例輸出一樣 然後簡單看了一下程式碼就直接算你通過 我認為這喪失了公平性因為人工評測是直接用範例測資來看輸出是否正確 但正常比賽用的線上評測是由很多筆測試資料測試你的程式碼是否通過 如果用人工評測範例測資輸出正確 但程式碼錯誤 卻沒被檢查到呢？
4. 在系統正常後 我提交了剛剛人工評測通過的題目程式碼看看是否在評測平台也能通過 雖然成功通過 但主辦方過了一陣子才出來說：人工評測通過的人不用傳線上評測 又說上傳的話會影響原本人工評測時紀錄的時間 我都已經在平台正常的那刻上傳通過了之後才說不用傳＝＝ 而且重點是不傳怎麼知道程式碼通過或不通過？那如果有人人工評測正確但程式碼錯誤卻又不用上傳線上評測 是不是就多賺別人一題？
5. 主辦出題感覺真的很不用心 不知道有沒有認真審題 題目很多數字都沒給範圍 然後很多題都需要在賽中出來大聲講解補充題目意思 很多題都是在比賽時改了又改 還有重新拿一張題目給我們的 一堆題目連範例側資都是錯的 還叫我們整個打叉不要看 然後我都已經照著原版題目意思寫完程式碼了 才出來把題目意思改掉讓我重新修改程式碼

---

## 心得+檢討

這次比賽總共 15 題 我只解出 4 題
有很多都是出自 CSES 的簡單經典題
而我卻因為練太少題目 都想不出解法
這場比賽集結了很多電神 整個比賽會場都充滿著高壓電
全場最強第一名的自學生趙翊佑（聽說是陳水扁的孫子）
還有前幾名有進全國賽的郭育愷、葉智揚、陳秉宏、鄭柏軒 都南一中的 還有一個沒聽過
還有因為 SCIST 而認識新化高中的 Eason 跟 Silv 他們都有得佳作
我看到些人就會覺得我自己超級弱
我本身實力與其他選手相比實在差太多了
最後雖然跟 silv 一樣都是解出 4 題 但他有佳作我卻沒有
我認為可能真的是被主辦方說的上傳線上評測的時間影響到成績
或是他有解到第一題會多一分 或是我最後花的時間確實比較多
心裡其實滿沮喪的 一直在想為什麼會這樣 也一直很想抱怨主辦方
但又覺得我實力比不上別人 好像也沒什麼資格抱怨的
總而言之 見識到有那麼多人都比我更厲害而且比我更努力
我覺得讓我想向他們學習 我會多多練題 持續精進自己

---

## 11/3 更新 我得佳作了？！
廢話不多說 直接附上得獎名單
明明現場沒喊到我的名字
今天公布的得獎名單裡佳作竟然有我？？？
心中滿滿問號與懷疑
不過後來猜測是因為主辦方重新整理過分數與解題時間
調整了名次 讓我成功獲得佳作
心情慢慢轉變為喜悅
我把這次的成績視為對自己的一種肯定
作為我之後的動力

高二的一堆比賽 讓我心裡也不知道該怎麼平衡課業與競賽
一直在擔心如果把時間花在比賽 卻沒有比出成績的話怎麼辦
我的段考分數也因為社團與競賽 相比高一真的變差太多了
身邊的同學也一直在問為什麼我成績變得不好
但我真的無法解釋 只能做好我該做的事 做我想做的事
希望我能漸漸學會如何分配我自己的時間 慢慢調整課業與競賽的比重
我相信我能越來越好的

## 特別感謝
Yudong 每次比賽的搭檔 沒有你我也不會有佳作 感謝你常常陪我打線上程式競賽到半夜 每天討論程式題目怎麼解 讓我們一起進步 雖然這次你比賽你打的不太理想 不過我相信你的實力是有的 不要太在意 明年我們再拼一次 最後也謝謝賽前給我加油打氣的老師與同學朋友們

## 延伸閱讀
[Yudong 的心得](https://hackmd.io/@YuDong/NHSPC112)
[台南一中 葉智揚 競賽心得](https://hackmd.io/@tw20000807/2023south_contest)

---

# [點擊回到導覽頁面](https://shiyu0318.github.io/post/Sitemap/)

---