PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Google Code Jam 2010, Round 2 - C

看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間12年前 (2012/02/25 09:19)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/2 (看更多)

※ 引述《RockLee (Now of all times)》之銘言： : 題目敘述網址: : http://code.google.com/codejam/contest/635102/dashboard#s=p2 : 我想到的 algorithm 只能在限定時間內跑完 small data set, : 遇到 large data set 就無力了 Orz... : 看了前幾名的 algorithm, 關鍵似乎在於, : 一開始相鄰的 bacteria 的長方形, : 存在的時間會是相鄰長方形中 (Max(X2) + Max(Y2)) 扣掉 : 相鄰長方形中任一個的 (X1 + Y1) 得到的值中最大的那一個再加一. : 相鄰長方形個數為 1 或 2 時, 這樣的關係還蠻明顯的. : 但個數更多時, 這樣的關係似乎沒那麼直覺. : 有高手可以進一步說明或證明為何有這樣的關係嗎? 你聽過 Level-Set 的方法嗎? 我認為應該是這樣的: Let's define the survial time of each node. t(n) A is in the left node, B is the upper node then the C node survial time will be t(C) = max( t(A), t(B) ) + 1. But when you start to scan, you need to pay attentaion to the ordering. Because the bacteria can only grow to the right-lower direction, you should start your scan from left-upper boundary. -- 趙客縵胡纓，吾鉤霜雪明。銀鞍照白馬，颯沓如流星。十步殺一人，千里不留行。是了拂衣去，深藏身與名。閑過信陵飲，脫劍膝前橫。將炙啖朱亥，持觴勸侯贏。三杯吐然諾，五嶽倒為輕。眼花耳熱後，意氣素霓生。就趙揮金錘，邯鄲先震驚。千秋二壯士，烜赫大梁城。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 128.125.20.198