AOJ2087 Speed

問題リンク Speed

• 概要

トランプの「スピード」をプレイするロボットA, Bがいる。このロボットたちの動作をシミュレートしてどちらが勝つかを判定せよ。
「スピード」は手札が4枚、場が2か所、デッキを使い、2人が向かい合って遊ぶ。場に出ている一番上のカードに書いてある数字と隣り合っている数字が手札にあるとき、そのカードをその場の一番上に置くことができる。2人が同時に置こうとしたとき、早く置いたもの勝ちである。置けなかった人は出そうとしていたカードを元の位置に戻さなければならない。手札に空きができると、デッキからカードを1枚補充する必要がある。デッキが無い場合は補充する必要はない。2人とも、場に置くカードが無くなった場合はデッキから1枚取って同時にそれぞれ右側の場へカードを置く。デッキが空の場合は手札から任意の1枚を置く。早く手札、デッキを空にした者が勝ちである。

ロボットはそれぞれNA枚、NB枚のカードが与えられる。そしてロボットは次のようなアルゴリズムで動作する。
・ロボットは与えられたカードの順にカードを引く
　・使うカードはトランプ1組を分けて使うので、全く同じカードが存在しない

・ゲームの初期時、ロボットはカードを4枚引き、右から左の順に手札の場に置く。与えられたカードが4枚未満の場合は置けるだけ置く。この動作が終わると、ロボットは互いに同期を始める。ロボットが各々の右側の場へカードを同時に置いてゲームがスタートする。出すカードはデッキから取る。デッキが空の場合、手札の一番右側に置いたカードを出す。

・この後、上記の一般的なスピードのルールにのっとってロボットは動き続ける
　・ロボットが場にカードを出したとき、デッキが空でないならば、デッキからカードを1枚取って、手札の空いた場所へ置く
　・ロボットが同じ場へカードを出そうとしている場合、完全に置ききった方のみが置ける。置けなかった場合は、ただちに出そうとしたカードを元の位置へ戻す
　・ロボットは、場に出ている一番上のカードと隣り合っているカードがある場合のみ、カードを置く動作を開始することができる
　・もし、ロボットが同じ場へカードを出そうとしている場合で、なおかつ、置ききる時間も同時ならば、ロボットから見て、左側の場へ出そうとしているロボットのみが置くことができる。
　・手札に、場に出すことができるカードが複数ある場合、右側の場へ置けるカードを優先する。それでも候補が複数あるならば、その中で一番弱いカードを出す

・どちらのロボットも場に出すカードがない状態に陥った場合、ゲーム開始時の、同時にカードを出す動作をしてゲームが再開される。

・どちらかのロボットのカードが無くなった場合ゲームが終了する
　・カードが無くなった方のロボットが勝つ
　・もし、同時にカードが無くなった場合、最後に出したカードが強い方が勝つ

カードの強さは、その数字、その柄の順で強さを決定する。数字は
A > K > Q > J > X(10) > 9 > ... > 2
の強さの序列がある。数字が同じ場合、柄の強さで比較する。
S > H > D > C
が柄の強さの序列である。
カードが隣り合っているとは、その数字が隣接しているかどうかである。AとKは隣接しているとみなす。

ロボットは各動作をする場合、以下の通りの時間がかかる
・デッキから手札にカードを補充する動作　300ms
・右側の場へカードを置く動作　500ms
・左側の場へカードを置く動作　700ms
・カードを元の場所へ戻す動作　500ms

カードを元の場所へ戻す動作は、カードを置こうとする動作の進捗に関わらず常に500msかかる。また、カードを置こうとする動作がキャンセルされたその時点から500msかかる。

• 解法

目がくらむようなシミュレーション実装問題です。
ロボットの動作にかかる時間ですが、全て100msの倍数なので100で割ってしまいましょう。
そして、各ロボットに対して、時間tに動作eventを行うという情報を持たせ、時間を1msずつ動かしてシミュレートしました。
ロボットの動作は以下のように区切ってみました
WAIT: 場に出せるカードがないので待機
THINK: 手札に空きがあれば補充し、そうでなければ場に出すカードを決定する
BACK: カードを出そうとしたら置かれてしまったので、元の位置に戻そうとしている状態
PUT: 場にカードを置きにいっている状態
WIN: カードを出し切った
DRAW: デッキからカードを補充しようとしている状態
あとは、これを使って色々気を配りながら実装していきます。
相当苦戦しました。
作ったソースはかなり冗長な部分が多いのですが、もはや整形する気力がありません。

• ソース

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//Speed
public class AOJ2087 {

