提出 #72328502

---

ソースコード 拡げる

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintStream;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static final boolean TEST = false;
    public static final boolean DEBUG = false;
    static final String baseDir = "C:\\tmp\\AHC059\\";
    static final String inDir = baseDir + "in\\";
    static final String outDir = baseDir + "out\\";
    static final String infoDir = baseDir + "info\\";
    long startTime = System.currentTimeMillis();
    Random RND = new Random();
    long TIMER = 1700;

    Scanner in;
    PrintStream out;

    public static void main(String[] args) throws Exception {
        if (TEST) {
            try {
                {
                    FileWriter writer = new FileWriter(infoDir + "result.txt");
                    BufferedWriter bufferedWriter = new BufferedWriter(writer);
                    bufferedWriter.write("\n");
                    writer.close();
                }
                {
                    FileWriter writer = new FileWriter(infoDir + "data.txt");
                    BufferedWriter bufferedWriter = new BufferedWriter(writer);
                    bufferedWriter.write("\n");
                    bufferedWriter.close();
                }
            } catch (IOException e) {
                e.printStackTrace();
            }

            File[] files = new File(inDir).listFiles();
            for (File f : files) {
                if (f.isFile()) {

                	//if ( !f.getName().equals("0282.txt") ) continue;

                	Main main = new Main(
                            new Scanner(f),
                            new PrintStream(outDir + f.getName())
                    );
                    main.fileName = f.getName();
                    main.init0();
                    main.fire();
                    main.out();
                    main.terminate();
                }
            }
        } else {
            Main main = new Main(new Scanner(System.in), System.out);
            main.init0();
            main.fire();
            main.out();
            main.terminate();
        }
    }

    public Main(Scanner in, PrintStream out) {
        this.in = in;
        this.out = out;
    }

    String fileName = null;

    static int N;
    int[][] A0,A;
    Stack<Integer> yama;
    int x,y;
    int turn=0;
    
    Pos[][] cardPos;
    
    final int[] vx = {0,-1,1,0,0};
    final int[] vy = {1,0,0,-1,0};
    
    long score, bestScore = Long.MAX_VALUE;
    char[] answer,bestAnswer;

    void init0() {
        N = in.nextInt();
        A = new int[N][N];
        A0 = new int[N][N];

        for (int y=0;y<N;y++) {
        	for (int x=0;x<N;x++) {
        		A0[y][x] = in.nextInt();
        	}
        }
        
        Pos.init(N);

        cardPos = new Pos[N*N/2][2];
        for (int y=0;y<N;y++) {
        	for (int x=0;x<N;x++) {
        		int n = A0[y][x];
        		if ( cardPos[n][0]==null )  cardPos[n][0] = Pos.get(x,y);
        		else cardPos[n][1] = Pos.get(x,y);
        	}
        }
                
        startTime = System.currentTimeMillis();
    }

    void init1() {
    	score = 0;
        for (int y=0;y<N;y++) {
        	for (int x=0;x<N;x++) {
        		A[y][x] = A0[y][x];
        	}
        }
        yama = new Stack<>();

        answer = new char[2*N*N*N];
        turn = 0;
        x=0;y=0;
    }

    void updateScore() {
    	if ( score < bestScore ) {
    		bestScore = score;
    		bestAnswer = answer;
    	}
    }
    
    void fire() {
    	init1();
    	f3();
    	updateScore();
}
    

    void f1() {
    	for (int t=0;t<N*N/2;t++) {
//    		System.err.println("T="+t +"  pos="+x+","+y);

//    		show(A);

            //一番近いカードに移動 & GET
    		Pos target = findNearestCard(x,y);
    		move(target);
    		getCard();

//    		System.err.println("T="+t +"  move to="+x+","+y);
//    		show(yama);
    		
    		//対応するカードに移動 & PUT
    		target = findPair(yama.peek());
    		move(target);
    		getCard();
    		
//    		System.err.println("T="+t +"  move to="+x+","+y);
//    		show(yama);
//    		System.err.println(answer);
    	}
    }
    
    void f2() {
    	int t=0;
    	while (t < N*N/2 ) {
    		//山が空→一番近いカードに移動 & GET
    		if ( yama.empty() ) {
        		Pos target = findNearestCard(x,y);
        		move(target);
        		getCard();
    		}
    		
    		//現在地とGOALの間に、ペアがあるか？
			Pos via=null;
			while ( ( via=findPair(x,y,findPair(yama.peek())) ) != null ) {
	    		//ペアがあれば、移動＆GET
        		move(via);
        		getCard();
			}

			//山のてっぺんに対応するカードに移動 & PUT
    		Pos target = findPair(yama.peek());
    		move(target);
    		getCard();
    		t++;
    	}
    }
    
    void f3() {
    	int t=0;
    	while (t < N*N/2 ) {
    		//山が空→一番近いカードに移動 & GET
    		if ( yama.empty() ) {
        		Pos target = null;
        		
        		int bestMH=0;
        		for (int d=0;d<5;d++) {
        			int xx = x + vx[d];
        			int yy = y + vy[d];
        			if ( inside(xx, yy) && A[yy][xx]>=0 ) { //
        				int n = A[yy][xx];
        				int wkMH = cardPos[n][0].MH(cardPos[n][1]); //ペアまでの距離
        				if ( wkMH > bestMH ) {
        					target = Pos.get(xx, yy); //遠くに行こう
        					bestMH = wkMH;
        				}
        			}
        		}
        		
        		if ( target==null )target = findNearestCard(x,y);
    			
    			//近くのカードをランダムに選ぶ
        		move(target);
        		getCard();
    		}
    		
    		//現在地とGOALの間に、ペアがあるか？
			Pos via=null;
			while ( ( via=findPair(x,y,findPair(yama.peek())) ) != null ) {
	    		//ペアがあれば、移動＆GET
        		move(via);
        		getCard();
			}

			//山のてっぺんに対応するカードに移動 & PUT
    		Pos target = findPair(yama.peek());
    		move(target);
    		getCard();
    		t++;
    	}
    }
    
    void move(Pos target) {
		while ( x != target.x ) {
			if ( x<target.x ) R();
			if ( x>target.x ) L();
		}
		while ( y != target.y ) {
			if ( y<target.y ) D();
			if ( y>target.y ) U();
		}
    }
    
    void R() {
    	answer[turn++] = 'R';
    	score++;
    	x++;
    }
    void L() {
    	answer[turn++] = 'L';
    	x--;
    }
    void U() {
    	answer[turn++] = 'U';
    	y--;
    }
    void D() {
    	answer[turn++] = 'D';
    	y++;
    }
    void getCard() {
    	answer[turn++] = 'Z';
    	if ( A[y][x]<0 ) System.err.println("No card at " + x + "," + y );
    	int wk = A[y][x];
    	A[y][x]=-1;
    	
    	if ( !yama.empty() && yama.peek() == wk ) {
    		yama.pop();
    		score++;
    	} else {
    		yama.push(wk);
    	}
    }
    void putCard() {
    	answer[turn++] = 'X';
    	if ( A[y][x]>=0 ) System.err.println("Already card at " + x + "," + y );
    	A[y][x] = yama.pop();
    }
    
    
    //一番近いカードを探す
    Pos findNearestCard(int x,int y) {
    	boolean[][] mark = new boolean[N][N];
    	Pos[] posList = new Pos[N*N*2];
    	int idx=0,length=0;
    	
    	posList[length++] = Pos.get(x, y);
    	while (idx<length) {
    		Pos crt = posList[idx++];
    	
    		for (int d=0;d<4;d++) {
    			int xx = crt.x + vx[d];
    			int yy = crt.y + vy[d];
    			if ( inside(xx,yy) && mark[yy][xx]==false ) {
    				if ( A[yy][xx]>=0 ) return Pos.get(xx, yy);
    				
    				mark[yy][xx]=true;
    				posList[length++] = Pos.get(xx, yy);
    			}
    		}
    	}
    	return null;
    }

    Pos findPair(int x0,int y0,Pos goal) {
    	int x1 = goal.x;
    	int y1 = goal.y;
    	
    	Pos ret = null;
    	int bestMH = goal.MH(x0,y0);    	
    	
    	for (int n=0;n<N*N/2;n++) {
    		int xx0 = cardPos[n][0].x; 
    		int yy0 = cardPos[n][0].y; 
    		int xx1 = cardPos[n][1].x; 
    		int yy1 = cardPos[n][1].y;
    		
    		if  ( A[yy0][xx0]>=0 && A[yy1][xx1]>=0 &&
    				xx0 >= x0 && xx0 <= x1 &&
    				xx1 >= x0 && xx1 <= x1 &&
    				yy0 >= y0 && yy0 <= y1 &&
    				yy1 >= y0 && yy1 <= y1 ) {
    			//近いほうを返す
    			int mh1 = cardPos[n][0].MH(x,y);
    			int mh2 = cardPos[n][1].MH(x,y);
    			
    			Pos wkTarget =  mh1<mh2 ? cardPos[n][0]:cardPos[n][1];
    			int wkMH = wkTarget.MH(x0,y0);
    			if ( wkMH < bestMH ) {
    				bestMH = wkMH;
    				ret = wkTarget;
    			}
    		}
    	}
    	return ret;
    }
    
    
    boolean inside(int x,int y) {
    	return x>=0 && y>=0 && x<N && y<N;
    }

    Pos findPair(int n) {
    	for (int y=0;y<N;y++) {
    		for (int x=0;x<N;x++) {
    			if ( A[y][x]==n ) return Pos.get(x,y);
    		}
    	}
    	return null;
    }
    
    
    //デバッグ出力
    void show(Object[] O) {
    	for (Object o : O ) System.err.println(o.toString());
    }
    void show(int[] z) {
		for (int x : z ) System.err.print(x +" " );
		System.err.println(".");
    }
    void show(int[][] Z) {
    	for (int[] z : Z ) show(z);
    }
    void show(Stack st) {
    	for (int i=0;i<st.size();i++) {
    		System.err.print( st.elementAt(i) +" " );
    	}
		System.err.println(".");
    }
    
    
    void out() {
    	int idx=0;
    	while ( bestAnswer[idx]!='\0' ) {
    		out.println(bestAnswer[idx++]);
    	}
        out.flush();
    }

    void terminate() {
        in.close();
        out.flush();
        out.close();

        System.err.println( bestScore );
        
        if (TEST) {
            try {
                FileWriter writer = new FileWriter(infoDir + "result.txt", true);
                writer.flush();
                writer.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
}

class Pos {
	static Pos[][] P;
	
	static void init(int N) {
		P = new Pos[N][N];
		for (int y=0;y<N;y++) {
			for (int x=0;x<N;x++) {
				P[y][x] = new Pos(x,y);
			}
		}
	}
	
	static Pos get(int x,int y) {
		return P[y][x];
	}
	
	int x,y;
	
	public Pos(int x,int y) {
		this.x=x;
		this.y=y;
	}
	
	int MH(int xx,int yy) {
		return Math.abs(x-xx)+Math.abs(y-yy);
	}
	int MH(Pos p) {
		return Math.abs(x-p.x)+Math.abs(y-p.y);
	}
	
	public String toString() {
		return x +","+ y;
	}
}

提出情報

ジャッジ結果