⚾ (17281)


1.質問


質問リンク
説明:
⑦は9人で構成された両チームが交互に攻撃と守備を行うゲーム.1セットは攻撃と守備で構成され、全部でNセットの試合が行われる.1セット3アウト、1セット終了、両チームは攻撃を変えて守備を変えた.
両チームは試合開始前に打順(打席での打順)を決め、試合中に打順を変更することはできない.9番まで3アウトが出なければ、このイニングは終わらず、1番打者は再び打席に立った.打者は局が変わっても順番を守らなければならない.例えば、2回6番が最後の打者なら、3回7番から打席に立つ.
攻撃は打者が投手の投げたボールを打席に打つ打者である.攻撃チームの選手は1塁、2塁、3塁を経てホームに着いて1点を得点した.打者はホームに届かず、一塁、二塁、三塁の一つにとどまるしかない.塁にいる選手をランナーと言います.序盤はランナーがいなかった.
打者が打てる結果は安打、二塁打、三塁打、本塁打、アウトの一つだった.別れたとき、起こったことは以下の通りです.
  • 安打:打者とすべてのランナーが1塁ずつ入る.
  • 2塁打:打者とすべてのランナーが2塁に入る.
  • 3塁打:打者とすべてのランナーが三塁に進出した.
  • 本塁打:打者とすべてのランナーがホームに入る.
  • アウト:すべてのランナーが塁に入ることができず、攻撃チームは1アウト増加した.
  • ある野球チームのアインタ監督は打順を決めるつもりだ.アインタの選手は全部で9人で、番号は1番から9番までです.アインタは自分の大好きな1番を4番に選ぶことにした.今は他の選手の打順を決めなければならない.アインタは選手一人一人が試合ごとにどのような結果を得るかを事前に知っていた.最多得点の打順を見つけ、その時の得点を求める.
    入力
    第1行は整数N(2≦N≦50)を与える.2行目からN行目まで、各選手が各局で得た結果は1番局からN番局の順であった.このセットで得られた結果は9つの整数が空白に分けられた.各結果の整数は次のとおりです.
  • 安打:1
  • 2サンタクロース:
  • 3安打:324579182
  • 本塁打:4
  • アウト:024579182
    各局には少なくとも1人のアウトになった人がいる.
    しゅつりょく
    アインタチームが獲得できる最大点数を出力します.

    2.解答


    2-1. 条件

  • 1番は4番打者に固定されている.
  • 2-2. に答える


    さすがに典型的な三星機の問題提起スタイルDFSで選手を配置するすべての場合の数.시뮬레이션を行い、点数の最値を出します.
    計画1-すべての状況で配置された選手の数を作成します.
    for (int i = 1; i < 9; i++) {
    	if (positioned[i]) continue;
    	
    	positioned[i] = true;
    	player[depth] = i;
    	ret = Math.max(ret, max(depth + 1, player, positioned));
    	player[depth] = 0;
    	positioned[i] = false;
    }
    1番が4番に固定されているため、(0번 인덱스 제외)を除く
    打者を決めるたびに2~9番で選手を決める方式でコードを書けばよい.
    2−4番を計画した瞬間が過ぎた.
    // 4번 타자는 1번 선수로 고정돼있기 때문에 다음 5번 타자를 결정하는 재귀로 넘깁니다. 
    if (depth == 3) return max(depth + 1, player, positioned);
    計画3-野球のシミュレーションゲーム.
    // 기저 사례 - 9명의 선수를 모두 배치했을 때
    if (depth == 9) {
    	// 야구 시뮬레이션 진행
    	int outCnt = 0;
    	int curPlayer = player[0];
    	int cursor = 0;
    	int score = 0;
    	int[] field = {0, 0, 0, 0};
    	
    	for (int i = 0; i < N; i++) { 
    		while (true) {
    			int result = M[i][curPlayer]; // player의 결과
    			
    			if (result == 0) {
    				// 선수 교체
    				curPlayer = player[++cursor % 9];
    				
    				// 3아웃일시 이닝 종료
    				if (++outCnt >= 3)  break;
    					
    				continue;
    			}
    			
    			// 필드에 나가있는 선수들 재배치 및 점수 계산
    			for (int j = 3; j >= 1; j--) {
    				if (field[j] > 0) {
    					field[j] = 0;
    					
    					if (j + result > 3) score++;
    					else field[j + result] = 1;
    				}
    			}
    			
    			if (result == 4) score++; // 홈런
    			else field[result] = 1; // 안타
    			
    			curPlayer = player[++cursor % 9]; // 플레이어 교체
    		}
    		
    		// 주요 변수들 초기화
    		for (int j = 1; j <= 3; j++) field[j] = 0;
    		outCnt = 0;
    	}
    	
    	return score;
    }
    何か特別なものがありますか.質問の通り野球ゲームを実施すればいいです.

    3.完全なコード

    import java.io.BufferedReader;
    import java.io.BufferedWriter;
    import java.io.InputStreamReader;
    import java.io.OutputStreamWriter;
    
    public class Main {
    	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	static int N, M[][], MIN = -987654321;
    	
    	static int max(int depth, int[] player, boolean[] positioned) {
    		// 기저 사례 - 9명의 선수를 모두 배치했을 때
    		if (depth == 9) {
    			// 야구 시뮬레이션 진행
    			int outCnt = 0;
    			int curPlayer = player[0];
    			int cursor = 0;
    			int score = 0;
    			int[] field = {0, 0, 0, 0};
    			
    			for (int i = 0; i < N; i++) { 
    				while (true) {
    					int result = M[i][curPlayer]; // player의 결과
    					
    					if (result == 0) {
    						// 선수 교체
    						curPlayer = player[++cursor % 9];
    						
    						// 3아웃일시 이닝 종료
    						if (++outCnt >= 3)  break;
    							
    						continue;
    					}
    					
    					// 필드에 나가있는 선수들 재배치 및 점수 계산
    					for (int j = 3; j >= 1; j--) {
    						if (field[j] > 0) {
    							field[j] = 0;
    							
    							if (j + result > 3) score++;
    							else field[j + result] = 1;
    						}
    					}
    					
    					if (result == 4) score++; // 홈런
    					else field[result] = 1; // 안타
    					
    					curPlayer = player[++cursor % 9]; // 플레이어 교체
    				}
    				
    				// 주요 변수들 초기화
    				for (int j = 1; j <= 3; j++) field[j] = 0;
    				outCnt = 0;
    			}
    			
    			return score;
    		}
    		
    		// 4번 타자는 1번 선수로 고정돼있기 때문에 다음 5번 타자를 결정하는 재귀로 넘깁니다. 
    		if (depth == 3) return max(depth + 1, player, positioned);
    		
    		int ret = MIN;
    		
    		for (int i = 1; i < 9; i++) {
    			if (positioned[i]) continue;
    			
    			positioned[i] = true;
    			player[depth] = i;
    			ret = Math.max(ret, max(depth + 1, player, positioned));
    			player[depth] = 0;
    			positioned[i] = false;
    		}
    			
    		return ret;
    	}
    	
    	public static void main(String[] args) throws Exception {
    		N = Integer.parseInt(br.readLine());
    		M = new int[N][9];
    		
    		int[] player = new int[9];
    		
    		for (int i = 0; i < N; i++) {
    			String[] s = br.readLine().split(" ");
    			for (int j = 0; j < 9; j++)
    				M[i][j] = Integer.parseInt(s[j]);
    		}
    		
         		// 4번 타자는 1번 플레이어로 고정
    		player[3] = 0;
    		
    		bw.write(max(0, player,  new boolean[9]) + "");
    		bw.close();
    	}
    }