#267299 (Java) No.43 野球の試合

• 問題: No.43 野球の試合
• ユーザー: YamaKasa
• 提出日時: 2018-06-20 01:30:56
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 308 ms / 5,000 ms
• コード長: 2,275 bytes
• コンパイル時間: 2,305 ms
• コンパイル使用メモリ: 78,904 KB
• 実行使用メモリ: 58,668 KB
• 最終ジャッジ日時: 2024-06-30 17:22:13
• 合計ジャッジ時間: 4,663 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
sample	AC * 4
other	AC * 7

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
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();
        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 = 0; 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]);
            }
        }
        int cnt3 = 0;
        for(int i = 1; i < N; i++) {
            if(a[0][i].equals("o")) {
                cnt3 ++;
            }
        }
        w0 = cnt3;
        for(int i = 0; i < list.size(); i++) {
            if(w0 >= list.get(i)) {
                return cnt2;
            }else {
                cnt2 ++;
            }
        }
        return list.size();
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX