結果

問題 No.43 野球の試合
コンテスト
ユーザー jp_ste
提出日時 2016-05-06 23:43:35
言語 Java
(openjdk 23)
結果
AC  
実行時間 427 ms / 5,000 ms
コード長 2,396 bytes
コンパイル時間 2,693 ms
コンパイル使用メモリ 83,436 KB
実行使用メモリ 53,684 KB
最終ジャッジ日時 2024-10-05 10:12:53
合計ジャッジ時間 4,298 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Comparator;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    static int N;
    static char list[][];
    
    public static void main(String[] args) {
        try (Scanner scan = new Scanner(System.in)) {
            N = scan.nextInt();
            list = new char[N][N];
            for(int i=0; i<N; i++) {
                String line = scan.next();
                list[i] = line.toCharArray();
            }
            
            int count = 0;
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    if(i<j && list[i][j] == '-') count++;   
                }
            }
            
            int ans = N;
            for(int i=0; i<Math.pow(2, count); i++) {
                String tmp = Integer.toBinaryString(i);
                int zeroNum = count - tmp.length();
                for(int j=0; j<zeroNum; j++) tmp = "o" + tmp;
                tmp = tmp.replace('0', 'o');
                tmp = tmp.replace('1', 'x');

                char tmpList[][] = new char[N][N];
                for(int j=0; j<N; j++) tmpList[j] = list[j].clone();
                
                int look = 0;
                for(int j=0; j<N; j++) {
                    for(int k=0; k<N; k++) {
                        if(j<k && tmpList[j][k] == '-') {
                            char now = tmp.charAt(look);
                            tmpList[j][k] = now;
                            if(now == 'o') tmpList[k][j] = 'x';
                            else           tmpList[k][j] = 'o';
                            look++;
                        }
                    }
                }
                
                int myTeam = getWinNum(0, tmpList);
                TreeSet<Integer> set = new TreeSet<>(Comparator.reverseOrder());
                for(int j=0; j<N; j++) {
                    set.add(getWinNum(j, tmpList));
                }

                int tmpAns = 0;
                for(Integer v : set) {
                    tmpAns++;
                    if(v == myTeam) break;
                }
                ans = Math.min(ans, tmpAns);
            }
            System.out.println(ans);
        }
    }
    
    static int getWinNum(int i, char list[][]) {
        int count = 0;
        for(int j=0; j<N; j++) {
            if(list[i][j] == 'o') count++;
        }
        return count;
    }
}
0