エンジニアの kenkoooo です。今年の GW は 9 連休です。

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

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

Div1 の結果

どの問題も非常に難しく、 Div1 は全員が座るだけのコンテストでした。哀しいなあ。

0 点でも 58 位という良い順位が得られることから、参加者の大半が座るだけだった事が分かりますが、そのような横並びの状況で Challenge に失敗して負の点数を取って大きく順位を下げてしまった人もいました。

Div2 の結果

Div2 の方はまともなコンテストになっていたようです。

Div1 Medium “DFSCount” レビュー

今回はコンテスト中考えていたものの通せなかった Div1 Medium DFSCount を復習します。

解法としては、メモ化再帰と呼ばれる手法を用います。

深さ優先探索 (DFS) をしている途中の状況を考えます。ある頂点 v に到達した時、それまでに通ってきた頂点の集合を S とします。 S に含まれる頂点を通らずに v から DFS をして到達できる頂点の並べ方の数 を計算する方法を考えてみましょう。

S に含まれず、かつ、 v に隣接している頂点 u を考えます。DFS した順番が ... -> v -> u -> ... となるような並べ方を数え上げてみます。 S に含まれる頂点と v を通らずに u から DFS した時に到達できる頂点の並べ方の数 x を考えると x を計算する過程で S に含まれる頂点と v を通らずに u から DFS した時に到達できる頂点の集合 T を求めることができます。これを用いて、 S または T に含まれる頂点と u を通らずに DFS した時に到達できる頂点の並べ方の数 y を計算すると、x * y が DFS した順番が ... -> v -> u -> ... となるような並べ方の数になることがわかります。

この計算を各 u について計算して足し合わせると、 S に含まれる頂点を通らずに v から DFS をして到達できる頂点の並べ方の数 になります。

上記の手順を S が空集合の状態から順番に計算し、足し合わせることで、求めたい答えが出ます。

実装例

public class DFSCount {

  private int N;
  private boolean[][] edges;

  // dfs[v][used] := used に含まれている頂点を通らないように v から DFS した時に通る頂点集合 (used を含む)
  private int[][] dfs;

  // dp[v][used] := used に含まれている頂点を通らないように v から DFS した時に通る頂点の並び方
  private long[][] dp;

  private boolean contains(int set, int v) {
    return ((1 << v) & set) != 0;
  }

  /**
   * 頂点 v から始めて used に含まれる頂点を通らないように深さ優先探索する
   *
   * @param v 今から見る頂点
   * @param used 頂点集合をビット列で表現したもの
   * @return 深さ優先探索した時に通る頂点の並び方の数
   */
  private long dfs(int v, int used) {
    if (dfs[v][used] != 0) {
      return dp[v][used];
    }

    int usedV = used | (1 << v);
    dfs[v][used] = usedV;
    boolean done = true;
    for (int u = 0; u < N; u++) {
      if (!edges[v][u] || contains(used, u)) {
        continue;
      }

      done = false;
      dfs(u, usedV);

      // u から usedV に含まれる頂点を通らないように DFS して得られた頂点集合から v を抜いたもの
      int subset = dfs[u][usedV] ^ (1 << v);

      // v から used も u も通らずに DFS する
      dfs(v, subset);

      dfs[v][used] |= dfs[u][usedV];
      dfs[v][used] |= dfs[v][subset];

      // u から usedV を通らずに DFS して通る頂点の並び方
      // すなわち v から u を通り used を通らずに DFS して通る頂点の並び方
      long x = dp[u][usedV];

      // v から u と used を通らずに DFS して通る頂点の並び方
      long y = dp[v][subset];

      dp[v][used] += x * y;
    }

    if (done) {
      // v から used を通らずにどこにも行けない時は 1 通りしかない
      dp[v][used] = 1;
    }
    return dp[v][used];
  }

  public long count(String[] G) {
    N = G.length;
    dp = new long[N][1 << N];
    dfs = new int[N][1 << N];

    edges = new boolean[N][N];
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        edges[i][j] = G[i].charAt(j) == 'Y';
      }
    }

    long ans = 0;
    for (int i = 0; i < N; i++) {
      ans += dfs(i, 0);
    }
    return ans;
  }
}

会席弁当「花車」

0 点で食べる弁当おいしいです！（次は頑張ります…）

広告

入札可能な広告の集合をビット列で保持する実装をしたり、高速に通信するためにバイト列を操作する実装をしたりすることがあり、競技プログラミングの経験が活きている実感があります。RCOアドテク部では、競技プログラミングで実装力を鍛えたエンジニアも募集しています。

採用ページ