這場由我生的題目有 B、Ｃ、Ｆ，A 和 E 是 drazil 出的， D 是 tmt514 出的。
我這裡就稍微解釋一下我出的題目大致上的獲得 AC 流程和對這些題目的看法，就不附上程式碼了。
Problem B - Everyone look forward to high rating user
會想到出這題是因為... 就如題目敘述所說的，我還蠻喜歡看這些關於厲害的人的表現數據的，但是我過去又很懶得研究 API 之類的東西，所以就沒有什麼動力寫程式碼列出我想知道的事情。
但最近工作後，其實每天做的事大概就是解這題所需要做的事情吧 = =，一直查一直查 tools 怎麼用，實際思考程式結構的時間挺少的。於是漸漸地對查 tool 怎麼用這件事麻痺了吧？把這提出成題目也不會給自己太大壓力，是個輕鬆三個小時左右就可以生完的題目。
先附上 Codeforces API 的連結。先聲明，我並不釋出完題目就知道用哪個 method 的，出題前我還不知道那些 method 怎麼用 = =，但至少... 這題要做的事用想的就覺得不太難，API 如果不能輕鬆得到結果的話，那這個 API 也太沒用了吧 0.0
我簡單地用 Python 試了幾個 method，最後決定使用 contest.ratingChanges 這個 method 來獲得 rating 資訊，因為我只要獲得每場比賽所有人的 rating change，就可以獲得這題所想要的結果了，而且只需要不到 $1000$ 個詢問，若你真的每個 Codeforces user 都詢問的話，由於它限制一個 ip 每秒中最多能詢問 $5$ 次，可能跑一天還跑不完吧 XD (不過我這樣寫可能還是要跑個十幾分鐘吧 )
使用了此 API 後，我就先把他丟給我的 JSON 檔案丟到 online json visualizer，例如 這個，於是我就可以快速地了解他的 json 結構，找到我想要的資料的位置，於是我就寫了一個能印出所有滿足 newRating > 2765的 (user, newRating) pair，之後再用 c++ 處理這些資料，把答案寫死在 code 裡，這題就大功告成了！
順帶一提，據說賽內唯一一個 AC 的人是肉眼一個一個看排名前面的人的 rating 的 ... 所以說我這題目並設計得不好，讓人還有機會不藉由 API 就在塞內獲得 AC... 應該要使用排名在一千左右的人當主角...。
P.S 可能還是有人想知道我 api 是怎麼使用的，我還是貼一下我的程式碼好了，但我對 python 真的完全不懂 >_<，相信熟悉 python 的人一定能有更輕省的寫法
Problem C - It's a hard problem that I believe you can't solve by yourself
這題則是標準的 OEIS 題，標題都說地那麼明白了，並不期望大家在三小時內寫出來啦... 若這種題目有那麼多人能在三小時內解出來，那麼那些研究這個問題的 paper 大概沒什麼太大的價值吧 XD
雖然這題是 OEIS 題，但也不是最簡單地把前三個數放進去就能找到答案的 OEIS 題。首先，你會注意到，第 $n$ 個數一定是 $n!$ 的倍數，所以我們就可以把它除以 $n!$，若你把前三項經過這樣的處理，或許就有機會找到答案了～但可惜的是，在我寫這篇 blog 的時候，輸入前三個數將獲得高達 $324$ 項結果，你要一個一個檢查是不是你想要的序列，可能比 Problem B 人眼搜索 Rating 前 $80$ 高的人還難吧 XD。
接下來要做的事應該已經呼之欲出了，寫個簡單的爆搜程式搜索出第四個數，就可以在 OEIS 上找到唯一的序列，剛好也就是這題的答案～ OEIS 上也有附了一個簡單明瞭的公式，使用它就能 AC 了。
若有興趣想深入研究這個問題，請自行翻閱 OEIS 附的 reference 吧。
最後提一下，為什麼我會選擇這個序列呢？這個問題其實是我當兵期間研究的眾多問題之一。有時睡不著就會亂想題目，有天開開心心地再這個問題上獲得了一個 $O(N^2)$ 的解，想要之後出在比賽上，但當時並沒有把解法記下來。直到退伍後才認真把 code 寫出來，但這時我只能做到 O(N^3)，已經想不起來在軍中時 O(N^2) 的作法到底是什麼，抑或是根本當時就想錯了？但最後我還是把它當它寫成題目的 proposal 投稿到 SRM，結果卻被 cgy4ever 發現其實 OEIS 有這個序列！而且還有好多論文在研究這個問題！知道後整個崩饋 T_T 最後這題就不了了之啦～
最後的最後再提一下， 賽中唯一 AC 的人並不是靠 OEIS，而是 google 了關鍵字:"number of partitions with k-intersection matchings" 而找到相關論文的。
Problem F - This is a sign-in Problem!
這題就如同標題所說的，是個簽到題
近來我們發現，若最簡單的題目不夠簡單，我們無法準確地獲得有參加比賽的人數，所以比進行間多放一題簽到題。並且我們因為簽到題多捕獲了 3 個有讀題的人！謝謝大家的餐與 m(_ _)m
沒有留言:
張貼留言