山傘のプログラミング勉強日記[Java & Unity]

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[yukicoder] No.43 野球の試合

負けるが勝ち?

No.43 野球の試合 - yukicoder

f:id:yamakasa3:20180620013528p:plain

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

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

勝つか負けるかの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();
    }
}