#19965 (Java21) No.43 野球の試合

• 問題: No.43 野球の試合
• ユーザー: t8m8⛄️
• 提出日時: 2015-04-16 18:54:39
• 言語: Java21 (openjdk 21)
• 結果: AC
• 実行時間: 155 ms / 5,000 ms
• コード長: 5,429 bytes
• コンパイル時間: 4,022 ms
• コンパイル使用メモリ: 77,236 KB
• 実行使用メモリ: 54,056 KB
• 最終ジャッジ日時: 2023-09-17 20:55:11
• 合計ジャッジ時間: 5,771 ms
• ジャッジサーバーID （参考情報）: judge14 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	43 ms; 49,476 KB
testcase_01	AC	43 ms; 49,608 KB
testcase_02	AC	42 ms; 49,596 KB
testcase_03	AC	44 ms; 49,548 KB
testcase_04	AC	43 ms; 49,528 KB
testcase_05	AC	43 ms; 49,456 KB
testcase_06	AC	47 ms; 49,604 KB
testcase_07	AC	155 ms; 54,056 KB
testcase_08	AC	46 ms; 47,712 KB
testcase_09	AC	46 ms; 49,576 KB
testcase_10	AC	45 ms; 49,764 KB

ソースコード

//No.43 野球の試合

import java.util.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.lang.Math.*;

public class No43 {

    static final Reader in = new Reader();
    static final PrintWriter out = new PrintWriter(System.out,false);

    static void solve(){
        int n = in.nextInt();
        int[] ord = new int[n];
        Integer[] team = new Integer[n];
        char[][] cs = new char[n][n];
        ArrayList<int[]> list = new ArrayList<>();

        for (int i=0; i<n; i++) {
            team[i] = i;
            cs[i] = in.next().toCharArray();
            for (int j=0; j<n; j++) {
                if (cs[i][j] == 'o') ord[i]++;
                if (i >= j) continue;
                if (cs[i][j] == '-') list.add(new int[]{i,j});
            }
        }

        Comparator<Integer> COMPARATOR = new Comparator<Integer>(){
            public int compare(Integer a, Integer b) {
                if (ord[a] != ord[b]) return ord[b] - ord[a];
                return a == 0 ? -1 : (b == 0 ? 1 : a - b);
            }
        };

        int m = list.size();
        int min = Integer.MAX_VALUE;

        for (int i=0; i<1<<m; i++) {
            int[] t = ord.clone();
            for (int j=0; j<m; j++) {
                int[] x = list.get(j);
                if ((i>>j&1) == 1) {
                    ord[x[0]]++;
                }else {
                    ord[x[1]]++;
                }
            }
            sort(team,COMPARATOR);
            int cnt = 1, zero = -1;
            for (int j=0; j<n; j++) {
                if (j != 0 && ord[team[j-1]] != ord[team[j]]) cnt++;
                if (team[j] == 0) zero = cnt;
                ord[j] = t[j];
            }
            min = min(min,zero);
        }

        out.println(min);
    }

    public static final Comparator<Integer> COMPARATOR = new Comp();
    
    private static class Comp implements Comparator<Integer>{
        public int compare(Integer x,Integer y){
            return (x > y) ? 1 : ((x == y) ? 0 : -1);
        }
    }

    public static void main(String[] args) throws Exception {
        long start = System.currentTimeMillis();

        solve();
        out.flush();

        long end = System.currentTimeMillis();
        //trace(end-start + "ms");
        in.close();
        out.close();
    }

    static void trace(Object... o) { System.out.println(deepToString(o));}
}

class Reader {
    private final InputStream in;
    private final byte[] buf = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    public Reader() { this(System.in);}
    public Reader(InputStream source) { this.in = source;}

    private boolean hasNextByte() {
        if (ptr < buflen) return true;
        ptr = 0;
        try{
            buflen = in.read(buf);
        }catch (IOException e) {e.printStackTrace();}
        if (buflen <= 0) return false;
        return true;
    }

    private int readByte() { if (hasNextByte()) return buf[ptr++]; else return -1;}

    private boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}

    private void skip() { while(hasNextByte() && !isPrintableChar(buf[ptr])) ptr++;}

    public boolean hasNext() {skip(); return hasNextByte();}

    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        boolean minus = false;
        long num = readByte();

        if(num == '-'){
            num = 0;
            minus = true;
        }else if (num < '0' || '9' < num){
            throw new NumberFormatException();
        }else{
            num -= '0';
        }
        
        while(true){
            int b = readByte();
            if('0' <= b && b <= '9')
                num = num * 10 + (b - '0');
            else if(b == -1 || !isPrintableChar(b))
                return minus ? -num : num;
            else
                throw new NoSuchElementException();
        }
    }

    public int nextInt() {
        long num = nextLong();
        if (num < Integer.MIN_VALUE || Integer.MAX_VALUE < num)
            throw new NumberFormatException();
        return (int)num;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public char nextChar() {
        if (!hasNext()) throw new NoSuchElementException();
        return (char)readByte();
    }

    public String nextLine() {
        while (hasNextByte() && (buf[ptr] == '\n' || buf[ptr] == '\r')) ptr++;
        if (!hasNextByte()) throw new NoSuchElementException();

        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (b != '\n' && b != '\r') {
            sb.appendCodePoint(b);
            b = readByte();
        }

        return sb.toString();
    }

    public int[] nextIntArray(int n) {
        int[] res = new int[n];
        for (int i=0; i<n; i++) res[i] = nextInt();
        return res;
    }

    public char[] nextCharArray(int n) {
        char[] res = new char[n];
        for (int i=0; i<n; i++) res[i] = nextChar();
        return res;
    }

    public void close() {try{ in.close();}catch(IOException e){ e.printStackTrace();}};
}