エンジニアの kenkoooo です。朝型生活に切り替えたらエグいほど体重が減りました。

プロコン部活動

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

SRM はレーティング 1200 以上のプレイヤーが参加する Div1 と 1200 未満のプレイヤーが参加する Div2 に分かれています。それぞれ難易度順に Easy, Medium, Hard の3問が出題され、早く解くほど高い得点を得ることができます。また Challenge によって他のプレイヤーのソースコードの不備を見つけると 50 ポイント加算、Challenge に失敗すると -25 ポイントになります。結果は以下のとおりです。

Div1 の結果

Medium も Hard も難しく、全体的に Easy を早解きする勝負になりました。0 点の2人も解法にはたどり着いたようですが、 64 bit を超える範囲の整数を処理せずオーバーフローによって不正解となってしまったようです。

Div1 Easy “LR” レビュー

今回は気持ちよく解けた Div1 Easy LR を解説させていただきます。

「操作 L を適用した後に操作 R を適用する」ことによって得られる結果と「操作 R を適用した後に操作 L を適用する」ことによって得られる結果が同じであることがわかります。すると、操作列内で隣り合う R と L を入れ替えても最終的な結果に影響しないことがわかります。そうなるとソートの要領で、操作列を LLL...L...LLLRRR...R...RRR というように「L を何回か続けて適用した後に R を何回か続けて適用する」という形に変形してしまっても良いことがわかり、数列 s を t に変換するために必要な L の数と R の数を求めさえすれば良いことがわかります。

数列に操作 L を 1 回適用すると数列の和は 2 倍になるので、操作の回数は高々 50 回くらいだということがわかります。そこで、「数列 s に操作 L を 0 回適用した数列」「数列 s に操作 L を 1 回適用した数列」…「数列 s に操作 L を 50 回適用した数列」について、それぞれひたすら操作 R を適用していき、無事数列 t に変換できればそれを出力、操作 R を 50 回ほど適用しても数列 t にならなければ破棄、というように全探索すれば答えが出ます。

実装例

import java.util.ArrayList;

public class LR {

  public String construct(long[] s, long[] t) {
    int N = s.length;

    //元の数列が全て 0 だった時
    boolean allZero = true;
    for (long value : s) {
      if (value > 0) {
        allZero = false;
        break;
      }
    }
    if (allZero) {
      for (int i = 0; i < N; i++) {
        if (t[i] > 0) {
          //変換先の数列が全て 0 でなければ変換することはできない
          return "No solution";
        }
      }
      //変換先の数列も全て 0 ならば操作無しで変換できる
      return "";
    }

    //操作 L を 0, 1, ... 回適用した数列を用意する
    ArrayList<long[]> lefts = new ArrayList<>();
    lefts.add(s);
    while (true) {
      long[] last = lefts.get(lefts.size() - 1);
      long[] next = new long[N];
      for (int i = 1; i < N; i++) {
        next[i] = last[i] + last[i - 1];
      }
      next[0] = last[0] + last[N - 1];

      if (!included(next, t)) {
        //操作Lを適用しすぎて変換先の数列を超えてしまった場合はそこでやめる
        break;
      }
      lefts.add(next);
    }

    for (int L = 0; L < lefts.size(); L++) {
      //操作LをL回適用した数列について、操作Rを何回適用すると数列tになるかを調べる
      long[] left = lefts.get(L);
      for (int R = 0; ; R++) {
        if (ok(left, t)) {
          //答えが見つかった場合はその操作列を出力する
          StringBuilder builder = new StringBuilder();
          for (int i = 0; i < L; i++) {
            builder.append("L");
          }
          for (int i = 0; i < R; i++) {
            builder.append("R");
          }
          return builder.toString();
        }

        long[] next = new long[N];
        for (int i = 0; i < N - 1; i++) {
          next[i] = left[i] + left[i + 1];
        }
        next[N - 1] = left[N - 1] + left[0];
        left = next;
        if (!included(left, t)) {
          //操作Rを適用しすぎて変換先の数列を超えてしまった場合はそこでやめる
          break;
        }
      }
    }

    //全探索しても答えが見つからない場合はその旨を出力する
    return "No solution";
  }

  private static boolean included(long[] left, long[] t) {
    for (int i = 0; i < left.length; i++) {
      if (left[i] > t[i]) {
        return false;
      }
    }
    return true;
  }

  private static boolean ok(long[] left, long[] t) {
    for (int i = 0; i < left.length; i++) {
      if (left[i] != t[i]) {
        return false;
      }
    }
    return true;
  }
}

海鮮弁当

好順位で食べる弁当美味しいです！（前回の SRM が 0 点だったので一層嬉しく感じます）

広告

RCO アドテク部では、オーバーフローに負けないエンジニアも募集しています。

採用ページ