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

Re: [問題] 這次的摳醬資格賽

看板Prob_Solve (計算數學 Problem Solving)作者RockLee (Now of all times)時間12年前 (2012/04/15 21:59)推噓3(3推 0噓 4→)

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

※ 引述《vocaloid (void *)》之銘言： : 查了一下台灣滿分的共三位強者 : 不知是否有在這邊潛水? : 想知道第四題的想法 : https://code.google.com/codejam/contest/1460488/dashboard#s=p3 : 讀完題目再看看sample就去打魔獸了... zz 昨天這題花了蠻久的時間，跟之前練習過的 2008-Final 相比，這題讓我覺得比其中的 (A)(B)(C) 都還要難。如果不是出在 Qualification Round，我應該沒有得分的機會。最後我用的方法正如同 dreamoon 大所說的「列舉所有可能發射的角度模擬一下」。原本我一直覺得這題應該有 trick 可以用，因為覺得 Qualification Round 的題目應該不會太難實作，不過一直到了吃完晚飯都還想不出 trick ，只好硬著頭皮寫我覺得可能 case 很多、非常容易寫錯的 simulation 。正如同官方解答提供的圖所顯示： http://code.google.com/codejam/contest/1460488/dashboard#s=a&a=3 這題可能的發射角度是有限的，只需要檢查半徑範圍為Ｄ內的所有格子中心的方向。我的作法是將每個格子分為 100 等分，以Ｘ中心對所有可能向量發射光線，光線的每一步以百分之一的向量長度進行移動，如果撞上鏡子邊縁就反射，如果撞上會消失的角落就繼續檢查下一個。如果這個向量是有效的，那麼在一百步之內一定會通過Ｘ中心。最後答案就是有效的向量數總和。以下是小弟將昨天上傳的 code 稍微 refactor 後的程式，希望不會太難懂： import java.io.*; import java.util.*; import java.math.*; class D { private static final boolean ECHO_ON = true; private static BufferedReader input; private static BufferedWriter output; private static int H, W, D, row, col; public static int gcd(int n, int m) {return (0 == m) ? (n) : gcd(m, n % m);} public static int sqrt(int X) { int answer = 1, interval = 1; for (int i = String.valueOf(X).length() / 2; i > 0; i--) {interval *= 10;} while (interval >= 1) { while ((answer * answer) <= X) {answer += interval;} answer -= interval; interval /= 10; } return answer; } public static void main(String[] args) { try { input = new BufferedReader(new FileReader(args[0] + ".in")); output = new BufferedWriter(new FileWriter(args[0] + ".out")); String line = input.readLine(); int testcases = getInt(line, 0); for (int testcase = 1; testcase <= testcases; testcase++) { char[][] real = getCharMatrix(input); HashSet<Integer> valid = new HashSet<Integer>(); for (int i = row - D; i <= row + D; i++) { int range = sqrt((D * D) - ((i - row) * (i - row))); for (int j = col - range; j <= col + range; j++) { int diffX = i - row; int diffY = j - col; if (0 == diffX && 0 == diffY) {continue;} int gcd = gcd(Math.abs(diffX), Math.abs(diffY)); int direction = (((diffX/gcd) + D) << 16) + ((diffY/gcd) + D); if (valid.contains(direction)) {continue;} int x = 100 * row + 50; int y = 100 * col + 50; for (int k = 0; k < 100; k++) { int nextX = x + diffX; int nextY = y + diffY; int xCell = x / 100; int yCell = y / 100; int nextXCell = nextX / 100; if (0 == nextX % 100) {nextXCell = (nextX + diffX) / 100;} // look one step furthur to decide true next cell for edge int nextYCell = nextY / 100; if (0 == nextY % 100) {nextYCell = (nextY + diffY) / 100;} boolean xReflection = false; boolean yReflection = false; if (xCell != nextXCell && yCell == nextYCell) { if ('#' == real[nextXCell][nextYCell]) {xReflection = true;} } else if (xCell == nextXCell && yCell != nextYCell) { if ('#' == real[nextXCell][nextYCell]) {yReflection = true;} } else if (xCell != nextXCell && yCell != nextYCell) { int cornerX = -1, cornerY = -1; if (nextXCell < xCell && nextYCell < yCell) {cornerX = 100 * (nextXCell + 1); cornerY = 100 * (nextYCell + 1);} else if (nextXCell > xCell && nextYCell < yCell) {cornerX = 100 * nextXCell; cornerY = 100 * (nextYCell + 1);} else if (nextXCell < xCell && nextYCell > yCell) {cornerX = 100 * (nextXCell + 1); cornerY = 100 * nextYCell;} else if (nextXCell > xCell && nextYCell > yCell) {cornerX = 100 * nextXCell; cornerY = 100 * nextYCell;} if ('#' == real[nextXCell][nextYCell] && '#' == real[xCell][nextYCell] && '#' == real[nextXCell][yCell]) {xReflection = yReflection = true;} else if ('#' == real[nextXCell][nextYCell] && '#' == real[xCell][nextYCell] && '#' != real[nextXCell][yCell]) {yReflection = true;} else if ('#' == real[nextXCell][nextYCell] && '#' != real[xCell][nextYCell] && '#' == real[nextXCell][yCell]) {xReflection = true;} else if ('#' != real[nextXCell][nextYCell] && '#' == real[xCell][nextYCell] && '#' == real[nextXCell][yCell]) { if ((cornerX - x) * (nextY - y) != (nextX - x) * (cornerY - y)) {xReflection = yReflection = true;} // not passing corner } else if ('#' == real[nextXCell][nextYCell] && '#' != real[xCell][nextYCell] && '#' != real[nextXCell][yCell]) { if ((cornerX - x) * (nextY - y) == (nextX - x) * (cornerY - y)) {break;} // hitting corner else if (Math.abs((cornerX - x) * (nextY - y)) < Math.abs((nextX - x) * (cornerY - y))) {yReflection = true;} else {xReflection = true;} } else if ('#' != real[nextXCell][nextYCell] && '#' == real[xCell][nextYCell] && '#' != real[nextXCell][yCell]) { if (Math.abs((cornerX - x) * (nextY - y)) > Math.abs((nextX - x) * (cornerY - y))) {yReflection = true;} } else if ('#' != real[nextXCell][nextYCell] && '#' != real[xCell][nextYCell] && '#' == real[nextXCell][yCell]) { if (Math.abs((cornerX - x) * (nextY - y)) < Math.abs((nextX - x) * (cornerY - y))) {xReflection = true;} } } if (xReflection) { diffX = -diffX; if (nextXCell < xCell) {x = (100 * (nextXCell + 1)) - (x - (100 * (nextXCell + 1)));} else {x = (100 * nextXCell) + ((100 * nextXCell) - x);} } if (yReflection) { diffY = -diffY; if (nextYCell < yCell) {y = (100 * (nextYCell + 1)) - (y - (100 * (nextYCell + 1)));} else {y = (100 * nextYCell) + ((100 * nextYCell) - y);} } x = x + diffX; y = y + diffY; if ((100 * row + 50) == x && (100 * col + 50) == y) {valid.add(direction); break;} } } } String result = "Case #" + testcase + ": " + valid.size(); output(result); } input.close(); output.close(); } catch (Exception e) { e.printStackTrace(); } } public static int getInt(String line, int index) {return Integer.parseInt(getString(line, index));} public static String getString(String line, int index) { line = line.trim(); while (index > 0) {line = line.substring(line.indexOf(' ') + 1); index--;} if ((-1) == line.indexOf(' ')) {return line;} else {return line.substring(0, line.indexOf(' '));} } public static char[][] getCharMatrix(BufferedReader input) throws Exception { String line = input.readLine(); H = getInt(line, 0); W = getInt(line, 1); D = getInt(line, 2); char[][] matrix = new char[H][W]; for (int i = 0; i < H; i++) { line = input.readLine(); for (int j = 0; j < W; j++) { char c = matrix[i][j] = line.charAt(j); if ('X' == c) {row = i; col = j;} } } return matrix; } public static void output(String s) throws Exception { if (ECHO_ON) {System.out.println(s);} output.write(s); output.newLine(); } } -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.137.136.75