= = = = = = = = = = = = = =
馬上就毀了不久前說的 V 字形目標 XD
這場比賽無疑是我寫解題報告至今最簡單的一場Div. 1比賽，可是我出太多包了就掛掉了 Orz 總覺得當我有明確目標的時候就一定會爆炸 ... (看看我至今為止進不了任何 online round)。
這場比賽有幾個特殊的地方：1. 難度沒有按照順序排 2. Codeforces 第一次採用以 250 分為間隔的動態分數。
Problem B --- Group Photo 2 (online version)
tag：[ 枚舉 ][ greedy ]
關鍵字：矩形橫擺直擺
賽前我並不知道題目沒有按照難度排，但尤於求攻心切就先開了 pB (自負能以差不多的時間寫完 A 和 B)，但是大概是太急躁了 ... 過了三分多鐘我都還沒看懂題目，在想要不要先回來讀 A 的題目時先看了一下 scoreboard，看了感到非常莫名， pA沒有人上傳，倒是 pE 有少數幾隻貓上傳 ... 這時心裡猜想或許 pE 是 well know 的難題才會發生這種事？於是決定繼續試圖理解 pB，終於理解意思後，立刻把這題連想到我曾經在 Topcoder SRM629 出的 Div1 250 都是橫擺或直擺的矩形問一些事情，馬上就會做了。
Problem E --- The Art of Dealing with ATM
tag： [搜索]
關鍵字：零錢
pB 過了 pretest 後看了 scoreboard，發現有大量的人傳了 pE，以及少數人傳 pB，但沒有人傳 p ，於是我開始相信這場難度沒有按照順序排，但看完 pE想了一下後並不知道怎麼做 ...，賽後看了別人 AC 的 code 才發現我看錯題目了。我沒有看到題目說的每次提領的錢至多只能提領兩種幣額的限制，賽中我不時回來思考這題，花了不少時間。
Problem D --- Social Network
tag：[貪心]
關鍵字：區間貪心
雖然 pE 卡住了，但是一直卡下去很不妙，所以就繼續開其他題，這題題目對我來說也是很難讀懂，但也是讀懂後就會做了，而且 code 很簡短，一個 for 迴圈掃過去就結束了。在我感覺上這題只有一般 Div. 1 B 以下的程度。
Problem A --- And Yet Another Bracket Sequence
tag：[字串比對][ 資料結構 ]
關鍵字：合法括弧
這題我也是看完題目後就會做了，但是覺得可能還會有比這題好寫的題目，在寫這題前先去看了 pC。
Problem C --- Rooks and Rectangules
tag：[ offline ] [ 資料結構 ]
關鍵字：矩形區域類資料結構
這題我倒是沒有讀完題就知道怎麼做 ...，應該說我第一個想到的做法有點困難，但看別人 AC這題的速度大概可以知道這題有更簡單的方法，但我覺得比起去思考更簡單的方法，還是去抄抄 codebook 寫 pA 會比較容易。賽後多想個幾分鐘就想到簡單的做法了。
我複製了 suffix array 和線段樹求 RMQ 的 codebook 迅速的寫完 pA， 但是之後一直 WA 在 pretest 第 12 組，直到賽末。賽中一直 de 不出 bug 時超心急的，我已經好久沒有卡 bug 卡那麼久了，我覺得 code 完全有按照我的思考寫啊！當下覺得要不是我想到的做法是錯的，要不然就是我的 codebook 有錯，可是無論重新檢視自己的做法證確性多少次，都還是覺得是對的，並且我那兩份 codebook 都用了好多次了。又重新看了幾次這份 code 我沒抄 codebook 的部分，都找不到錯誤，過程中索性先回去繼續想 pE 轉換情緒幾次，但也都處處碰壁。直到最後，沒有奇蹟。這場比賽我以兩題作收。
事後沉澱下繼續找 bug，當時心想，要是真的是 codebook 有 bug 的話那還蠻糟糕的，所以也幫抄 codebook 的部分 debug，然後就發現我的 bug 了...，原來我的 RMQ codebook 只當所有數是非負才會對 ...，把這部份修過後重上傳，在第 14 組 test TLE 了...，這也太崩潰 Orz 這代表就算我 RMQ 的 codebook 沒有 bug，我也一定無法 AC 這題 ...。難道我的方法太慢了嗎？我看了一下別人的 AC code，複雜度也和我一樣呀！也是一個 suffix array加一個 O(n log n) 的資料結構，我在測了一下我的 code，發現在 suffix array 的部分就 TLE 了 ...，這是怎樣，這已經是過去我把我自己寫的 suffix array code換成對友寫的快我幾倍的 code耶，結果還是不夠快 Orz，最後我去複製了一分別人 AC 的 code 裡的 suffix array 的部分蓋掉我用的 suffix array，終於 AC了。
雖然 rating 大降，不過這場收穫算是很多吧，把我的suffix array codebook 變得更快，以及除掉 codebook 裡的其中一個潛在 bug。不過上一篇 BLOG 裡寫的目標失敗了還是令人非常傷心 OAQ
沒有留言:
張貼留言