[白俊]#3980選抜リスト

質問する

サッカーの欧州チャンピオンズリーグ決勝進出を決めたマンチェスター・ユナイテッドのファーガソン監督は、今大会で4−2のダイヤモンド戦術を駆使する.
今日の決勝戦の11人の先発選手は事前に選ばれたが、どの選手をどの位置に配置すべきかはまだ決まっていない.
マイク・ペラン首席コーチは、11人の選手のそれぞれのポジションでの能力を0から100の整数に量子化した.0はその選手がその位置に合わないことを示している.
このとき、すべての選手の位置を決めるプログラムを作成してください.すべてのポジションは選手を配置し、各選手は能力値が0のポジションに配置できない.

入力

入力は、複数のテスト・インスタンスから構成されます.第1行は、試験例の個数Cを与える.各キャビネットは11行で構成され、i番のパッケージには0と100の間の11個の整数sijが含まれています.sijはi番選手がj番ポジションで走るときの能力です.全選手にふさわしいポジションは最大5つ.(コンピテンシー値が0より大きい)

しゅつりょく

各テストケースについて、すべてのポジションの選手が満たされると、能力値の和の最値が出力されます.常に1つ以上の正しいラインナップを創造することができます.

入力例1

1
100 0 0 0 0 0 0 0 0 0 0
0 80 70 70 60 0 0 0 0 0 0
0 40 90 90 40 0 0 0 0 0 0
0 40 85 85 33 0 0 0 0 0 0
0 70 60 60 85 0 0 0 0 0 0
0 0 0 0 0 95 70 60 60 0 0
0 45 0 0 0 80 90 50 70 0 0
0 0 0 0 0 40 90 90 40 70 0
0 0 0 0 0 0 50 70 85 50 0
0 0 0 0 0 0 66 60 0 80 80
0 0 0 0 0 0 50 50 0 90 88

サンプル出力1

970

に答える

この問題はdfs(深さ優先探索)アルゴリズムで解くことができる.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    static ArrayList<Pos>[] list;
    static int ans;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i=0; i<T; i++) {
            list = new ArrayList[11];
            for(int j=0; j<11; j++)
                list[j] = new ArrayList<>();
            ans = Integer.MIN_VALUE;

            for(int j=0; j<11; j++) {
                String[] input = br.readLine().split(" ");
                for(int k=0; k<11; k++) {
                    int x = Integer.parseInt(input[k]);
                    if(x>0)
                        list[j].add(new Pos(x, k));
                }
            }
            dfs(new int[11], 0);

            System.out.println(ans);
        }
    }

    public static void dfs(int[] score, int num) {
        if(num==11) {
            boolean flag = false;
            int sum = 0;
            for(int idx=0; idx<11; idx++) {
                if(score[idx]!=0)
                    sum += score[idx];
                else {
                    flag = true;
                    break;
                }
            }

            if(!flag)
                ans = Math.max(sum, ans);

            return;
        }

        for(int i=0; i<list[num].size(); i++) {
            Pos temp = list[num].get(i);

            if(score[temp.idx]==0) {
                score[temp.idx] = temp.x;
                dfs(score, num+1);
                score[temp.idx] = 0;
            }
        }
    }

    public static class Pos{
        int x;
        int idx;

        public Pos(int x, int idx){
            this.x = x;
            this.idx = idx;
        }
    }
}