AtCoder Regular Contest 003

Submission #19529

Source codeソースコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
		String[] nmk = s.readLine().split(" ");
		int N = Integer.valueOf(nmk[0]);
		int M = Integer.valueOf(nmk[1]);
		int K = Integer.valueOf(nmk[2]);
		boolean[][] forbidden = new boolean[N][N];
		for (int i = 0 ; i < M ; i++) {
			String[] data = s.readLine().split(" ");
			int a = Integer.valueOf(data[0]);
			int b = Integer.valueOf(data[1]);
			forbidden[a][b] = true;
			forbidden[b][a] = true;
		}

		long till = System.currentTimeMillis() + 9000;
		long succeeded = 0;
		long tried = 0;
		
		int[] init = new int[N];
		for (int i = 0 ; i < N ; i++) {
			init[i] = i;
		}
		while (true) {
			int[] now = init.clone();
			if (tried % 100 == 0) {
				if (System.currentTimeMillis() >= till) {
					break;
				}
			}
			for (int k = 0 ; k < K ; k++) {
				int a = (int)(Math.random() * N);
				int b = (int)(Math.random() * N);
				if (a == b) {
					k--;
					continue;
				}
				int t = now[a];
				now[a] = now[b];
				now[b] = t;
			}
			
			tried++;
			if (!forbidden[now[0]][now[N-1]]) {
				boolean isok = true;
				for (int i = 0 ; i < N - 1 ; i++) {
					if (forbidden[now[i]][now[i+1]]) {
						isok = false;
						break;
					}
				}
				if (isok) {
					succeeded++;
				}
			}
		}
		System.out.println(1.0d * succeeded / tried);
	}
}

Submission

Task問題 D - シャッフル席替え
User nameユーザ名 hama_du
Created time投稿日時
Language言語 Java (OpenJDK 1.7.0)
Status状態 AC
Score得点 100
Source lengthソースコード長 1639 Byte
File nameファイル名
Exec time実行時間 9567 ms
Memory usageメモリ使用量 30176 KB

Test case

Set

