2017年2月12日 星期日

農場例行賽 #23.5

為什麼會有這場奇怪的比賽出現呢?主因是 tmt514 和 drazil 在出題目時,常常會不小心舉出一些太偏離普通的演算法競賽或有些刁難的題目,於是我就想說,就辦一場讓大家隨心所欲、不限至題目類型的比賽吧~雖然最終看來...這些題目大部分還算是普通的 = =,大家還是很克制的沒有出真的非常奇怪的題目 (drazil 之前跟我舉了好多他想出的題目,但最後都自己否決掉了 XD)

這場由我生的題目有 B、C、F,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