白駿20056号:魔法使いサメと火球





問題の説明
  • メッシュの行と列は1からN番号、1行はN番号、1列はN番号に関連付けられます.
  • 	moduler연산이 필요하단 뜻입니다.
  • 火の玉の方向は、ある格子に隣接する8つの格子の方向を意味し、整数は:
  • 	static int[] dx = {-1,-1,0,1,1,1,0,-1};
    	static int[] dy = {0,1,1,1,0,-1,-1,-1};
  • 法師サメがすべての火球を移動させると、次のようなことが起こります.
  • 	주어진 조건대로 구현을 진행해야 합니다.
    方法
  • すべての火球は移動後に分割されるため、同じアレイナビゲーションで一度に処理することはできない.
  • 動作を実行する2つのドアはいずれも回転し、分割された2つのドアは回転する.
  • pseudocode
    2차원 배열 board가 list를 담고 있음.
    list에는 fireball 객체가 들어감.
    board = [[list()],[list(fball1,fball2)],
    		[list(fball3)],[list()]] 
    
    for(K){
    	move();
        split();
    }
    move(){
    	for(board전체를 탐색하면서){
        	if(해당 칸의 list가 비었으면) continue;
            for(해당 칸의 list 크기만큼){
            	if(이번턴에 아직 안움직인 파이어볼이면){
                    f = 해당 칸의 list에서 pollFirst();
                    nx = (현재row + (방향 * 속도))%N;
                    ny = (현재col + (방향 * 속도))%N;
    			}
            }
            board[nx][ny]에 f를 이동        
        }
    }
    split(){
    	for(board전체를 탐색하면서){
        	if(해당 칸의 list가 비었으면)continue;
            if(해당 칸에 파이어볼이 하나만 있으면){
            	다음턴에 움직일 수 있게 can_move true로 설정
            }else{ // 해당 칸에 파이어볼이 둘 이상이면
            	질량,속도,방향을 모두 합침.
                if(모든 d가 홀수거나 모든 d가 짝수면){
                	질량을 /5만큼, 속도를 /합친개수 만큼 가진 0,2,4,6방향의 파이어볼 4개 생성
                }else{
                	질량을 /5만큼, 속도를 /합친개수 만큼 가진 1,3,5,7방향의 파이어볼 4개 생성   
                }
            }
        }
    }
    
    正解
    import java.io.*;
    import java.util.*;
    
    public class Main {
    	static int[] dx = { -1, -1, 0, 1, 1, 1, 0, -1 };
    	static int[] dy = { 0, 1, 1, 1, 0, -1, -1, -1 };
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int N = sc.nextInt();
    		int M = sc.nextInt();
    		int K = sc.nextInt();
    		Deque<fireball>[][] board = new Deque[N][N];
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < N; j++) {
    				board[i][j] = new LinkedList<fireball>();
    			}
    		}
    		// 최초 M개의 파이어볼을 생성합니다.
    		for (int i = 0; i < M; i++) {
    			int x = sc.nextInt();
    			int y = sc.nextInt();
    			int m = sc.nextInt();
    			int s = sc.nextInt();
    			int d = sc.nextInt();
    			board[x - 1][y - 1].addLast(new fireball(x - 1, y - 1, m, s, d, true));
    
    		}
    
    		// K번 움직이고 분열합니다.
    		for (int k = 0; k < K; k++) {
    			move(N, board);
    			split(N, board);
    		}
    
    		// 최종 점수를 계산합니다.
    		int score = 0;
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < N; j++) {
    				if (board[i][j].size() == 0)
    					continue;
    				int size = board[i][j].size();
    				for (int t = 0; t < size; t++) {
    					fireball val = board[i][j].poll();
    					score += val.m;
    				}
    			}
    		}
    		System.out.println(score);
    
    	}
    
    	public static void split(int N, Deque<fireball> board[][]) {
    		// move 후 모든 board칸에 대해 검사를 진행합니다.
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < N; j++) {
    				if (board[i][j].size() == 0)
    					continue; // 파이어볼이 없는 칸은 지나갑니다.
    				if (board[i][j].size() == 1) { // 파이어볼이 하나만 있는 칸은 split하지 않고 다음번에 움직일 수 있게 can_move만 변경해 줍니다.
    					fireball f = board[i][j].pollFirst();
    					f.can_move = true;
    					board[i][j].addLast(f);
    				} else {
    
    					int sumM = 0;
    					int sumS = 0;
    					int sumD = 0;
    					int oddEven = board[i][j].peekFirst().d;
    					boolean token = false;
    					int size = board[i][j].size();
    					for (int l = 0; l < size; l++) {
    						fireball f = board[i][j].pollFirst();
    						sumM += f.m;
    						sumS += f.s;
    						sumD += f.d;
    						if (!token && f.d % 2 != oddEven % 2) { // 모든 d의 합이 짝수면 될 거라 생각했는데 아니였습니다(반례 - 1+1+2 = 4로 짝수지만 모든 수가 홀수 or 짝수 X)
    							token = true;
    						}
    					}
    					if (sumM / 5 == 0) {
    						// 소멸
    					} else if (!token) { // 모든 d가 홀수거나 짝수면
    						board[i][j].addLast(new fireball(i, j, sumM / 5, sumS / size, 0, true));
    						board[i][j].addLast(new fireball(i, j, sumM / 5, sumS / size, 2, true));
    						board[i][j].addLast(new fireball(i, j, sumM / 5, sumS / size, 4, true));
    						board[i][j].addLast(new fireball(i, j, sumM / 5, sumS / size, 6, true));
    					} else {
    						board[i][j].addLast(new fireball(i, j, sumM / 5, sumS / size, 1, true));
    						board[i][j].addLast(new fireball(i, j, sumM / 5, sumS / size, 3, true));
    						board[i][j].addLast(new fireball(i, j, sumM / 5, sumS / size, 5, true));
    						board[i][j].addLast(new fireball(i, j, sumM / 5, sumS / size, 7, true));
    					}
    				}
    
    			}
    		}
    
    	}
    
    	public static void move(int N, Deque<fireball> board[][]) {
    		// board에 있는 모든 fireball을 움직입니다.
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < N; j++) {
    				if (board[i][j].size() == 0)
    					continue; // fireball이 없는 칸은 패스합니다.
    				int size = board[i][j].size();
    				for (int t = 0; t < size; t++) { // poll로
    					if (board[i][j].peekFirst().can_move) { // 움직일 수 있으면(이미 어디선가 움직여서 온 fireball이 아니라는 의미입니다)
    						fireball f = board[i][j].pollFirst();
    						// 음수 모듈러 연산방법을 잘 모르겠습니다.(아래는 임시방편 코드)
    						int nx = (f.r + dx[f.d] * f.s >= 0) ? (f.r + dx[f.d] * f.s) % N
    								: (N * N * N * N * N + (f.r + dx[f.d] * f.s)) % N;
    						int ny = (f.c + dy[f.d] * f.s >= 0) ? (f.c + dy[f.d] * f.s) % N
    								: (N * N * N * N * N + (f.c + dy[f.d] * f.s)) % N;
    						// 방향으로 속도만큼 이동 후 해당 위치로 불꽃을 옮깁니다.
    						f.r = nx;
    						f.c = ny;
    						f.can_move = false; // 한번 움직였기 때문에 이번턴에는 더 이상 움직일 수 없습니다.
    						board[nx][ny].addLast(f);
    					}
    
    				}
    			}
    		}
    	}
    
    	static class fireball {
    		int r;
    		int c;
    		int m;
    		int s;
    		int d;
    		boolean can_move;
    
    		public fireball(int r, int c, int m, int s, int d, boolean can_move) {
    			super();
    			this.r = r;
    			this.c = c;
    			this.m = m;
    			this.s = s;
    			this.d = d;
    			this.can_move = can_move;
    		}
    
    		@Override
    		public String toString() {
    			return "fireball [r=" + r + ", c=" + c + ", m=" + m + ", s=" + s + ", d=" + d + ", can_move=" + can_move
    					+ "]";
    		}
    
    	}
    
    }
    
    その他
    注意事項
  • listで投票を行う場合は、重複文listを使用します.size()はあげられません.
  • ポーリングはリストのサイズを変更するからです.
  • // 잘못된 예시
    for(int i = 0; i < list.size(); i++){
    	val = list.poll();
    }
    // 올바른 방법
    size = list.size()
    for(int i = 0; i < size; i++){
    	val = list.poll();
    }
  • 音声モジュール化計算方法
    ???