#261154 (Java) No.5002 stick xor

• 問題: No.5002 stick xor
• ユーザー: tsukammo
• 提出日時: 2018-05-28 20:08:39
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 958 ms / 1,000 ms
• コード長: 6,938 bytes
• コンパイル時間: 35,753 ms
• 実行使用メモリ: 24,592 KB
• スコア: 41,201
• 最終ジャッジ日時: 2018-05-28 20:09:16
• ジャッジサーバーID （参考情報）: judge9 /

ファイルパターン	結果
other	AC * 32

ソースコード

import java.io.IOException;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
import java.util.Scanner;

/**
 * yukicoder
 *
 * @author tsukammo
 */
public class Main {

	Scanner sc = new Scanner(System.in);
	Random rnd = new Random(19881221L);
	long st, et;
	int first;

	public static void main(String[] args) throws IOException {
		new Main().solve();
	}

	// 制約
	static int N = 60, K = 500, NN = N * N, W = 25;
	int[] L;
	boolean[][] map;
	Rect[] rs;
	List<Rect> rlist;
	Deque<Node> nstack;

	void solve() {
		input();
		init();
		simulate(); // new
		if (submit) {
			output();
		}
	}

	void init() {
		rs = new Rect[K];
		rlist = new ArrayList<Rect>();
		for (int i = 0; i < K; i++) {
			Rect tmp = new Rect(i, L[i] - 1);
			rs[i] = tmp;
			rlist.add(tmp);
		}
		Collections.sort(rlist);
		if (submit) {
			return;
		}
	}

	void simulate() {
		System.err.println("First:" + (first));

		int score = first;

		for (Rect r : rlist) {
			int max = -100;
			// row
			for (int i = 0; i < N; i++) {
				int sum = 0;
				for (int x = 0; x <= r.w; x++) {
					sum += map[i][x] ? 1 : -1;
				}
				if (max <= sum) {
					max = sum;
					r.y = i;
					r.x = 0;
					r.d = 0;
				}
				for (int j = 1; j < N - r.w; j++) {
					sum += map[i][j + r.w] ? 1 : -1;
					sum -= map[i][j - 1] ? 1 : -1;
					if (max <= sum) {
						max = sum;
						r.y = i;
						r.x = j;
						r.d = 0;
					}
				}
			}
			// col
			for (int j = 0; j < N; j++) {
				int sum = 0;
				for (int y = 0; y <= r.w; y++) {
					sum += map[y][j] ? 1 : -1;
				}
				if (max < sum) {
					max = sum;
					r.y = 0;
					r.x = j;
					r.d = 1;
				}
				for (int i = 1; i < N - r.w; i++) {
					sum += map[i + r.w][j] ? 1 : -1;
					sum -= map[i - 1][j] ? 1 : -1;
					if (max < sum) {
						max = sum;
						r.y = i;
						r.x = j;
						r.d = 1;
					}
				}
			}
			// update
			score -= max;
			int ex = r.x;
			int ey = r.y;
			// flip
			for (int i = 0; i <= r.w; i++) {
				map[ey][ex] = !map[ey][ex];
				ex += dx[r.d];
				ey += dy[r.d];
			}
		}

		System.err.println("End  :" + (score));

		score = evalAll();
		System.err.println("Start:" + (score));

		long currentTime = System.currentTimeMillis();

		double C = TEMP * TL;
		double Line = 0.0;

		int tmpScore = 0;
		int c = 0, u = 0;

		while (currentTime < et) {

			if (c % 1000 == 0) {
				currentTime = System.currentTimeMillis();
				Line = (et - currentTime) / C;
			}
			c++;

			int id = rnd.nextInt(rlist.size());
			Rect r = rs[id];
			int d = rnd.nextInt(2);
			int x, y;
			if (d == 0) {
				x = rnd.nextInt(N - r.w);
				y = rnd.nextInt(N);
			} else {
				x = rnd.nextInt(N);
				y = rnd.nextInt(N - r.w);
			}
			int ex = x + r.w * dx[d];
			int ey = y + r.w * dy[d];
			tmpScore = evalChange(x, y, d, r);

			if (tmpScore <= 0 || Line > tmpScore * rnd.nextDouble()) {
				score += tmpScore;
				// update
				r.x = x;
				r.y = y;
				r.d = d;
				if (tmpScore < 0) {
					u++;
				}
				//System.err.println("update:" + score);
			} else {
				// rollback
				// before
				ex = r.x;
				ey = r.y;
				for (int i = 0; i <= r.w; i++) {
					map[ey][ex] = !map[ey][ex];
					//map.flip(ey * N + ex);
					ex += dx[r.d];
					ey += dy[r.d];
				}
				// after
				ex = x;
				ey = y;
				for (int i = 0; i <= r.w; i++) {
					map[ey][ex] = !map[ey][ex];
					//map.flip(ey * N + ex);
					ex += dx[d];
					ey += dy[d];
				}
			}
		}
		System.err.println("End  :" + (score));
		score = evalAll();
		System.err.println("End  :" + (score));
		System.err.println("Last :" + (first - score));
	}

