AOJ1120 Pile Up!

問題リンク Pile Up!

• 概要

1〜Nの番号が書かれたブロックがある。最初は全て床に転がっている。
2つの整数の命令リストが与えられ、ロボットはそれに従ってブロックを動かす。最終的にできたブロックの塔全ての高さを昇順に答えよ。
命令はX, Yの整数で構成される。Xのブロックを、Yのブロックが含まれる塔の上に積む。
このとき、Xのブロックより上にあるブロックは全て1つずつ床に置かれる。
もし、XとYが既に同じ塔の中に合った場合は次のいずれかの行動をとる。
XがYよりも下に積まれていた場合、通常通りXより上のブロックを全て床におき、XをYの上に積む。
XがYよりも上に積まれていた場合、この命令は無視される。
Y=0のとき、これはXを床に置けという命令である。このときも次のいずれかの行動をとる。
Xが既に床に合った場合、命令は無視される。Xが床にあるとは、Xが塔の一番下にあるという意味である。
Xが床になかった場合、Xより上のブロックを全て床におき、Xを床に置く。
N <= 100
1 <= X <= N
0 <= Y <= N

• 解法

問題文さえ読解できれば後はその通りに実装するだけです。塔はスタックを使って実現できるので、床にあるブロックの集合と、Listを使って実装します。塔に番号xが含まれるかはStack.contains()を、xが塔の一番下にあるかはStack.get(0)==xで判定できます。

• ソース

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

//Pile Up!
public class AOJ1120 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			Set<Integer> floor = new TreeSet<Integer>();
			LinkedList<Stack<Integer>> pile = new LinkedList<Stack<Integer>>();
			for(int i=1;i<=n;i++)floor.add(i);
			for(;;){
				int a = sc.nextInt();
				int b = sc.nextInt();
				if((a|b)==0)break;
				if(a==b)continue;
				if(b==0){
					if(floor.contains(a))continue;
					for(Stack<Integer> s:pile){
						if(s.contains(a)){
							if(s.get(0)==a)break;
							while(s.peek()!=a){
								floor.add(s.pop());
							}
							floor.add(s.pop());
							break;
						}
					}
					continue;
				}
				int ai = -1;
				int bi = -1;
				for(int i=0;i<pile.size();i++){
					if(pile.get(i).contains(a))ai = i;
					if(pile.get(i).contains(b))bi = i;
				}
				if(ai==bi&&ai!=-1){
					Stack<Integer> s = pile.get(ai);
					int aj = s.search(a);
					int bj = s.search(b);
					if(aj<bj)continue;
					while(s.peek()!=a){
						floor.add(s.pop());
					}
					floor.remove(b);
					Stack<Integer> st = new Stack<Integer>();
					st.push(b); st.push(s.pop());
					pile.add(st);
					if(s.isEmpty())pile.remove(ai);
					continue;
				}
				if(ai!=-1){
					Stack<Integer> s = pile.get(ai);
					while(s.peek()!=a)floor.add(s.pop());
					s.pop();
					if(s.isEmpty())pile.remove(ai);
					for(int i=0;i<pile.size();i++)if(pile.get(i).contains(b))bi=i;
				}
				else floor.remove(a);
				if(bi!=-1)pile.get(bi).push(a);
				else{
					Stack<Integer> st = new Stack<Integer>();
					floor.remove(b);
					st.push(b); st.push(a);
					pile.add(st);
				}
			}
			PriorityQueue<Integer> q = new PriorityQueue<Integer>();
			for(int i=0;i<floor.size();i++)q.add(1);
			for(Stack<Integer> s:pile)q.add(s.size());
			while(!q.isEmpty())System.out.println(q.poll());
			System.out.println("end");
		}
	}
	
	public static void main(String[] args) {
		new AOJ1120().run();
	}
}