※ 引述《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