エンジニアの kenkoooo です。プロコン部活動日誌です。

プロコン部活動

RCOアドテク部には「プロコン部」というサークルがあり、各自でプログラミングコンテストに参加して、 終了後に解法を共有したり、コンテスト中に不正解となったコードをみんなでデバッグしたりしています。今回は topcoder が開催する Single Round Match (SRM) というコンテストに参加しました。

SRM はレーティング 1200 以上のプレイヤーが参加する Div1 と 1200 未満のプレイヤーが参加する Div2 に分かれています。それぞれ難易度順に Easy, Medium, Hard の3問が出題され、早く解くほど高い得点を得ることができます。結果は以下のとおりです。

Div1 の結果

まさかの全員 0 点でした…… 俺たちは一体何を…… （0点でも42位になれるくらい難しい回でした）

詳しくは後述しますが、Easy について Type A を繰り返した後 Type B を繰り返せば良さそうということは 3 人とも分かっていたようですが、1 ヶ所に集めるということには誰も気づかなかったようです。

Div2 の結果

Div1 とは対象的に高順位を叩き出していました。

Div1 Easy “ReverseMancala” レビュー

せっかくなのでコンテスト中は手も足も出なかった Div1 Easy “ReverseMancala” を解説させていただきます。

問題ページ

問題文は上記のページにあるとおりです。

Type A の操作は Type B の真逆の操作であることが、サンプルケースから分かると思います。また、「穴 x 以外の穴を1つ選び、そこに対して Type A を適用する」という操作を繰り返すことで穴 x に全ての石を集めることが出来ます。これは、この操作によって少なくとも穴 x 以外の穴の石が 1 個以上減り、穴 x の石の個数は減らないためです。常に穴 x の右方向の近い穴から実行すると無限ループせずにできます。

全ての石を穴 x に集めたら、今度は Type B を繰り返すことによって復元したいのですが、Type B は Type A の真逆の操作であることを利用すると、復元したい状態から Type A を繰り返して穴 x に石をすべて集め、その逆をすればよいということになります。

つまり、「Type A を繰り返して全ての石を1ヶ所に集める」「Type A を繰り返して復元した状態から全ての石を1ヶ所に集め、それを反転させる」という2ステップで求めることが出来ます。

実装例

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) {
      // 1 番後ろ以外の穴で、石が残っている穴を探す
      int start = N - 2;
      while (start >= 0 && array[start] == 0) {
        start--;
      }
      if (start < 0) {
        // 残っていなければ終了
        return list;
      }

      // Type B だったとした場合の開始位置
      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<Integer> ans = new ArrayList<>();

    ArrayList<int[]> a = typeA(start);
    for (int[] p : a) {
      ans.add(p[0]);
    }

    ArrayList<int[]> b = typeA(target);
    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;
  }
}

今回のご飯

0 点で食べる弁当美味しいです！（次までに修行しておきます……）

広告

RCOアドテク部では、誰も解けない問題こそ解いてやろうという気概のあるエンジニアも募集しています。

採用ページ