Set name Score得点 / Max score Cases
all 100 / 100 00_mini_01.txt,00_mini_02.txt,00_sample_01.txt,00_sample_02.txt,00_sample_03.txt,01_rnd_11_01.txt,01_rnd_11_02.txt,01_rnd_11_03.txt,01_rnd_11_04.txt,01_rnd_11_05.txt,01_rnd_11_06.txt,01_rnd_11_07.txt,01_rnd_11_08.txt,01_rnd_11_09.txt,01_rnd_11_10.txt,01_rnd_11_11.txt,01_rnd_11_12.txt,01_rnd_11_13.txt,01_rnd_11_14.txt,01_rnd_11_15.txt,01_rnd_11_16.txt,01_rnd_11_17.txt,01_rnd_11_18.txt,01_rnd_11_19.txt,01_rnd_11_20.txt,01_rnd_11_21.txt,01_rnd_11_22.txt,01_rnd_7_01.txt,01_rnd_7_02.txt,01_rnd_7_03.txt,01_rnd_7_04.txt,01_rnd_7_05.txt,01_rnd_7_06.txt,01_rnd_7_07.txt,01_rnd_7_08.txt,01_rnd_7_09.txt,01_rnd_7_10.txt,01_rnd_7_11.txt,01_rnd_7_12.txt,01_rnd_7_13.txt,01_rnd_7_14.txt,01_rnd_7_15.txt,01_rnd_7_16.txt,01_rnd_7_17.txt,01_rnd_7_18.txt,01_rnd_7_19.txt,01_rnd_7_20.txt,01_rnd_7_21.txt,01_rnd_7_22.txt,01_rnd_8_01.txt,01_rnd_8_02.txt,01_rnd_8_03.txt,01_rnd_8_04.txt,01_rnd_8_05.txt,01_rnd_8_06.txt,01_rnd_8_07.txt,01_rnd_8_08.txt,01_rnd_8_09.txt,01_rnd_8_10.txt,01_rnd_8_11.txt,01_rnd_8_12.txt,01_rnd_8_13.txt,01_rnd_8_14.txt,01_rnd_8_15.txt,01_rnd_8_16.txt,01_rnd_8_17.txt,01_rnd_8_18.txt,01_rnd_8_19.txt,01_rnd_8_20.txt,01_rnd_8_21.txt,01_rnd_8_22.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_mini_01.txt AC 9426 ms 28748 KB
00_mini_02.txt AC 9425 ms 29072 KB
00_sample_01.txt AC 9423 ms 29324 KB
00_sample_02.txt AC 9418 ms 28772 KB
00_sample_03.txt AC 9425 ms 30112 KB
01_rnd_11_01.txt AC 9429 ms 29136 KB
01_rnd_11_02.txt AC 9439 ms 29112 KB
01_rnd_11_03.txt AC 9418 ms 29100 KB
01_rnd_11_04.txt AC 9422 ms 29112 KB
01_rnd_11_05.txt AC 9446 ms 29184 KB
01_rnd_11_06.txt AC 9421 ms 29172 KB
01_rnd_11_07.txt AC 9421 ms 29096 KB
01_rnd_11_08.txt AC 9454 ms 29424 KB
01_rnd_11_09.txt AC 9424 ms 29028 KB
01_rnd_11_10.txt AC 9419 ms 29020 KB
01_rnd_11_11.txt AC 9427 ms 29072 KB
01_rnd_11_12.txt AC 9486 ms 29092 KB
01_rnd_11_13.txt AC 9424 ms 28824 KB
01_rnd_11_14.txt AC 9427 ms 29948 KB
01_rnd_11_15.txt AC 9429 ms 29108 KB
01_rnd_11_16.txt AC 9422 ms 29232 KB
01_rnd_11_17.txt AC 9451 ms 29196 KB
01_rnd_11_18.txt AC 9420 ms 29116 KB
01_rnd_11_19.txt AC 9433 ms 29112 KB
01_rnd_11_20.txt AC 9441 ms 29092 KB
01_rnd_11_21.txt AC 9433 ms 29184 KB
01_rnd_11_22.txt AC 9432 ms 29192 KB
01_rnd_7_01.txt AC 9456 ms 29472 KB
01_rnd_7_02.txt AC 9460 ms 29060 KB
01_rnd_7_03.txt AC 9431 ms 29072 KB
01_rnd_7_04.txt AC 9458 ms 29072 KB
01_rnd_7_05.txt AC 9427 ms 29176 KB
01_rnd_7_06.txt AC 9567 ms 29060 KB
01_rnd_7_07.txt AC 9515 ms 28756 KB
01_rnd_7_08.txt AC 9428 ms 28828 KB
01_rnd_7_09.txt AC 9505 ms 28648 KB
01_rnd_7_10.txt AC 9425 ms 28772 KB
01_rnd_7_11.txt AC 9423 ms 28736 KB
01_rnd_7_12.txt AC 9567 ms 28940 KB
01_rnd_7_13.txt AC 9466 ms 29200 KB
01_rnd_7_14.txt AC 9461 ms 29184 KB
01_rnd_7_15.txt AC 9416 ms 29048 KB
01_rnd_7_16.txt AC 9417 ms 29048 KB
01_rnd_7_17.txt AC 9421 ms 29276 KB
01_rnd_7_18.txt AC 9427 ms 28784 KB
01_rnd_7_19.txt AC 9428 ms 28796 KB
01_rnd_7_20.txt AC 9415 ms 28636 KB
01_rnd_7_21.txt AC 9448 ms 28632 KB
01_rnd_7_22.txt AC 9433 ms 29184 KB
01_rnd_8_01.txt AC 9426 ms 29044 KB
01_rnd_8_02.txt AC 9421 ms 29088 KB
01_rnd_8_03.txt AC 9423 ms 29548 KB
01_rnd_8_04.txt AC 9421 ms 29052 KB
01_rnd_8_05.txt AC 9423 ms 29112 KB
01_rnd_8_06.txt AC 9453 ms 29188 KB
01_rnd_8_07.txt AC 9458 ms 29084 KB
01_rnd_8_08.txt AC 9427 ms 29060 KB
01_rnd_8_09.txt AC 9420 ms 28660 KB
01_rnd_8_10.txt AC 9436 ms 28704 KB
01_rnd_8_11.txt AC 9440 ms 28736 KB
01_rnd_8_12.txt AC 9444 ms 29100 KB
01_rnd_8_13.txt AC 9450 ms 30176 KB
01_rnd_8_14.txt AC 9465 ms 29052 KB
01_rnd_8_15.txt AC 9427 ms 29180 KB
01_rnd_8_16.txt AC 9435 ms 29796 KB
01_rnd_8_17.txt AC 9414 ms 29104 KB
01_rnd_8_18.txt AC 9423 ms 29108 KB
01_rnd_8_19.txt AC 9419 ms 29048 KB
01_rnd_8_20.txt AC 9430 ms 29096 KB
01_rnd_8_21.txt AC 9421 ms 28832 KB
01_rnd_8_22.txt AC 9438 ms 28728 KB