結果

問題 No.5002 stick xor
ユーザー threepipes_sthreepipes_s
提出日時 2018-05-29 04:00:27
言語 Java21
(openjdk 21)
結果
AC  
実行時間 939 ms / 1,000 ms
コード長 10,535 bytes
コンパイル時間 33,229 ms
実行使用メモリ 24,800 KB
スコア 42,349
最終ジャッジ日時 2018-05-29 04:01:02
ジャッジサーバーID
（参考情報） 		judge8 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 889 ms
24,792 KB
testcase_01 AC 920 ms
24,796 KB
testcase_02 AC 902 ms
24,796 KB
testcase_03 AC 929 ms
24,796 KB
testcase_04 AC 871 ms
24,792 KB
testcase_05 AC 878 ms
24,796 KB
testcase_06 AC 891 ms
24,796 KB
testcase_07 AC 881 ms
24,800 KB
testcase_08 AC 922 ms
24,792 KB
testcase_09 AC 879 ms
24,796 KB
testcase_10 AC 930 ms
24,348 KB
testcase_11 AC 883 ms
24,796 KB
testcase_12 AC 929 ms
24,792 KB
testcase_13 AC 886 ms
24,796 KB
testcase_14 AC 912 ms
24,792 KB
testcase_15 AC 924 ms
24,800 KB
testcase_16 AC 918 ms
24,344 KB
testcase_17 AC 873 ms
24,792 KB
testcase_18 AC 908 ms
24,800 KB
testcase_19 AC 939 ms
24,344 KB
testcase_20 AC 891 ms
24,796 KB
testcase_21 AC 926 ms
24,796 KB
testcase_22 AC 937 ms
24,792 KB
testcase_23 AC 895 ms
24,792 KB
testcase_24 AC 923 ms
24,796 KB
testcase_25 AC 895 ms
24,792 KB
testcase_26 AC 933 ms
24,792 KB
testcase_27 AC 921 ms
24,796 KB
testcase_28 AC 885 ms
24,800 KB
testcase_29 AC 889 ms
24,344 KB
testcase_30 AC 866 ms
24,796 KB
testcase_31 AC 879 ms
24,792 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.*;
import java.util.*;

public class Main implements Runnable {
    static ContestScanner in;
    static Writer out;
    public static void main(String[] args) {
        new Thread(null, new Main(), "", 16 * 1024 * 1024).start();
    }

