2015年4月1日 星期三

比賽debug側記---把自己的思緒說給別人聽的好處

這篇也是紀錄有關某場比賽的事,不過只特別記錄其中一件插曲。

應該有不少人都聽過黃色小鴨除錯法吧?我個人相信這招對 debug 真的很有用,由其是在正式比賽中心浮氣躁的情況下用這招效果更是顯著 (把隊友當成黃色小鴨之類的),常參加團隊比賽的人或許多少都有這種經驗:當自己debug許久但都找不到bug,於是就要把自己的作法說給隊友聽,請隊友幫忙debug,但說著說著忽然自己就發現 bug 了!這個時候,其實你的隊友的地位就和黃色小鴨一樣而已XD畢竟他什麼都還沒做,只是在用耳朵聽你說。

3/29(日) 受人邀請組隊參加了 UTPC,是個主要給日本人參加的比賽(題目都用日語),不過藉由翻譯功能,多少還是能看得懂題目,並且真的讀不懂的地方可以向日本人的隊友確認。

但這場比賽我的表現實在欠佳,不知是太久沒比團隊比賽還是對第一次組的隊伍不習慣,總之這場我只寫了兩題 pD,和 pH,不過隊友們很罩就是了,最後還使勉強上了記分版上的第三名,唉唉不過大家看到我們這隊的組成應該還是會覺得比的不夠好吧 XD

這場比賽題目共分成 100 分、200 分、300 分三種,照記分版來看 pD 應該是 200 分以下最麻煩的一題,但實際上難度頂多只有 SRM Div.1 500或Codeforces Div.1 pC 左右吧,這裡就不提他了,我要談的題目是 pH --- 回すだけ,是個互動題。整場比賽我花了將近兩個半小時在上面 ...

題意:平面座標上有一個凸多邊行,其中一個頂點座標是 (0, 0),其他頂點座標你都不知道,你只確定它至多 $10$ 個頂點,每個頂點座標皆為整數,並且所有內角都在 170 度以下。現在你可以問至多 $1000$ 個問題,每個問題都形如下:"把此多邊行繞著原點逆時針轉 $x$ 度後,y座標的最大值是多少?"

互動格式:當要問問題的時候,以一個 '?' 加一個空白作開頭,後面接一個浮點數 $x$ 代表你所問的問題中的 $x$。當要回報答案時,答案有 $n+1$ 行 (n為凸多邊形頂點座標),每行都以 '!' 加一個空白做開頭,第一行僅包含一個數 $n$,第二行之後,由 (0, 0) 開始往逆時針回報所有頂點座標。

這題應該不太難,我想了幾秒就想到一個做法:每一個詢問等於我們可以知道這個凸多邊形在哪個半平面裡,並且我們若以 $1$ 度為間隔詢問 $360$ 次以上,那麼原本的凸多邊形頂點,一定在這$360$ 次詢問所得到的半平面的交集的凸多邊形頂點上。那我們就大膽的相信,求半平面交後的凸多邊形上的所有整數座標頂點搜集起來後,就是答案。

實際上有更精簡的做法,不需要使用半平面交,只需要求線段交點就有辦法得到答案,但這裡就不提了,畢竟我的重點是在於這題的 debug 。

總之這題就解法而言其實相當單純,但麻煩的就是很難測試自己程式碼的正確性,它的 Sample 很不親切,完全就只有格式上的舉例而已,於是我就把我的程式分區塊,用我自己的方法檢驗其正確性,大致上無誤後就 submit 了,但是卻 WA了 ... 我再仔細看了一次題目,發現要輸出 $n$ 但我沒有輸出,但是我改了這個 bug後還是 WA。

接下來我又測了很多東西,但真的完全找不到錯誤,於是我又完全改寫做法,改用不需要半平面交的做法(畢竟半平面交我是直接使用 codebook ,很擔心 codebook 其實是錯的 Orz),但還是 WA 掉了,甚至拿到 TLE,真的是莫名其妙呀...一直在考慮要不要把互動的 Judge 程式也寫一份來對拍看看是否正確,但是覺得好麻煩就放棄了。

我就這樣測了好久好久 ... 後來隊友來問我這題到底盡展得如何,我就開始向隊友說這題我實際採用的方法,以及我覺得可能出錯的地方和疑點,說著說著我突然發現,問問題時前面要加 '?',但是我卻加成 '!' 啊...該不會我 debug 那麼久就只是因為這樣吧?之後修掉這個 bug 後就 AC 了。並且實驗證時,AC的八十分鐘前上傳的 code也是修掉這個 bug 就能 AC。

真的非常對不起這場比賽的隊友們 OAQ