AtCoder Regular Contest 003

Submission #19160

Source codeソースコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
	public static class State implements Comparable<State> {
		int nx;
		int ny;
		int t;
		
		public State(int x, int y, int _t) {
			nx = x;
			ny = y;
			t = _t;
		}
		
		
		
		@Override
		public int compareTo(State arg0) {
			return t - arg0.t;
		}
	}
	
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
		String[] sz = s.readLine().split(" ");
		int N = Integer.valueOf(sz[0]);
		int M = Integer.valueOf(sz[1]);
		
		int[][] data = new int[N+2][M+2];
		int sx = 0, sy = 0;
		int gx = 0, gy = 0;
		for (int i = 0 ; i < N ; i++) {
			String line = s.readLine();
			for (int j = 0 ; j < M ; j++) {
				if (line.charAt(j) == 's') {
					data[i+1][j+1] = 11;
					sx = j+1;
					sy = i+1;
				} else if (line.charAt(j) == 'g') {
					data[i+1][j+1] = 12;
					gx = j+1;
					gy = i+1;
				} else if (line.charAt(j) == '#') {
				} else {
					data[i+1][j+1] = line.charAt(j) - '0';
				}
			}
		}
		
		
		double[][] dvalue = new double[10][5001];
		for (int v = 1 ; v <= 9 ; v++) {
			dvalue[v][0] = v;
			for (int t = 0 ; t < 5000 ; t++) {
				dvalue[v][t+1] = dvalue[v][t] * 99 / 100; 
			}
		}
		
		int time = -1;
		{
			Queue<State> q = new PriorityQueue<State>();
			q.add(new State(sx, sy, 0));
			boolean[][] visited = new boolean[N+2][M+2];
			visited[sy][sx] = true;
			while (q.size() >= 1) {
				State stat = q.poll();
				for (int d = 0 ; d < 4 ; d++) {
					int tx = (stat.nx + dx[d]);
					int ty = (stat.ny + dy[d]);
					int tt = stat.t + 1;
					int lightval = data[ty][tx];
					if (lightval == 11 || lightval == 0) {
						continue;
					}
					if (lightval == 12) {
						time = tt;
						break;
					}
					if (!visited[ty][tx]) {
						visited[ty][tx] = true;
						q.add(new State(tx, ty, tt));
					}
				}
			}
			if (time == -1) {
				System.out.println("-1");
				return;
			}
		}
		
		
		double max = 9.0d;
		double min = 0.0d;
		for (int cur = 0 ; cur < 300 ; cur++) {
			double med = (max + min) / 2.0d;
			if (Math.abs(min - med) < 10e-11) {
				break;
			}
			double[][] maxl = new double[N+2][M+2];
			for (int d = 0 ; d < N+2 ; d++) {
				Arrays.fill(maxl[d], 0.0d);
			}
			Queue<State> q = new PriorityQueue<State>();
			q.add(new State(sx, sy, 0));
			boolean isok = false;
			search: while (q.size() >= 1) {
				State stat = q.poll();
				for (int d = 0 ; d < 4 ; d++) {
					int tx = (stat.nx + dx[d]);
					int ty = (stat.ny + dy[d]);
					int tt = stat.t + 1;
					if (data[ty][tx] == 0) {
						continue;
					}
					if (tt >= 5000) {
						continue;
					}
					
					int lightval = data[ty][tx];
					if (lightval == 11) {
						continue;
					}
					if (lightval == 12) {
						isok = true;
						break search;
					}
					if (dvalue[lightval][tt] < med) {
						continue;
					}
					if (maxl[ty][tx] < dvalue[lightval][tt]) {
						maxl[ty][tx] = dvalue[lightval][tt];
						q.add(new State(tx, ty, tt));
					}
				}
			}
			if (isok) {
				min = med;
			} else {
				max = med;
			}
		}
		System.out.println(min);
	}
}

Submission

Task問題 C - 暗闇帰り道
User nameユーザ名 hama_du
Created time投稿日時
Language言語 Java (OpenJDK 1.7.0)
Status状態 AC
Score得点 100
Source lengthソースコード長 3469 Byte
File nameファイル名
Exec time実行時間 2479 ms
Memory usageメモリ使用量 51444 KB

Test case

Set

