読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 710 Div 1 Easy: ReverseMancala

競技プログラミング SRM

解法

操作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;
  }
}