0503: Cup - ArrayListとLinkedList
ちょっとずつ問題が難しくなってきましたね。
方針
今回は綺麗な解法が思いつかず結構悩んだ。。。
一旦寝て次の日電車でぼーっとしてるときににいくつがルールがあることに気づく
【ルール①】移動したコップは次のターンには元いた方向に動かさない
☆ ☆
◎＊ → ◎＊
ＡＢＣ ＡＢＣ
☆をA→Bに移動しました、それだけです。
☆は次に動くとしたらCです、Aにはいきません、元に戻っちゃうので
【ルール②】トレイAからトレイBに連続でコップは動かせない
①で☆をA→Bに動かしました。
AB間に限定して考えた場合、
・動かしたコップ（☆）は次はそのまま ※ルール①
・動かしたコップ（☆）の隣にあるコップ（◎）は直前まで動かしたコップ（◎）の下にあった。つまり問題の（規則２）により動かしたコップ方向には移動できない
（規則 2）大きいコップの上に小さいコップを重ねてはいけない．
B→Aパターンも考えてみましょう
☆ ☆
◎＊ → ◎＊
ＡＢＣ ＡＢＣ
☆：そのまま（ルール①）
◎：動かせない（ルール②）
＊：動かせつとしたらC方向
【ルール③】移動はAB間↔BC間の繰り返し
①②を踏まえるトAB間で移動を行った場合、BC間で移動を行うしかありません。
BC間で移動を行った場合、AB間で移動を行うしかありません。
これに気づいてしまえばあとは簡単。
アルゴリズム
①AB間で大きいコップを小さいコップ方向に移動
②BC間で大きいコップを小さいコップ方向に移動
③”①②”の繰り返し
回答
package joaapp; import java.io.*; import java.util.Stack; class Main{ static int n,m,ans=0; static Stack<Integer> stackA_ini; static Stack<Integer> stackB_ini; static Stack<Integer> stackC_ini; static Stack<Integer> stackA; static Stack<Integer> stackB; static Stack<Integer> stackC; static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] a)throws IOException{ while(true){ inputData(); ans = Math.min(calcFromLeft(),calcFromRight()); ans = (ans <= m) ? ans : -1; System.out.println(ans); } } static int calcFromLeft(){ int step = 0; //左初動 while(true){ // 終了判定 if(isFinished()) break; // 左２つのコップで入れ替え if(peekStack(stackA)>peekStack(stackB)) stackB.push(stackA.pop()); else stackA.push(stackB.pop()); step++; // 終了判定 if(isFinished()) break; // 右２つのコップで入れ替え if(peekStack(stackB)>peekStack(stackC)) stackC.push(stackB.pop()); else stackB.push(stackC.pop()); step++; } return step; } static int calcFromRight(){ int step = 0; stackA = stackA_ini; stackB = stackB_ini; stackC = stackC_ini; //右初動 while(true){ // 終了判定 if(isFinished()) break; // 右２つのコップで入れ替え if(peekStack(stackB)>peekStack(stackC)) stackC.push(stackB.pop()); else stackB.push(stackC.pop()); step++; // 終了判定 if(isFinished()) break; // 左２つのコップで入れ替え if(peekStack(stackA)>peekStack(stackB)) stackB.push(stackA.pop()); else stackA.push(stackB.pop()); step++; } return step; } static boolean isFinished(){ if(stackB.empty() && (stackA.empty() || stackC.empty())) return true; else return false; } static int peekStack(Stack<Integer> stack){ return stack.empty() ? 0:stack.peek(); } static void inputData() throws IOException{ String[] nm = in.readLine().split(" "); String[] cupList; int cupNum = 0; stackA = new Stack<Integer>(); stackB = new Stack<Integer>(); stackC = new Stack<Integer>(); stackA_ini = new Stack<Integer>(); stackB_ini = new Stack<Integer>(); stackC_ini = new Stack<Integer>(); n = Integer.parseInt(nm[0]); m = Integer.parseInt(nm[1]); if(n+m == 0){ System.exit(0); } cupList = in.readLine().split(" "); for(int j=0; Integer.parseInt(cupList[0])>j; j++){ stackA_ini.push(Integer.parseInt(cupList[j+1])); stackA.push(Integer.parseInt(cupList[j+1])); } cupList = in.readLine().split(" "); for(int j=0; Integer.parseInt(cupList[0])>j; j++){ stackB_ini.push(Integer.parseInt(cupList[j+1])); stackB.push(Integer.parseInt(cupList[j+1])); } cupList = in.readLine().split(" "); for(int j=0; Integer.parseInt(cupList[0])>j; j++){ stackC_ini.push(Integer.parseInt(cupList[j+1])); stackC.push(Integer.parseInt(cupList[j+1])); } } }
できました。これを提出すると。。。※susunshunが僕です
11人中11位。。。結構いい線いってると思ったのに。
ArrayListとLinkedList
こんな記事を見かけました。
JavaのArrayListとLinkedListの違い
LinkedListは情報処理試験でお馴染みのスタックやキューを実装しているクラスです。
今回スタックが実装をイメージしやすかったのstackクラスを使用しました。
上記記事によると
先端の要素・終端の要素に対して操作できるメソッドを持っているので
とありますが今回はコップは最大でも１５個。先端終端に簡単にアクセスできるというメリットを享受しにくい気がします。
だったら一般的に処理が軽いArrayListで実装してみたらどうだ。
import java.io.*; import java.util.ArrayList; class Main{ static int n,m,ans=0; static ArrayList<Integer> stackA_ini ; static ArrayList<Integer> stackB_ini ; static ArrayList<Integer> stackC_ini ; static ArrayList<Integer> stackA; static ArrayList<Integer> stackB; static ArrayList<Integer> stackC; static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] a)throws IOException{ while(true){ inputData(); ans = Math.min(calcFromLeft(),calcFromRight()); ans = (ans <= m) ? ans : -1; System.out.println(ans); } } static int calcFromLeft(){ int step = 0; //左初動 while(true){ // 終了判定 if(isFinished()) break; // 左２つのコップで入れ替え if(peekStack(stackA)>peekStack(stackB)){ stackB.add(stackA.get(stackA.size()-1)); stackA.remove(stackA.size()-1); }else{ stackA.add(stackB.get(stackB.size()-1)); stackB.remove(stackB.size()-1); } step++; // 終了判定 if(isFinished()) break; // 右２つのコップで入れ替え if(peekStack(stackB)>peekStack(stackC)){ stackC.add(stackB.get(stackB.size()-1)); stackB.remove(stackB.size()-1); }else{ stackB.add(stackC.get(stackC.size()-1)); stackC.remove(stackC.size()-1); } step++; } return step; } static int calcFromRight(){ int step = 0; stackA = stackA_ini; stackB = stackB_ini; stackC = stackC_ini; //右初動 while(true){ // 終了判定 if(isFinished()) break; // 右２つのコップで入れ替え if(peekStack(stackB)>peekStack(stackC)){ stackC.add(stackB.get(stackB.size()-1)); stackB.remove(stackB.size()-1); }else{ stackB.add(stackC.get(stackC.size()-1)); stackC.remove(stackC.size()-1); } step++; // 終了判定 if(isFinished()) break; // 左２つのコップで入れ替え if(peekStack(stackA)>peekStack(stackB)){ stackB.add(stackA.get(stackA.size()-1)); stackA.remove(stackA.size()-1); }else{ stackA.add(stackB.get(stackB.size()-1)); stackB.remove(stackB.size()-1); } step++; } return step; } static boolean isFinished(){ if(stackB.isEmpty() && (stackA.isEmpty() || stackC.isEmpty())) return true; else return false; } static int peekStack(ArrayList<Integer> stack){ return stack.isEmpty() ? 0:stack.get(stack.size()-1); } static void inputData() throws IOException{ String[] nm = in.readLine().split(" "); String[] cupList; int cupNum = 0; stackA = new ArrayList<Integer>(); stackB = new ArrayList<Integer>(); stackC = new ArrayList<Integer>(); stackA_ini = new ArrayList<Integer>(); stackB_ini = new ArrayList<Integer>(); stackC_ini = new ArrayList<Integer>(); n = Integer.parseInt(nm[0]); m = Integer.parseInt(nm[1]); if(n+m == 0){ System.exit(0); } cupList = in.readLine().split(" "); for(int j=0; Integer.parseInt(cupList[0])>j; j++){ stackA_ini.add(Integer.parseInt(cupList[j+1])); stackA.add(Integer.parseInt(cupList[j+1])); } cupList = in.readLine().split(" "); for(int j=0; Integer.parseInt(cupList[0])>j; j++){ stackB_ini.add(Integer.parseInt(cupList[j+1])); stackB.add(Integer.parseInt(cupList[j+1])); } cupList = in.readLine().split(" "); for(int j=0; Integer.parseInt(cupList[0])>j; j++){ stackC_ini.add(Integer.parseInt(cupList[j+1])); stackC.add(Integer.parseInt(cupList[j+1])); } } }
スタックを使ったときと全く処理は同じです。違いはArrayListかstackかだけ。
では実行時間を見てみましょう。
！？！？
性能が大幅に改善されました。
アルゴリズムだけでなく使用するクラスの選択でここまで変わるものなのかぁ、一つ学びになりました。