	class C{
		int suit, rank;
		String str;
		public C(String s) {
			str = s;
			suit = s.charAt(0);
			char c = s.charAt(1);
			rank = c=='A'?1:c=='K'?13:c=='Q'?12:c=='J'?11:c=='X'?10:(c-'0');
		}
		boolean isNeighbor(C c){
			int r1 = rank-1, r2 = c.rank-1;
			return (r1+1)%13==r2 || (r2+1)%13==r1;
		}
		boolean isStrong(C c){
			int r1 = rank, r2 = c.rank;
			if(r1==1)r1=14;
			if(r2==1)r2=14;
			return r1!=r2?r1>r2:suit>c.suit;
		}
		boolean same(C c){
			return suit==c.suit&&rank==c.rank;
		}
	}
	
	final int WAIT = 0, THINK = 1, PUT = 2, BACK = 3, WIN = 4, DRAW = 5;
	
	class R{
		int id;
		C lastCard, nowCard;
		int pos, to, t, event, num;
		Queue<C> deck;
		boolean leftSide;
		C[] place;
		public R(int id) {
			place = new C[4];
			this.id = id;
			lastCard = nowCard = null;
			deck = new LinkedList<C>();
		}
		void put(){
			num--;
			table[to] = nowCard;
			nowCard = null;
			lastCard = table[to];
		}
		void putPrepare(){
			int j = choice();
			nowCard = place[j];
			place[j] = null;
			pos = j;
			event = PUT;
			if(table[id].isNeighbor(nowCard)){
				to = id;
				t+=5;
				leftSide = false;
			}
			else{
				to = 1-id;
				t+=7;
				leftSide = true;
			}
		}
		void back(){
			place[pos] = nowCard;
		}
		void init(){
			num = Math.min(4, deck.size());
			for(int i=0;i<num;i++)place[i]=deck.poll();
		}
		void restart(){
			if(deck.isEmpty()){
				num--;
				for(int i=0;i<4;i++)if(place[i]!=null){
					table[id] = place[i];
					lastCard  = place[i];
					place[i] = null;
					break;
				}
			}
			else{
				table[id] = deck.poll();
				lastCard = table[id];
			}
		}
		void draw(){
			for(int i=0;i<4;i++)if(place[i]==null){
				num++;
				place[i] = deck.poll();
				break;
			}
		}
		int choice(){
			C c = null;
			int r = -1;
			for(int i=0;i<4;i++)if(place[i]!=null){
				if(place[i].isNeighbor(table[id])){
					if(c==null){
						c = place[i]; r = i;
					}
					else if(!place[i].isStrong(c)){
						c = place[i]; r = i;
					}
				}
			}
			if(r!=-1)return r;
			for(int i=0;i<4;i++)if(place[i]!=null){
				if(place[i].isNeighbor(table[1-id])){
					if(c==null){
						c = place[i]; r = i;
					}
					else if(!place[i].isStrong(c)){
						c = place[i]; r = i;
					}
				}
			}
			return r;
		}
	}
	
	R[] robot;
	C[] table;
	
