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

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

看板Prob_Solve (計算數學 Problem Solving)作者RockLee (Now of all times)時間12年前 (2012/02/24 16:00)推噓0(0推 0噓 0→)

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

題目敘述網址: 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 時, 這樣的關係還蠻明顯的. 但個數更多時, 這樣的關係似乎沒那麼直覺. 有高手可以進一步說明或證明為何有這樣的關係嗎? [Jonick's solution in Java] import java.io.*; public class c implements Runnable { BufferedReader in; BufferedWriter out; final static int INF = 10000000; public class Rect { int x1, y1, x2, y2; Rect(int x1, int y1, int x2, int y2) { this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; } public boolean isOverlapped(int s1, int f1, int ss1, int ff1) { int ms = Math.max(s1, ss1); int mf = Math.min(f1,ff1); return mf - ms >= -1; } public boolean canJoin(Rect r) { if( !isOverlapped(x1,x2,r.x1,r.x2) ) return false; if( !isOverlapped(y1,y2,r.y1,r.y2) ) return false; if( x1 == r.x2 + 1 && y1 == r.y2 + 1 ) return false; if( r.x1 == x2 + 1 && r.y1 == y2 + 1 ) return false; return true; } } int color[]; public void join(int n, int c1, int c2 ) { for( int i = 0; i < n; i++ ) { if( color[i] == c2 ) { color[i] = c1; } } } public void solve() throws Exception { int n = Integer.parseInt(readword()); color = new int[n]; Rect a[] = new Rect[n]; for( int i = 0; i < n; i++ ) { color[i] = i; a[i] = new Rect(Integer.parseInt(readword()), Integer.parseInt(readword()), Integer.parseInt(readword()), Integer.parseInt(readword())); } for( int i = 0; i < n; i++ ) for( int j = i+1; j < n; j++ ) { if( a[i].canJoin(a[j]) ) { join(n,color[i],color[j]); } } int answer = 0; for( int i = 0; i < n; i++ ) { boolean hasColor = false; for( int j = 0; j < n; j++ ) { if( color[j] == i ) { hasColor = true; break; } } if( !hasColor ) { continue; } int maxX = -INF; int maxY = -INF; for( int j = 0; j < n; j++ ) { if( color[j] == i ) { maxX = Math.max(maxX, a[j].x2); maxY = Math.max(maxY, a[j].y2); } } for( int j = 0; j < n; j++ ) { if( color[j] == i ) { int tmp = maxX - a[j].x1 + maxY - a[j].y1; if( tmp > answer ) answer = tmp; } } } out.write((answer+1) + "\n"); } public String readword() throws IOException { int c = in.read(); while( c >= 0 && c <= ' ' ) c = in.read(); if( c < 0 ) return ""; StringBuilder bld = new StringBuilder(); while( c > ' ' ) { bld.append((char)c); c = in.read(); } return bld.toString(); } public void run() { try { in = new BufferedReader(new FileReader(this.getClass().getName() + ".in")); out = new BufferedWriter(new FileWriter(this.getClass().getName() + ".out")); int tn = Integer.parseInt(readword()); for(int i = 0; i < tn; i++ ) { out.write("Case #" + (i+1) + ": "); solve(); } out.flush(); } catch( Exception e ) { e.printStackTrace(); System.exit(1); } } public static void main(String[] args) { new Thread(new c()).start(); } } -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.137.134.119