2024 ISSC 心得

關於ISSC

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

關於報名

隊員

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

指導老師

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

BONUS

從報名就很諧咖 : 報名簡章…

準備

刷題

本來想說刷一下ISSC考古題，但ISSC連官網都沒有…

參考經驗

去網路上找到了 Ststone的2022ISSC心得
看到一大堆大佬、becaido都有去打了，期望值++

交通

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

心理建設

相信主辦單位會一年辦得比一年還要好!

比賽當天

從台南出發

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

到達桃園

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

自行車旅程

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

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

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

附上一張自行車旅行的 charhao

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

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

到了中原大學

charhao : "我一定要考台大"
me : "中原大學狗都不讀…"

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

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

早上

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

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

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

在現場的賽前準備

看到一大堆隊伍不是在用筆電就是在玩遊戲，哼哼我們根本贏爛 (我跟charhao開始翻字典…

測機賽

諧咖的開始

總共五題

給一數列

$1, 2, \dots, N - 1$ 求有多少區間和為
$N$

$N \leq 10^{6}$ 、 several testcases
timelimit : 2 sec

看起來很明顯就是直接前綴和做一做
那時候我還在思考複雜度 + 被several testcases搞到
他沒講多少筆，所以根本很難估複雜度…

給二數

$N$
$K$ 求一長度為
$N$ 的數列其中有
$K$ 個逆敘數對
且此數列需為最小字典序

大概類似排列組合的解法
像是問一數列由

$A$
$B$
$C$ 三個字元組成
求
$B$
$A$
$C$ 在裡面是第幾個的那種題目
所以應該是用 DP 下去做
實作太麻煩了，Paul教授解的orz

給一數列

$A$ ，求此數列是否符合一性質
性質 :
$A_{i} \leq A_{⌊ i / 2 ⌋}$
$i$ 為 1-based
several testcases
範測(隨便打的意思有到就行):

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

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

給測資數

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

3
ATGCATGC
AAAAAAA
ATGGCAT

輸出:

1
1
4

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

給測資數
給二長方形(p1、p2)左上右下二頂點
求二長方形是否會重疊
假如會再輸出 :
求p1的四頂點在p2(包含邊上)的數量
求p2的四頂點在p1(包含邊上)的數量

反正讀題目很花時間 + 我不太想做
所以就丟給charhao寫
大概概念就直接8個if砸下去就行了

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

中午休息

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

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

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

正式賽

總共有15題，超級多

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

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

聽paul說就是連通塊，但是是找0的連通塊…

dp題目
給你二數

$N$
$K$
求長度為
$N$ 的數列中，逆序數對為
$K$ 的數列有幾種

看起來就排組的料+DP
所以後面就丟給paul解了
他最後也解出來了 orz

給

$N$ 個點，然後每個點的
$X$ 、
$Y$ 軸將會被切割
到最後會切割出很多個長方形
求最大最小面積的長方形以及數量

大概長這樣

題目很難看懂，但看懂後就很好做了
直接暴力求

$X$ 、
$Y$ 軸的最大長度跟最小長度還有數量就行

聽paul說是水題，然後他就AC了…

約瑟夫問題
但是改成平民、騎士、欺騙者(?)
平民不能做事
騎士會殺死下一個人
欺騙者會殺死上一個人
保證最後一定會剩下來一個人

tuple綁很多個訊息，然後list模擬解
但是要將平民縮點，不然會吃TLE
(只是我真的不知道要怎麼證明縮點後複雜度就是好的…)

英文題，我跟charhao都看不懂題目，輸光

最後聽國手隊說是SCC，輸光

忘記了

給

$N$ 個人，再給你鄰接矩陣代表著與另外一個人是否認識
求最多可以多少個人組一團，至少有兩個人互相不認識

聽charhao跟paul都說是折半枚舉，但我根本不會

賽局題

因為這題只要輸出YES 跟 NO
所以第一名直接砸69次random 直接AC

給二陣列

$A$
$B$ ，且此二陣列都是遞增數列
有一陣列
$C$ 滿足
$C_{i, j} = A_{i} + B_{j}$
求此數(
$A$ 的中位數 +
$B$ 的中位數) 在陣列
$C$ 中的排名

latex消失術，讀題目很痛苦，看不到數學公式
然後她的陣列大小也消失，我直接痛苦面具
最後還是paul說 : 這題雙指針
然後他就AC了orz
~~我刻了BIT被卡log，超不爽ㄟ~~

paul寫的，輸光

latex消失術2.0
題目根本沒人看得懂

寫了很多英文，看不懂…

但題目底下的hint說

$⌈ l o g_{2} N ⌉$
對，這就是答案

主辦單位忘記把出題者要給驗題者的提示刪掉…
到底什麼諧咖比賽

聽charhao說是經典區間DP

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

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

聽說很難，所以沒看

封版

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

氣球

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

頒獎

最後我們拿到了第6名，差在penalty (對不起我在搞…)