Set name Score得点 / Max score Cases
all 100 / 100 00_mini_01.txt,00_mini_02.txt,00_mini_03.txt,00_mini_04.txt,00_mini_05.txt,00_sample_01.txt,00_sample_02.txt,01_rnd_01.txt,01_rnd_02.txt,01_rnd_03.txt,01_rnd_04.txt,01_rnd_05.txt,01_rnd_06.txt,01_rnd_07.txt,01_rnd_08.txt,01_rnd_09.txt,01_rnd_10.txt,01_rnd_11.txt,01_rnd_12.txt,01_rnd_13.txt,01_rnd_14.txt,01_rnd_15.txt,01_rnd_16.txt,01_rnd_17.txt,01_rnd_18.txt,01_rnd_19.txt,01_rnd_20.txt,02_maxrnd_01.txt,02_maxrnd_02.txt,02_maxrnd_03.txt,02_maxrnd_04.txt,02_maxrnd_05.txt,02_maxrnd_06.txt,02_maxrnd_07.txt,02_maxrnd_08.txt,02_maxrnd_09.txt,02_maxrnd_10.txt,02_maxrnd_11.txt,02_maxrnd_12.txt,02_maxrnd_13.txt,02_maxrnd_14.txt,02_maxrnd_15.txt,02_maxrnd_16.txt,02_maxrnd_17.txt,02_maxrnd_18.txt,02_maxrnd_19.txt,03_hard_01.txt,03_hard_02.txt,03_hard_03.txt,03_hard_04.txt,03_hard_05.txt,03_hard_06.txt,03_hard_07.txt,03_hard_08.txt,04_open_01.txt,04_open_02.txt,05_minihard_01.txt,05_minihard_02.txt,05_minihard_03.txt,05_minihard_04.txt,05_minihard_05.txt,05_minihard_06.txt,05_minihard_07.txt,05_minihard_08.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_mini_01.txt AC 469 ms 21500 KB
00_mini_02.txt AC 462 ms 22856 KB
00_mini_03.txt AC 438 ms 22740 KB
00_mini_04.txt AC 449 ms 22820 KB
00_mini_05.txt AC 435 ms 20644 KB
00_sample_01.txt AC 434 ms 22956 KB
00_sample_02.txt AC 453 ms 22784 KB
01_rnd_01.txt AC 2125 ms 47168 KB
01_rnd_02.txt AC 752 ms 33944 KB
01_rnd_03.txt AC 624 ms 37036 KB
01_rnd_04.txt AC 657 ms 34200 KB
01_rnd_05.txt AC 565 ms 28396 KB
01_rnd_06.txt AC 509 ms 27264 KB
01_rnd_07.txt AC 612 ms 36360 KB
01_rnd_08.txt AC 810 ms 33584 KB
01_rnd_09.txt AC 989 ms 38392 KB
01_rnd_10.txt AC 1124 ms 35696 KB
01_rnd_11.txt AC 834 ms 33332 KB
01_rnd_12.txt AC 745 ms 32800 KB
01_rnd_13.txt AC 653 ms 37116 KB
01_rnd_14.txt AC 1307 ms 35736 KB
01_rnd_15.txt AC 859 ms 33400 KB
01_rnd_16.txt AC 579 ms 34788 KB
01_rnd_17.txt AC 509 ms 25412 KB
01_rnd_18.txt AC 440 ms 23660 KB
01_rnd_19.txt AC 466 ms 23956 KB
01_rnd_20.txt AC 705 ms 23156 KB
02_maxrnd_01.txt AC 1021 ms 43644 KB
02_maxrnd_02.txt AC 884 ms 40400 KB
02_maxrnd_03.txt AC 1066 ms 43736 KB
02_maxrnd_04.txt AC 1461 ms 48640 KB
02_maxrnd_05.txt AC 1067 ms 42336 KB
02_maxrnd_06.txt AC 2213 ms 51012 KB
02_maxrnd_07.txt AC 757 ms 39216 KB
02_maxrnd_08.txt AC 696 ms 38028 KB
02_maxrnd_09.txt AC 2213 ms 50928 KB
02_maxrnd_10.txt AC 864 ms 38292 KB
02_maxrnd_11.txt AC 2027 ms 51264 KB
02_maxrnd_12.txt AC 1263 ms 48040 KB
02_maxrnd_13.txt AC 1503 ms 47928 KB
02_maxrnd_14.txt AC 1649 ms 49572 KB
02_maxrnd_15.txt AC 790 ms 35556 KB
02_maxrnd_16.txt AC 1358 ms 45688 KB
02_maxrnd_17.txt AC 1106 ms 45924 KB
02_maxrnd_18.txt AC 517 ms 25880 KB
02_maxrnd_19.txt AC 483 ms 25724 KB
03_hard_01.txt AC 2255 ms 50560 KB
03_hard_02.txt AC 2333 ms 50944 KB
03_hard_03.txt AC 610 ms 38192 KB
03_hard_04.txt AC 660 ms 40596 KB
03_hard_05.txt AC 2271 ms 50860 KB
03_hard_06.txt AC 2328 ms 50892 KB
03_hard_07.txt AC 607 ms 38576 KB
03_hard_08.txt AC 624 ms 36804 KB
04_open_01.txt AC 2479 ms 51116 KB
04_open_02.txt AC 2412 ms 51444 KB
05_minihard_01.txt AC 513 ms 26164 KB
05_minihard_02.txt AC 500 ms 27796 KB
05_minihard_03.txt AC 492 ms 27108 KB
05_minihard_04.txt AC 511 ms 27788 KB
05_minihard_05.txt AC 512 ms 25760 KB
05_minihard_06.txt AC 496 ms 26288 KB
05_minihard_07.txt AC 502 ms 28020 KB
05_minihard_08.txt AC 501 ms 28696 KB