    public void run() {
        Main main = new Main();
        try {
            in = new ContestScanner();
            out = new Writer();
            main.solve();
            out.close();
            in.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    int[] l, lt;
    long[] mask;
    int[] lx, ly, ld;
    long[][] map;
    int n, k;
    void solve() throws IOException {
        genTestIO();
        solveGreedy();
        sa();
        output();
//        solveByTest();
    }

    void solveByTest() {
        int sum = 0;
        for (int i = 0; i < 32; i++) {
            genTest(i + 1000);
            int res = solveGreedy() + sa();
            sum += res;
            System.out.println(res);
        }
        System.out.println("Score: " + sum);
//        output();
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                System.out.print((map[i][0] >> j) & 1);
//                System.out.print(" ");
//            }
//            System.out.println();
//        }
    }

    void output() {
        for (int i = 0; i < k; i++) {
            final int idx = lt[i];
            if(ld[idx] == 0) out.println(String.format("%d %d %d %d", ly[idx] + 1, lx[idx] + 1, ly[idx] + 1, lx[idx] + l[idx]));
            else             out.println(String.format("%d %d %d %d", ly[idx] + 1, lx[idx] + 1, ly[idx] + l[idx], lx[idx] + 1));
        }
    }

    void genTest(long seed) {
        boolean debug = false;
        Random rand = new Random(seed);
        n = 60;
        k = 500;
        l = new int[k];
        lt = new int[k];
        lx = new int[k];
        ly = new int[k];
        ld = new int[k];
        mask = new long[k];
        Pair[] p = new Pair[k];
        if (debug) out.println(n + " " + k);
        for (int i = 0; i < k; i++) {
            l[i] = rand.nextInt(25) + 1;
            p[i] = new Pair(-l[i], i);

            if (debug) {
            if (i > 0) out.print(" ");
            out.print(l[i]);
            }
        }
        Arrays.sort(p);
        for (int i = 0; i < k; i++) {
            l[i] = -p[i].a;
            mask[i] = (1L << l[i]) - 1;
            lt[p[i].b] = i;
        }
        if (debug) out.println();
        map = new long[n][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                long a = rand.nextInt(2);
                map[i][0] |= a << j;
                map[j][1] |= a << i;

                if (debug)out.print(a);
            }
            if (debug)out.println();
        }
    }

    void genTestIO() throws IOException {
        n = in.nextInt();
        k = in.nextInt();
        l = new int[k];
        lt = new int[k];
        lx = new int[k];
        ly = new int[k];
        ld = new int[k];
        mask = new long[k];
        for (int i = 0; i < k; i++) {
            l[i] = in.nextInt();
            lt[i] = i;
            mask[i] = (1L << l[i]) - 1;
        }
        map = new long[n][2];
        for (int i = 0; i < n; i++) {
            char[] s = in.nextToken().toCharArray();
            for (int j = 0; j < n; j++) {
                long a = s[j] - '0';
                map[i][0] |= a << j;
                map[j][1] |= a << i;
            }
        }
    }

    int solveGreedy() {
        int cnt = 0;
        for (int i = 0; i < k; i++) {
            int max = Integer.MIN_VALUE;
            int maxPos = 0;
            int maxV = 0;
            for (int j = 0; j < n; j++) {
                for (int m = 0; m < n - l[i]; m++) {
                    for (int d = 0; d < 2; d++) {
                        int res = check(d, j, m, i, map);
                        if (res > max) {
                            max = res;
                            maxPos = j * n + m;
                            maxV = d;
                        }
                    }
                }
            }
            cnt += max;
            setLPos(maxV, maxPos / n, maxPos % n, i);
            apply(maxV, maxPos / n, maxPos % n, i, map);
        }
        return cnt;
    }

    /**
     * @param v 縦横
     * @param y y座標(実際のもの)
     * @param x x座標(実際のもの)
     * @param id 利用する棒のid
     */
    void applyReal(int v, int y, int x, int id, long[][] map) {
        if (v == 1) apply(v, x, y, id, map);
        else apply(v, y, x, id, map);
    }

    void apply(int v, int y, int x, int id, long[][] map) {
        map[y][v] ^= mask[id] << x;
        for (int i = 0; i < l[id]; i++) {
            map[i + x][v^1] ^= 1L << y;
        }
    }

    void setLPos(int v, int y, int x, int id) {
        if (v == 1) {
            int tmp = y;
            y = x;
            x = tmp;
        }
        ld[id] = v;
        ly[id] = y;
        lx[id] = x;
    }

    int checkReal(int v, int y, int x, int id, long[][] map) {
        if (v == 1) return check(v, x, y, id, map);
        else return check(v, y, x, id, map);
    }

    int check(int v, int y, int x, int id, long[][] map) {
        return Long.bitCount(map[y][v]) - Long.bitCount(map[y][v] ^ (mask[id] << x));
    }

    int checkDoubleReal(int v, int y1, int x1, int y2, int x2, int id, long[][] map) {
        if (v == 1) return checkDouble(v, x1, y1, x2, y2, id, map);
        else return checkDouble(v, y1, x1, y2, x2, id, map);
    }

    int checkDouble(int v, int y1, int x1, int y2, int x2, int id, long[][] map) {
        if (y1 == y2) {
            return Long.bitCount(map[y1][v]) - Long.bitCount(map[y1][v] ^ (mask[id] << x1) ^ (mask[id] << x2));
        } else {
            return check(v, y1, x1, id, map) + check(v, y2, x2, id, map);
        }
    }

    int tld, tly, tlx, tid;
    int next(Random rand, int vol) {
        tid = rand.nextInt(k);
        int score;
        if (rand.nextDouble() < 0.01) {
            tld = ld[tid] ^ 1;
            tlx = lx[tid];
            tly = ly[tid];
            if (tld == 0) {
                if (lx[tid] + l[tid] >= n) tlx = n - l[tid];
            } else {
                if (ly[tid] + l[tid] >= n) tly = n - l[tid];
            }
            final long cp = (map[ly[tid]][0] >> lx[tid]) & 1;
            score = checkReal(ld[tid], ly[tid], lx[tid], tid, map)
                    + checkReal(tld, tly, tlx, tid, map) + (cp == 1 ? -2 : 2);
        } else {
            final int mvol = rand.nextInt(vol) + 1;
            final int yvol = rand.nextInt(mvol);
            final int xvol = mvol - yvol;
            int minY = Math.max(0, ly[tid] - yvol);
            final int maxY = Math.min(n - (ld[tid] == 0 ? 1 : l[tid]), ly[tid] + yvol);
            minY = Math.min(minY, maxY);
            tly = rand.nextInt(maxY - minY + 1) + minY;
            int minX = Math.max(0, lx[tid] - xvol);
            final int maxX = Math.min(n - (ld[tid] == 0 ? l[tid] : 1), lx[tid] + xvol);
            minX = Math.min(minX, maxX);
            tlx = rand.nextInt(maxX - minX + 1) + minX;
            score = checkDoubleReal(ld[tid], ly[tid], lx[tid], tly, tlx, tid, map);
            tld = ld[tid];
        }
        return score;
    }

    void applyNext() {
        applyReal(ld[tid], ly[tid], lx[tid], tid, map);
        ld[tid] = tld;
        ly[tid] = tly;
        lx[tid] = tlx;
        applyReal(ld[tid], ly[tid], lx[tid], tid, map);
    }

    double temper(double r) {
        return Math.pow(TEMPER, r);
    }

    double prob(double nextScore, double temper) {
        if(0 <= nextScore) return 1;
        else return Math.pow(Math.E, nextScore / temper);
    }

    final double TEMPER = 0.15;
    int sa() {
        final int MAX_ITER = 1500000;
        Random rand = new Random(0);
        int score = 0;//init(rand);
        for (int i = 0; i < MAX_ITER; i++) {
            int vol = Math.max(1, (MAX_ITER - i) * 20 / MAX_ITER);
            int nextScore = next(rand, vol);

            double temperature = temper((double) i / MAX_ITER);
            double prob = prob(nextScore, temperature);
            if(rand.nextDouble() <= prob) {
                score += nextScore;
                applyNext();
            }
        }
        return score;
    }

    int init(Random rand) {
        int score = 0;
        for (int i = 0; i < k; i++) {
            ld[i] = rand.nextInt(2);
            final int maxY = n - (ld[i] == 0 ? 1 : l[i]);
            final int maxX = n - (ld[i] == 0 ? l[i] : 1);
            ly[i] = rand.nextInt(maxY + 1);
            lx[i] = rand.nextInt(maxX + 1);
            score += checkReal(ld[i], ly[i], lx[i], i, map);
            applyReal(ld[i], ly[i], lx[i], i, map);
        }
        return score;
    }
}

class Pair implements Comparable<Pair> {
    int a, b;
    Pair(int a, int b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public int compareTo(Pair o) {
        if (a != o.a) return a - o.a;
        return b - o.b;
    }
}

class Writer extends PrintWriter{
    public Writer(String filename)throws IOException
    {super(new BufferedWriter(new FileWriter(filename)));}
    public Writer()throws IOException {super(System.out);}
}
class ContestScanner implements Closeable {
    private BufferedReader in;private int c=-2;
    public ContestScanner()throws IOException
    {in=new BufferedReader(new InputStreamReader(System.in));}
    public ContestScanner(String filename)throws IOException
    {in=new BufferedReader(new InputStreamReader(new FileInputStream(filename)));}
    public String nextToken()throws IOException {
        StringBuilder sb=new StringBuilder();
        while((c=in.read())!=-1&&Character.isWhitespace(c));
        while(c!=-1&&!Character.isWhitespace(c)){sb.append((char)c);c=in.read();}
        return sb.toString();
    }
    public String readLine()throws IOException{
        StringBuilder sb=new StringBuilder();if(c==-2)c=in.read();
        while(c!=-1&&c!='\n'&&c!='\r'){sb.append((char)c);c=in.read();}
        return sb.toString();
    }
    public long nextLong()throws IOException,NumberFormatException
    {return Long.parseLong(nextToken());}
    public int nextInt()throws NumberFormatException,IOException
    {return(int)nextLong();}
    public double nextDouble()throws NumberFormatException,IOException
    {return Double.parseDouble(nextToken());}
    public void close() throws IOException {in.close();}
}
0