結果

問題 No.359 門松行列
ユーザー 37zigen37zigen
提出日時 2016-05-31 01:29:34
言語 Java21
(openjdk 21)
結果
AC  
実行時間 228 ms / 2,000 ms
コード長 4,372 bytes
コンパイル時間 2,486 ms
コンパイル使用メモリ 80,680 KB
実行使用メモリ 43,336 KB
最終ジャッジ日時 2024-10-07 20:07:16
合計ジャッジ時間 6,701 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 132 ms
41,216 KB
testcase_01 AC 131 ms
41,416 KB
testcase_02 AC 133 ms
41,448 KB
testcase_03 AC 196 ms
42,580 KB
testcase_04 AC 158 ms
41,824 KB
testcase_05 AC 196 ms
42,284 KB
testcase_06 AC 143 ms
41,560 KB
testcase_07 AC 195 ms
42,276 KB
testcase_08 AC 222 ms
43,336 KB
testcase_09 AC 228 ms
43,100 KB
testcase_10 AC 221 ms
43,192 KB
testcase_11 AC 219 ms
43,144 KB
testcase_12 AC 220 ms
42,872 KB
testcase_13 AC 207 ms
42,740 KB
testcase_14 AC 204 ms
43,024 KB
testcase_15 AC 219 ms
43,088 KB
testcase_16 AC 216 ms
42,808 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		new Main().solve();
//		 new Q359().naive();
	}

	void naive() {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int i = 0; i < T; i++) {
			int[][] table = new int[3][3];
			int L = sc.nextInt();
			int x1 = -1;
			int y1 = -1;
			int x2 = -1;
			int y2 = -1;
			for (int j = 0; j < 3; j++) {
				for (int k = 0; k < 3; k++) {
					table[j][k] = sc.nextInt();
					if (table[j][k] == 0) {
						if (x1 == -1 && y1 == -1) {
							x1 = k;
							y1 = j;
						} else {
							x2 = k;
							y2 = j;
						}
					}
				}
			}
			int sum = 0;
			ArrayList<Integer> ans=new ArrayList<>();
			for (int j = 1; j < L; j++) {
				int[][] d = table;
				d[y1][x1] = j;
				d[y2][x2] = L - j;
				if (ok(d)) {
					sum++;
					ans.add(d[y1][x1]);
				}
			}
			ans.sort(new Comparator<Integer>(){
				@Override
				public int compare(Integer o1, Integer o2) {
					return Integer.compare(o1, o2);
				}
			});
//			for(int j=0;j<ans.size();j++){
//				System.out.println(ans.get(j));
//			}
			System.out.println(sum);
		}
	}

	void solve() {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int i = 0; i < T; i++) {
			ArrayList<Singularity> singu = new ArrayList<>();
			ArrayList<Integer> checked = new ArrayList<>();
			int L = sc.nextInt();
			int[][] table = new int[3][3];
			int x1 = -1;
			int y1 = -1;
			int x2 = -1;
			int y2 = -1;
			ArrayList<Integer> cand = new ArrayList<>();

			for (int j = 0; j < 3; j++) {
				for (int k = 0; k < 3; k++) {
					table[j][k] = sc.nextInt();
					if (table[j][k] == 0) {
						if (x1 == -1 && y1 == -1) {
							x1 = k;
							y1 = j;
						} else {
							x2 = k;
							y2 = j;
						}
					} else {
						cand.add(table[j][k]);
					}
				}
			}
			cand.add(L/2);
			cand.add(0);
			cand.add(L);
			for (int j = 0; j < cand.size(); j++) {
				singu = add_singu(cand.get(j), table, x1, y1, x2, y2, L, singu, checked);
			}
			singu.sort(new Comparator<Singularity>() {
				@Override
				public int compare(Singularity o1, Singularity o2) {
					return Integer.compare(o1.num, o2.num);
				}
			});
//			for(int j=0;j<singu.size();j++){
//				System.out.println(singu.get(j).num+" "+singu.get(j).isKado);
//			}
			int sum = 0;
			for (int j = 0; j < singu.size(); j++) {
				if (singu.get(j).isKado) {
					if (j + 1 < singu.size() && singu.get(j + 1).isKado) {
						int pre = j;
						while (j + 1 < singu.size() && singu.get(j + 1).isKado)
							j++;
						sum += singu.get(j).num - singu.get(pre).num + 1;
					} else {
						sum++;
					}
					j++;
				}
			}
			System.out.println(sum);
		}
	}

	boolean isKaramatsu(int a, int b, int c) {
		if (a <= 0 || b <= 0 || c <= 0)
			return false;
		if (a == b || b == c || c == a)
			return false;
		if (a < b && b > c)
			return true;
		if (a > b && b < c)
			return true;
		return false;
	}

	boolean ok(int[][] table) {
		for (int i = 0; i < 3; i++) {
			if (!isKaramatsu(table[i][0], table[i][1], table[i][2])) {
				return false;
			}
			if (!isKaramatsu(table[0][i], table[1][i], table[2][i])) {
				return false;
			}
		}
		if (!isKaramatsu(table[0][0], table[1][1], table[2][2])) {
			return false;
		}
		if (!isKaramatsu(table[0][2], table[1][1], table[2][0])) {
			return false;
		}
		return true;
	}

	class Singularity {
		int num;
		boolean isKado;

		Singularity(int num, boolean isKado) {
			this.num = num;
			this.isKado = isKado;
		}
	}

	ArrayList add_singu(int x, int[][] table, int x1, int y1, int x2, int y2, int L, ArrayList singu, ArrayList used) {
		int[][] d = table;
		for (int l = 0; l < 3; l++) {
			int dd = 1;
			d[y1][x1] = x + (l == 0 ? dd : l == 1 ? -dd : 0);
			d[y2][x2] = L - d[y1][x1];
			if (!used.contains(d[y1][x1])) {
				singu.add(new Singularity(d[y1][x1], ok(d)));
				used.add(d[y1][x1]);
			}
		}
		for (int l = 0; l < 3; l++) {
			int dd = 1;
			d[y2][x2] = x + (l == 0 ? dd : l == 1 ? -dd : 0);
			d[y1][x1] = L - d[y2][x2];
			if (!used.contains(d[y1][x1])) {
				singu.add(new Singularity(d[y1][x1], ok(d)));
				used.add(d[y1][x1]);
			}
		}
		return singu;
	}
	// void showMt(int[][] table){
	// for(int i=0;i<3;i++){
	// for(int j=0;j<3;j++){
	// System.out.print(table[i][j]+(j!=2?" ":"\n"));
	// }
	// }
	// }
}
0