TCO17MM Round3 最終提出ソースコード

PoisonedWine.java

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<String> 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<Integer> 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<Integer> 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<Integer> 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<Integer> 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;
    }
}