	int evalChange(int x, int y, int d, Rect r) {
		int ret = 0;
		// before
		int ex = r.x;
		int ey = r.y;
		for (int i = 0; i <= r.w; i++) {
			if (map[ey][ex]) {
				ret--;
			} else {
				ret++;
			}
			map[ey][ex] = !map[ey][ex];
			ex += dx[r.d];
			ey += dy[r.d];
		}
		// after
		ex = x;
		ey = y;
		for (int i = 0; i <= r.w; i++) {
			if (map[ey][ex]) {
				ret--;
			} else {
				ret++;
			}
			map[ey][ex] = !map[ey][ex];
			ex += dx[d];
			ey += dy[d];
		}

		return ret;
	}

	int evalAll() {
		int ret = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j]) {
					ret++;
				}
			}
		}
		return ret;
	}

	final static int dx[] = new int[] { 1, 0, -1, 0 };
	final static int dy[] = new int[] { 0, 1, 0, -1 };

	boolean outMap(int x, int y) {
		return !(x > -1 && y > -1 && x < N && y < N);
	}

	void input() {
		N = sc.nextInt();
		st = System.currentTimeMillis();
		et = st + TL;
		K = sc.nextInt();
		L = new int[K];
		for (int i = 0; i < K; i++) {
			L[i] = sc.nextInt();
		}
		sc.nextLine();
		map = new boolean[N][N];
		first = 0;
		for (int i = 0; i < N; i++) {
			String tmp = sc.nextLine();
			char[] cl = tmp.toCharArray();
			for (int j = 0; j < N; j++) {
				if (cl[j] == '1') {
					map[i][j] = true;
					first++;
				}
			}
		}
	}

	class Node implements Comparable<Node> {

		BitSet map;
		Rect[] rs;
		int score;
		int nextRecNo;

		public Node(BitSet map) {
			this.map = (BitSet) map.clone();
			this.rs = new Rect[K];
			score = map.cardinality();
			nextRecNo = 0;
		}

		public Node(Node n) {
			this.score = n.score;
			this.map = (BitSet) n.map.clone();
			this.nextRecNo = n.nextRecNo;
		}

		@Override
		public int compareTo(Node o) {
			return Integer.compare(this.score, o.score);
		}
	}

	class Rect implements Comparable<Rect> {
		int id;
		int x, y, d;
		int w;

		public Rect(int id, int w) {
			this.id = id;
			this.w = w;
			/*
			this.x = rnd.nextInt(N);
			this.y = rnd.nextInt(N);
			this.d = rnd.nextInt(4);
			int ex = x + w * dx[d];
			int ey = y + w * dy[d];
			if (outMap(ex, ey)) {
			if (outMap(ex, ey)) {
			if (d > 1) {
			d -= 2;
			} else {
			d += 2;
			}
			}
			}
			ex = x;
			ey = y;
			// flip
			for (int i = 0; i <= w; i++) {
			map[ey][ex] = !map[ey][ex];
			ex += dx[d];
			ey += dy[d];
			}
			*/
		}

		public String toString() {
			int sx = x + 1;
			int sy = y + 1;
			int ex = sx + w * dx[d];
			int ey = sy + w * dy[d];
			if (d > 1) {
				sx = ex;
				sy = ey;
				d -= 2;
				ex = sx + w * dx[d];
				ey = sy + w * dy[d];
			}
			return sy + " " + sx + " " + ey + " " + ex;
		}

		@Override
		public int compareTo(Rect o) {
			return Integer.compare(o.w, this.w);
		}
	}

	class Random {
		private long seed;
		private final long multiplier = 0x5DEECE66DL, addend = 0xBL, mask = (1L << 48) - 1;
		int bits, val;

		Random(long seed) {
			this.seed = seed;
		}

		int nextInt(int n) {
			do {
				bits = (int) ((seed = (seed * multiplier + addend) & mask) >>> 17);
				val = bits % n;
			} while (bits - val + (n - 1) < 0);
			return val;
		}

		double nextDouble() {
			return nextInt(10000000) / 10000000.0;
		}
	}

	void output() {
		for (int i = 0; i < K; i++) {
			System.out.println(rs[i].toString());
		}
	}

	final double TEMP = 100000;
	static final long TL = 800;
	static boolean submit = true;
}