	void run(){
		Scanner sc = new Scanner(System.in);
		robot = new R[2];
		table = new C[2];
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			robot[0] = new R(0); robot[1] = new R(1);
			table[0] = table[1] = null;
			while(n--!=0)robot[0].deck.add(new C(sc.next()));
			n = sc.nextInt();
			while(n--!=0)robot[1].deck.add(new C(sc.next()));
			robot[0].init(); robot[1].init();
			robot[0].restart(); robot[1].restart();
			boolean winA = false;
			if(robot[0].num==0&&robot[1].num==0){
				winA = robot[0].lastCard.isStrong(robot[1].lastCard);
				System.out.println(winA?"A wins.":"B wins.");
				continue;
			}
			if(robot[0].num==0){
				System.out.println("A wins."); continue;
			}
			if(robot[1].num==0){
				System.out.println("B wins."); continue;
			}
			robot[0].event = THINK; robot[1].event = THINK;
			for(int T=0;;T++){
				R r0 = robot[0], r1 = robot[1];
				if(r0.t==T&&r1.t==T){
					if(r0.event == WIN && r1.event == WIN){
						winA = r0.lastCard.isStrong(r1.lastCard);
						break;
					}
					if(r0.event == WAIT && r1.event == WAIT){
						r0.restart(); r1.restart();
						r0.t++; r1.t++;
						if(r0.num==0)r0.event = WIN;
						if(r1.num==0)r1.event = WIN;
						if(r0.event==WIN && r1.event==WIN){
							winA = r0.lastCard.isStrong(r1.lastCard); break;
						}
						if(r0.event==WIN){
							winA = true; break;
						}
						if(r1.event==WIN){
							winA = false; break;
						}
						r0.event = THINK; r1.event = THINK;
						if(r0.event == THINK){
							int j = r0.choice();
							if(j==-1){
								r0.event = WAIT;
								r0.t++;
							}
							else{
								r0.putPrepare();
							}
						}
						if(r1.event == THINK){
							int j = r1.choice();
							if(j==-1){
								r1.event = WAIT;
								r1.t++;
							}
							else{
								r1.putPrepare();
							}
						}
						continue;
					}
					if(r0.event == PUT && r1.event == PUT){
						if(r0.leftSide!=r1.leftSide){
							//put Robot A
							if(r0.leftSide){
								r1.t+=5;
								r1.event = BACK;
								r0.put();
								//draw from deck
								if(!r0.deck.isEmpty()){
									r0.t+=3;
									r0.event = DRAW;
								}
								else{
									//win check
									if(r0.num==0){
										winA = true; break;
									}
									//behave as THINK
									else{
										int j = r0.choice();
										if(j==-1){
											r0.event = WAIT;
											r0.t++;
										}
										else{
											r0.putPrepare();
										}
									}
								}
							}
							//put Robot B
							else{
								r0.t+=5;
								r0.event = BACK;
								r1.put();
								if(!r1.deck.isEmpty()){
									r1.t+=3;
									r1.event = DRAW;
								}
								else{
									if(r1.num==0){
										winA = false; break;
									}
									else{
										int j = r1.choice();
										if(j==-1){
											r1.event = WAIT;
											r1.t++;
										}
										else{
											r1.putPrepare();
										}
									}
								}
							}
						}
						else{
							//put Robot A
							r0.put();
							r1.put();
							//draw from deck
							if(!r0.deck.isEmpty()){
								r0.t+=3;
								r0.event = DRAW;
							}
							else{
								//win check
								if(r0.num==0){
									r0.event = WIN;
								}
								//behave as THINK
								else{
									int j = r0.choice();
									if(j==-1){
										r0.event = WAIT;
										r0.t++;
									}
									else{
										r0.putPrepare();
									}
								}
							}
							//put Robot B
							if(!r1.deck.isEmpty()){
								r1.t+=3;
								r1.event = DRAW;
							}
							else{
								if(r1.num==0){
									r1.event = WIN;
								}
								else{
									int j = r1.choice();
									if(j==-1){
										r1.event = WAIT;
										r1.t++;
									}
									else{
										r1.putPrepare();
									}
								}
							}
							//double win check
							if(r0.event == WIN && r1.event == WIN){
								winA = r0.lastCard.isStrong(r1.lastCard);
								break;
							}
							if(r0.event == WIN){
								winA = true; break;
							}
							if(r1.event == WIN){
								winA = false; break;
							}
						}
						continue;
					}
					if(r0.event == PUT){
						r0.put();
						//draw from deck
						if(!r0.deck.isEmpty()){
							r0.t+=3;
							r0.event = DRAW;
						}
						else{
							//win check
							if(r0.num==0){
								if(r1.event==WIN){
									winA = r0.lastCard.isStrong(r1.lastCard); break;
								}
								winA = true; break;
							}
							//behave as THINK
							else{
								int j = r0.choice();
								if(j==-1){
									r0.event = WAIT;
									r0.t++;
								}
								else{
									r0.putPrepare();
								}
							}
						}
						//process Robot B
						if(r1.event == DRAW){
							r1.draw();
							r1.event = THINK;
						}
						if(r1.event == BACK){
							r1.back();
							r1.event = THINK;
						}
						if(r1.event == WAIT){
							r1.event = THINK;
						}
						if(r1.event == WIN){
							winA = false; break;
						}
						if(r1.event == THINK){
							if(r1.num==3 && !r1.deck.isEmpty()){
								r1.t+=3;
								r1.event = DRAW;
							}
							else{
								int j = r1.choice();
								if(j==-1){
									r1.event = WAIT;
									r1.t++;
								}
								else{
									r1.putPrepare();
								}
							}
						}
						continue;
					}
					else if(r1.event == PUT){
						r1.put();
						if(!r1.deck.isEmpty()){
							r1.t+=3;
							r1.event = DRAW;
						}
						else{
							//win check
							if(r1.num==0){
								if(r0.event==WIN){
									winA = r0.lastCard.isStrong(r1.lastCard); break;
								}
								winA = false; break;
							}
							//behave as THINK
							else{
								int j = r1.choice();
								if(j==-1){
									r1.event = WAIT;
									r1.t++;
								}
								else{
									r1.putPrepare();
								}
							}
						}
						//process Robot A
						if(r0.event == DRAW){
							r0.draw();
							r0.event = THINK;
						}
						if(r0.event == BACK){
							r0.back();
							r0.event = THINK;
						}
						if(r0.event == WAIT){
							r0.event = THINK;
						}
						if(r0.event == WIN){
							winA = true; break;
						}
						if(r0.event == THINK){
							if(r0.num==3 && !r0.deck.isEmpty()){
								r0.t+=3;
								r0.event = DRAW;
							}
							else{
								int j = r0.choice();
								if(j==-1){
									r0.event = WAIT;
									r0.t++;
								}
								else{
									r0.putPrepare();
								}
							}
						}
						continue;
					}
				}
				//process only Robot A
				if(r0.t==T){
					if(r0.event == DRAW){
						r0.draw();
						r0.event = THINK;
					}
					if(r0.event == BACK){
						r0.back();
						r0.event = THINK;
					}
					if(r0.event == WAIT){
						r0.t++;
					}
					else if(r0.event == THINK){
						//draw from deck
						if(r0.num==3 && !r0.deck.isEmpty()){
							r0.event = DRAW;
							r0.t+=3;
						}
						else{
							int j = r0.choice();
							if(j==-1){
								r0.event = WAIT;
								r0.t++;
							}
							else{
								r0.putPrepare();
							}
						}
					}
					else if(r0.event == PUT){
						//put same place, so cancel Robot B
						if(r1.event == PUT && r0.leftSide!=r1.leftSide){
							r0.put();
							//draw from deck
							if(!r0.deck.isEmpty()){
								r0.t+=3;
								r0.event = DRAW;
							}
							else{
								//win check
								if(r0.num==0){
									r0.event = WIN;
								}
								//behave as THINK
								else{
									int j = r0.choice();
									if(j==-1){
										r0.event = WAIT;
										r0.t++;
									}
									else{
										r0.putPrepare();
									}
								}
							}
							r1.t = T+5;
							r1.event = BACK;
						}
						else {
							r0.put();
							//draw from deck
							if(!r0.deck.isEmpty()){
								r0.t+=3;
								r0.event = DRAW;
							}
							else{
								//win check
								if(r0.num==0){
									r0.event = WIN;
								}
								//behave as THINK
								else{
									int j = r0.choice();
									if(j==-1){
										r0.event = WAIT;
										r0.t++;
									}
									else{
										r0.putPrepare();
									}
								}
							}
						}
						if(r1.event == WAIT){
							r1.event = THINK;
						}
					}
					if(r0.event == WIN){
						winA = true; break;
					}
				}
				//process only Robot B
				if(r1.t==T){
					if(r1.event == DRAW){
						r1.draw();
						r1.event = THINK;
					}
					if(r1.event == BACK){
						r1.back();
						r1.event = THINK;
					}
					if(r1.event == WAIT){
						r1.t++;
					}
					else if(r1.event == THINK){
						if(r1.num==3 && !r1.deck.isEmpty()){
							r1.t+=3;
							r1.event = DRAW;
						}
						else{
							int j = r1.choice();
							if(j==-1){
								r1.event = WAIT;
								r1.t++;
							}
							else{
								r1.putPrepare();
							}
						}
					}
					else if(r1.event == PUT){
						if(r0.event == PUT && r0.leftSide!=r1.leftSide){
							r1.put();
							if(!r1.deck.isEmpty()){
								r1.t+=3;
								r1.event = DRAW;
							}
							else{
								if(r1.num==0){
									r1.event = WIN;
								}
								else{
									int j = r1.choice();
									if(j==-1){
										r1.event = WAIT;
										r1.t++;
									}
									else{
										r1.putPrepare();
									}
								}
							}
							r0.t = T+5;
							r0.back();
							int j = r0.choice();
							if(j==-1){
								r0.event = WAIT;
								r0.t++;
							}
							else{
								r0.putPrepare();
							}
						}
						else{
							r1.put();
							if(!r1.deck.isEmpty()){
								r1.t+=3;
								r1.event = DRAW;
							}
							else{
								if(r1.num==0){
									r1.event = WIN;
								}
								else{
									int j = r1.choice();
									if(j==-1){
										r1.event = WAIT;
										r1.t++;
									}
									else{
										r1.putPrepare();
									}
								}
							}
						}
						if(r0.event==WAIT){
							r0.event = THINK;
						}
					}
					if(r1.event == WIN){
						winA = false; break;
					}
				}
			}
			System.out.println(winA?"A wins.":"B wins.");
		}
	}
	
	public static void main(String[] args) {
		new AOJ2087().run();
	}
}