Instantly share code, notes, and snippets.

# threepipes/PoisonedWine.java Last active Jul 20, 2017

TCO17MM Round3 最終提出ソースコード
 import java.io.*; import java.math.BigDecimal; import java.math.MathContext; import java.util.*; // -------8<------- start of solution submitted to the website -----8<------- public class PoisonedWine { // params static double LOG_COEF = 0.3 + 0.002 * 50; // 0.30-0.50:0.002*100 static double TEST_SUB = 0.0 + 0.05 * 66; // 0-5:0.05*100 static double ROUND_COEF = 1.0 + 0.01 * 7; // 1.0-2.0:0.01*100 static double WID_COEF = 0.95+ 0.002 * 59; // 0.95-1.15:0.002*100 static double TEST_COEF = 0.0 + 0.002 * 48; // 0.0-0.2:0.002*100 static double STRIP_COEF = 0.5 + 0.01 * 4; // -0.1-0.1:0.002*100 static double Y_COEF = 1.8 + 0.004 * 57; // 1.8-2.2:0.004*100 static double X_COEF = 0.9 + 0.002 * 71; // 0.9-1.1:0.002*100 static double SHUFFLE_COEF = 0.0 + 0.1 * 24; static double ROUND_OFFSET = 1; final double Y_OFFSET = 0.082; static int randSeed = 10; Random rand = new Random(randSeed); void shuffle(int[] a, int len) { for(int i = 0; i < len; i++) { int i1 = i; int i2 = rand.nextInt(len); int tmp = a[i1]; a[i1] = a[i2]; a[i2] = tmp; } } int W, P, S, R; int curW; int[] rangeLen, rangePoison; int rangeN; int findOneRest; public int[] testWine(int numBottles, int testStrips, int testRounds, int numPoison) { W = numBottles; P = numPoison; S = testStrips; R = testRounds; rangeLen = new int[S + 1]; rangePoison = new int[S + 1]; rangeLen[0] = W; rangePoison[0] = P; rangeN = 1; int[] bottle = new int[numBottles]; for(int i = 0; i < numBottles; i++) { bottle[i] = i; } shuffle(bottle, bottle.length); for(int test = 0; test < testRounds && testStrips > 0 && numBottles > P; test++) { boolean changeRange = false; if(P == 1 && (numBottles < (1 << testStrips) || testRounds - test == 1)) { // 1発でワインを求められるケース numBottles = findOnePoison(bottle, numBottles, numBottles, testStrips); testStrips = findOneRest; continue; } curW = numBottles; int round = testRounds - test; double bestWidth = Math.min( Y_OFFSET + Y_COEF * numBottles / ((numPoison * X_COEF - LOG_COEF * Math.log10(round) * (testStrips * STRIP_COEF - TEST_SUB)) * (round * ROUND_COEF + ROUND_OFFSET)), numBottles / Math.min(numBottles, testStrips) ); if(bestWidth < 1) { bestWidth = numBottles / Math.min(numBottles, testStrips); } if(numBottles == 1 && bestWidth > numBottles / 2) { bestWidth = numBottles / 2; if(bestWidth < 1) bestWidth = 1; } int n = (int) bestWidth; int newN = (int) (n * Math.pow(WID_COEF, test - testRounds * TEST_COEF)); if(newN * testStrips <= numBottles) n = newN; if(!changeRange) { rangeLen[0] = numBottles; rangePoison[0] = numPoison; rangeN = 1; } if(n <= 0) n = (numBottles + testStrips - 1) / testStrips; List tests = new ArrayList<>(); for (int i = 0; i < testStrips; ++i) { if(i * n >= numBottles) break; String t = "" + bottle[i * n]; for (int j = 1; j < n && i * n + j < numBottles; ++j) t += "," + bottle[i * n + j]; tests.add(t); } int[] testRes = PoisonTest.useTestStrips(tests.toArray(new String[0])); int next = 0; int used = 0; List warning = new ArrayList<>(); for (int i = 0; i * n < numBottles; ++i) { if (i >= testRes.length || testRes[i] == 1) { if (i < testRes.length) { // 毒を含む場合 int j; for (j = 0; j < n && i * n + j < numBottles; ++j) warning.add(bottle[i * n + j]); rangeLen[0] -= j; rangePoison[0]--; rangeLen[rangeN] = j; rangePoison[rangeN++] = 1; used++; } else for (int j = 0; j < n && i * n + j < numBottles; ++j) { // 今回考えられていない範囲 bottle[next++] = bottle[i * n + j]; } } else { // 毒がなかった場合 final int num = Math.min(n, numBottles - i * n); rangeLen[0] -= num; } } // bottleの先頭 n * used は毒密度が高いので後ろに回す for(int w: warning) bottle[next++] = w; testStrips -= used; numBottles = next; if(rangePoison[0] == 0) { // 先頭範囲の毒が0になった場合 for(int i = rangeLen[0]; i < numBottles; i++) { bottle[i - rangeLen[0]] = bottle[i]; } numBottles -= rangeLen[0]; for(int i = 1; i < rangeN; i++) { rangeLen[i - 1] = rangeLen[i]; rangePoison[i - 1] = rangePoison[i]; } rangeN--; } if(rangeN > 1 && rangeLen[0] <= rangeLen[1] * SHUFFLE_COEF) { rangeLen[0] = numBottles; rangePoison[0] = numPoison; rangeN = 1; shuffle(bottle, numBottles); } } int[] ret = new int[numBottles]; for (int i = 0; i < numBottles; ++i) ret[i] = bottle[i]; return ret; } /** * 引数3のfindOnePoisonを実行して，ボトルを整形する * @param bottle ワインリスト * @param range 調査したい(毒が1以下と判明している)範囲 * @param trueBottleNum 実際に現在残っているワイン * @param strip * @return 調査後のワインリストサイズ */ int findOnePoison(int[] bottle, int range, int trueBottleNum, int strip) { List bad = findOnePoison(bottle, range, strip); int idx = 0; for(int i = 0; i < trueBottleNum - range; i++) { bottle[idx++] = bottle[range + i]; } for(int b: bad) { bottle[idx++] = b; } return idx; } /** * 範囲内に毒が1つ以下の場合，ワインから毒を見つける有名な某問題の手法を用いる * 毒可能性のあるワインのリストを返す * 当然ながらtestRoundが残っていること前提 * (注意: bottleの内容は変更しないので，goodbottleに基づいてbottleを修正すること) * @param bottle ワインリスト * @param wine 先頭からwine本のワインについて考える * @param strip * @return 危険ワインリスト */ List findOnePoison(int[] bottle, int wine, int strip) { String[] test = new String[strip]; for(int i = 1; i <= wine; i++) { // iの下位stripビットを見て，立ってるビットに相当するtestStripにワインを加える // 1-indexedに注意(毒が0である場合を考慮するため) for(int j = 0; j < strip; j++) { if((i & 1 << j) == 0) continue; if(test[j] == null) test[j] = "" + bottle[i - 1]; else test[j] += "," + bottle[i - 1]; } } int used = strip; int nextStrip = strip; for(int i = 0; i < strip; i++) { if(test[i] == null) used--; } if(used < strip) { String[] resized = new String[used]; System.arraycopy(test, 0, resized, 0, used); test = resized; } int[] result = PoisonTest.useTestStrips(test); int bit = 0; for(int i = 0; i < test.length; i++) { if(result[i] == 1) { bit |= 1 << i; nextStrip--; } } List bad = new ArrayList<>(); // 下位stripビットのビットパターンがbitに等しい場合毒の可能性 int mask = (1 << strip) - 1; for(int i = 1; i <= wine; i++) { if((i & mask) == bit) bad.add(bottle[i - 1]); } findOneRest = nextStrip; return bad; } }
to join this conversation on GitHub. Already have an account? Sign in to comment