TopCoder SRM 710 Div 1 Easy: ReverseMancala
解法
操作Aと操作Bは完全に対称な操作であることが分かる。操作Aをしまくって1箇所に集め、操作Bをしまくって復元すれば良い。
コード
import java.util.ArrayList; import java.util.Collections; public class ReverseMancala { private int N; private ArrayList<int[]> typeA(int[] array) { ArrayList<int[]> list = new ArrayList<>(); while (true) { int start = N - 2; while (start >= 0 && array[start] == 0) { start--; } if (start < 0) { return list; } int end = (start + array[start]) % N; list.add(new int[]{start, end}); int num = array[start]; array[start] = 0; for (int j = 0; j < num; j++) { array[(start + 1 + j) % N]++; } } } public int[] findMoves(int[] start, int[] target) { this.N = start.length; ArrayList<int[]> a = typeA(start); ArrayList<int[]> b = typeA(target); ArrayList<Integer> ans = new ArrayList<>(); for (int[] p : a) { ans.add(p[0]); } Collections.reverse(b); for (int[] p : b) { ans.add(p[1] + start.length); } int[] ret = new int[ans.size()]; for (int i = 0; i < ret.length; i++) { ret[i] = ans.get(i); } return ret; } }