# 2024 ISSC 心得

## 關於ISSC
**開學隔一天，諧咖日期**
**辦在中原大學，諧咖地點**
**題目全英文，諧咖題目**

## 關於報名
### 隊員
**Paul不知道為啥總是能在資訊活動剛出來的時候就知道了**
**所以他看到ISSC就來揪我去打團體賽**
**那時候我想說8/31有點急(因為要趕開學考)，但因為是團體賽~~可以抱Paul的大腿~~ + 想多點ICPC制的經驗，所以就答應了下來**
**一隊的人數是3人，另一個人我們本來想說揪tw87~~這樣我就可以完全躺分了~~**
**但tw87覺得桃園太遠所以不想去...，然後我們就跑去揪CharHao**

### 指導老師
**解決了隊員問題後要解決指導老師的問題**
**聽說這個比賽很諧咖，所以我們打算讓tw87當我們的指導老師XD**
**而且tw87也有答應，只是報名限制要填身分證+需要在學校教書的老師資格**
**所以最後還是去找SA (聽說SA秒回，好感動)**

### BONUS
:::spoiler **從報名就很諧咖 : 報名簡章...**
:::

## 準備
### 刷題
**本來想說刷一下ISSC考古題，但ISSC連官網都沒有...**

### 參考經驗
**去網路上找到了 [Ststone的2022ISSC心得](https://ststone1687.github.io/2023/01/05/contest/issc2022/)**
**看到一大堆大佬、becaido都有去打了，期望值++**

### 交通
**因為在桃園，所以想說搭高鐵過去然後鬼轉計程車去中原大學 <font color = "red">這裡很重要，等等會講</font>**
**然後學校交通補助不能補高鐵全票價QQ**

### 心理建設
**相信主辦單位會一年辦得比一年還要好!**

## 比賽當天
### 從台南出發
**早上4.多起床，整個人昏昏沉沉好想睡覺**
**去到高鐵跟paul、charhao碰面就上高鐵了**
**因為我們是各自買票，所以都在不同車廂**
**我在車上閒的無聊所以看了一下資讀開學考的contest，結果發現時間調錯，提早開始了...**
**然後我就慌慌張張的把時間調回來 (早起的鳥兒有BUG修)**

### 到達桃園
**下了高鐵才7.20左右，最晚需要9.20到，所以我們就把計程車這個東西reject掉了**
**看到旁邊有UBIKE，恩...那就騎過去吧!**

### 自行車旅程
**一開始感覺還挺好的，有種大學生活騎腳踏車去大學上課個感覺**
**但越騎越奇怪，整個地方超偏僻，然後樓房開始變矮，蟲鳴鳥叫聲逐漸變大聲**
**...根本來到鄉村，感覺好像還在台南一樣...**

**然後路超窄，我又很久都沒騎自行車了**
**有汽車經過我都很怕我直接被頂一下掉下去旁邊的農田水溝...**

**騎了很久、很累，終於看到了城市的跡象**
**然後也看到了自行車步道XD，那時候真的感覺我們是來比自行車比賽的**

**附上一張自行車旅行的 charhao**

**騎在大馬路上也很危險，paul差點被公車撞到XD**

### 到了中原大學
**charhao : "我一定要考台大"**
**me : "中原大學狗都不讀..."**

**因為中原大學根本太難到了...**
**騎超久，然後學校大門口那邊還很窄...**

**全身都是汗，很想要買一件中原T，但沒有(中原aura-999999)**

### 早上
**到了中原大學後，在路上遇到了國手隊(mocha、leolin 1! + 2! orz)**
**然後聽到他們搭計程車過來... (極度羨慕)**

**上去了7樓，簽到 and 領牌子**
**發現也有SA的名牌XD**
**之後就下去4樓休息室等著了**
**BTW 那個電梯看起來就很中原，超怕他抖一下我們整間電梯直接掉進去backroom**

**進去休息室看到了一大堆大佬，chung、winlu、cheng 那些ionc的大佬也有來打**

### 在現場的賽前準備
**看到一大堆隊伍不是在用筆電就是在玩遊戲，哼哼 我們根本贏爛 (我跟charhao開始翻字典...**

### 測機賽
**諧咖的開始**

**總共五題**

**pA**
:::success
**給一數列 $1, 2, \ldots , N-1$ 求有多少區間和為 $N$**
**$N \le 10^6$ 、 several testcases**
**timelimit : 2 sec**
:::
:::warning
**看起來很明顯就是直接前綴和做一做**
**那時候我還在思考複雜度 + 被several testcases搞到**
**他沒講多少筆，所以根本很難估複雜度...**
:::

**pB**
:::success
**給二數 $N$ $K$ 求一長度為 $N$ 的數列 其中有 $K$ 個逆敘數對**
**且此數列需為最小字典序**
:::
:::warning
**大概類似排列組合的解法**
**像是問一數列由 $A$ $B$ $C$ 三個字元組成**
**求 $B$ $A$ $C$ 在裡面是第幾個 的那種題目**
**所以應該是用 DP 下去做**
**實作太麻煩了，Paul教授解的orz**
:::

**pC**
:::success
**給一數列 $A$ ，求此數列是否符合一性質**
**性質 : $A_i \le A_{\lfloor i/2 \rfloor}$ $i$ 為 1-based**
**several testcases**
**範測(隨便打的 意思有到就行):**

1 2 3
5 6 2 34
1 3 0 9 3

:::
:::warning
**看起來就直接做過去就行**
**但麻煩的點是: 他沒給你整個數列的長度**
**所以我直接用stringstream下去做**
**然後就拿這題的首殺了 yeah**
:::

**pD**
:::success
**給測資數 $T$**
**給一序列(僅包含ATGC)**
**求此序列中最長最早不重複子字串的頭index**
**範測(隨便打的 意思有到就行):**

3
ATGCATGC
AAAAAAA
ATGGCAT

**輸出:**

1
1
4

:::
:::warning
**這題是paul教授寫的**
**大概就暴力解過去**
**然後這題主辦單位測資爛掉，所以大家都一直吃WA**
:::

**pE**
:::success
**給測資數**
**給二長方形(p1、p2)左上右下二頂點**
**求二長方形是否會重疊**
**假如會再輸出 :**
**求p1的四頂點在p2(包含邊上)的數量**
**求p2的四頂點在p1(包含邊上)的數量**
:::
:::warning
**反正讀題目很花時間 + 我不太想做**
**所以就丟給charhao寫**
**大概概念就直接8個if砸下去就行了**
:::

**因為測機題目很少又蠻簡單的，所以好像有很多對破台**

### 中午休息
**測機賽破台之後要先出考場**
**考場外面有點心，真心覺得巧克力餅很好吃**
**然後回到休息室就看到mocha他們在玩陀螺遊戲，你們還揪了狼人殺**

**然後之後就跑去領便當**
**主辦單位說便當都一樣，結果我拿到鰻魚，paul charhao都拿到爌肉飯，諧咖**

**吃飽飯後我們就決定要上去點心區那裡拿咖啡包下來泡**
**結果我們拿了之後去旁邊的飲水機**
**我們一直在怪中原的飲水機太破，結果最後發現原來是我們沒有把咖啡包撕開...**
**原來以為是中原大學的咖啡包爛，原來是我們沒看包裝說明XD**

### 正式賽
**總共有15題，超級多**

**以下題目我沒有讀完，所以講一下大概而已**

**pA**
:::success
**我一開始看測資覺得是找1的連通塊，但仔細看卻發現好像不對**

3 4
1 0 0 1
1 0 0 0 
0 1 1 1

2

**聽paul說就是連通塊，但是是找0的連通塊...**
:::

**pB**
:::success
**dp題目**
**給你二數 $N$ $K$**
**求長度為 $N$ 的數列中，逆序數對為 $K$ 的數列有幾種**
:::
:::warning
**看起來就排組的料+DP**
**所以後面就丟給paul解了**
**他最後也解出來了 orz**
:::

**pC**
:::success
**給 $N$ 個點，然後每個點的 $X$ 、 $Y$ 軸將會被切割**
**到最後會切割出很多個長方形**
**求最大最小面積的長方形以及數量**
**大概長這樣**
:::
:::warning
**題目很難看懂，但看懂後就很好做了**
**直接暴力求 $X$ 、 $Y$ 軸的最大長度跟最小長度還有數量就行**
:::

**pD**
:::success
**聽paul說是水題，然後他就AC了...**
:::

**pE**
:::success
**約瑟夫問題**
**但是改成平民、騎士、欺騙者(?)**
**平民不能做事**
**騎士會殺死下一個人**
**欺騙者會殺死上一個人**
**保證最後一定會剩下來一個人**
:::
:::warning
**tuple綁很多個訊息，然後list模擬解**
**但是要將平民縮點，不然會吃TLE**
**(只是我真的不知道要怎麼證明縮點後複雜度就是好的...)**
:::

**pF**
:::success
**英文題，我跟charhao都看不懂題目，輸光**
:::
:::warning
**最後聽國手隊說是SCC，輸光**
:::

**pG**
:::success
**忘記了**
:::

**pH**
:::success
**給 $N$ 個人，再給你鄰接矩陣代表著與另外一個人是否認識**
**求最多可以多少個人組一團，至少有兩個人互相不認識**
:::
:::warning
**聽charhao跟paul都說是折半枚舉，但我根本不會**
:::

**pI**
:::success
**賽局題**
:::
:::warning
**因為這題只要輸出YES 跟 NO**
**所以第一名直接砸69次random 直接AC**
:::

**pJ**
:::success
**給二陣列 $A$ $B$，且此二陣列都是遞增數列**
**有一陣列 $C$ 滿足 $C_{i, j} = A_{i} + B_{j}$**
**求此數($A$的中位數 + $B$的中位數) 在陣列 $C$ 中的排名**
:::
:::warning
**latex消失術，讀題目很痛苦，看不到數學公式**
**然後她的陣列大小也消失，我直接痛苦面具**
**最後還是paul說 : 這題雙指針**
**然後他就AC了orz**
**~~我刻了BIT被卡log，超不爽ㄟ~~**
:::

**pK**
:::success
**paul寫的，輸光**
:::

**pL**
:::success
**latex消失術2.0**
**題目根本沒人看得懂**
:::

**pM**
:::success
**寫了很多英文，看不懂...**
:::
:::warning
**但題目底下的hint說 $\lceil log_2N \rceil$**
**對，這就是答案**
:::
:::danger
**主辦單位忘記把出題者要給驗題者的提示刪掉...**
**到底什麼諧咖比賽**
:::

**pN**
:::success
**聽charhao說是經典區間DP**
:::
:::warning
**一開始我把charhao說的"區間DP"聽成"曲線DP"**
**我整個嚇到，這樣是經典題???**

**然後這題還要用到stringstream，超廢**
:::

**pO**
:::success
**聽說很難，所以沒看**
:::

**封版**

**時間剩下一小時多的時候，mocha有問主辦單位會不會封版**
**然後主辦單位回說: 半小時才封版**
**結果等一個小時後，scoreboard大家的challenging submission直接變成藍色**
**有封跟沒封一樣**
**最後半小時的時候才關掉最後可以看到challenge完的狀態**

**氣球**

**每隊AC一題後就會拿到一顆氣球**
**Paul一直瘋狂AC拿氣球，我在旁邊抱頭痛哭，形成強烈對比...**

### 頒獎
**最後我們拿到了第6名，差在penalty (對不起我在搞...)**

### 回家