這篇也是紀錄有關某場比賽的事，不過只特別記錄其中一件插曲。
應該有不少人都聽過黃色小鴨除錯法吧？我個人相信這招對 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
沒有留言:
張貼留言