結果

問題 No.43 野球の試合
コンテスト
ユーザー YamaKasa
提出日時 2018-06-20 01:26:05
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 2,361 bytes
コンパイル時間 2,240 ms
コンパイル使用メモリ 78,684 KB
実行使用メモリ 54,544 KB
最終ジャッジ日時 2024-06-30 17:22:03
合計ジャッジ時間 4,509 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 6 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int rank;
	static String [][]s;
	static int N;
	static int w0;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		s = new String[N][N];
		String []S = new String[N];
		for(int i = 0; i < N; i++) {
			S[i] = scan.next();
		}
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				s[i][j] = S[i].substring(j, j + 1);
			}
		}
		scan.close();
		for(int i = 1; i < N; i++) {
			if(s[0][i].equals("-")) {
				s[0][i] = "o";
				s[i][0] = "x";
			}
		}
		w0 = 0;
		for(int i = 1; i < N; i++) {
			if(s[0][i].equals("o")) {
				w0 ++;
			}
		}

		int n = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(s[i][j].equals("-")) {
					n ++;
				}
			}
		}
		n = n / 2;
		rank = N;
		int []bit = new int[n];
        Arrays.fill(bit, 0);
        rec(0, n, bit);
        System.out.println(rank);
	}
	public static void copy(int n, String[][] s, String[][] a) {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				a[i][j] = s[i][j];
			}
		}
	}
	public static void rec(int k, int n, int[] S) {
        if(k == n) {
            int t = solve(S);
            if(rank > t) {
            	rank = t;
            }
            return;
        }
        rec(k + 1, n, S);
        S[k] = 1;
        rec(k + 1,n, S);
        S[k] = 0;
    }
	public static int solve(int[] S) {
		String [][]a = new String[N][N];
		copy(N, s, a);
		int cnt = 0;
		for(int i = 1; i < N; i++) {
			for(int j = 0; j <= i - 1; j++) {
				if(a[i][j].equals("-")) {
					if(S[cnt] == 0) {
						a[i][j] = "o";
						a[j][i] = "x";
						cnt ++;
					}else {
						a[i][j] = "x";
						a[j][i] = "o";
						cnt ++;
					}
				}
			}
		}
		int []win = new int[N];
		int cnt1 = 0;
		for(int i = 0; i < N; i++) {
			cnt1 = 0;
			for(int j = 0; j < N; j++) {
				if(a[i][j].equals("o")) {
					cnt1 ++;
				}
			}
			win[i] = cnt1;
		}
		Arrays.sort(win);
		int cnt2 = 1;
		ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(win[N - 1]);
		for(int i = N - 1; i >= 1; i--) {
			if(win[i] > win[i - 1]) {
				list.add(win[i - 1]);
			}
		}
		for(int i = 0; i < list.size(); i++) {
			if(w0 >= list.get(i)) {
				return cnt2;
			}else {
				cnt2 ++;
			}
		}
		return list.size();
    }
}
0