[yukicoder] No.43 野球の試合

負けるが勝ち？

No.43 野球の試合 - yukicoder

問題をみてまさか全探索じゃないよなと思ったんですが、全探索の問題でした。

問題文の順位付けの規則ですと、負けた方が順位が上になるケースがあるみたいです。

勝つか負けるかの2通りなので、ビット配列を利用して全探索しました。

最初、チーム0の未確定な試合を全て勝ちとして解いていたんですが、思わぬ落とし穴がありました。それは、この記事の見出しの通りで、負けた方が順位が上になるケースがあるということです。

テストケースに関心させられました。

以下酷いコード。リーダブルコードとは・・・。

コード

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

public class Exec0043 {
    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();
    }
}