エンジニアの中村です。今週はAAAIやWSDMなどへ海外出張している人が多く、アドテク部は閑散としています。

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

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

Div1 の結果

全体順位	ハンドル	Easy	Medium	Hard	合計
36	uwi	164.39	221.85	-	386.24
146	dpforest03	99.37	-	-	99.37
157	Kenko.Nakamura	94.83	-	-	94.83
191	shiratty9	0.00	-	-	0.00
191	iehn	0.00	-	-	0.00

Div1 Easy は入力が 100 通りしかない単純な問題で、ローカルで提出前に全てのテストケースを実行できる問題でしたが、チェックをサボった 2 人は落ちてしまったようです。

Div2 の結果

全体順位	ハンドル	Easy	Medium	Hard	合計
126	kobiki	230.62	215.31	-	445.93

Div1 Medium 問題レビュー

Div1 Medium はコンテスト中はさっぱり分かりませんでしたが、uwi さんの解説を聞いて理解したので、ここで紹介させていただきます。

topcoder SRM 708 Div1 Medium 問題概要

問題ページ

上記の問題ページの問題文をざっくり訳すと以下のような感じになります。

長さNの文字列Sがあります。X[i]を「Sのi文字目を含むSの部分文字列の回文の個数」とします。

言い換えると、あるiについて、Sからi文字目以外の文字を消して文字列を作るパターンは2^(N-1)通りありますが、そのうち残った文字列が回文となるパターンの数をX[i]とします。

各iについてY[i] = (X[i] * (i + 1)) modulo 1,000,000,007を計算し、さらにそれらのY[i]の値のXORをとった値を求めてください。

(topcoder様より許可をいただき、掲載させていただきました)

解法

文字Zを含む回文とはどのようなものか考えてみます。Zが中心となる回文はabcdZdcbaのようになります。これは分かりやすいですね。では、Zが中心ではない回文はどのようなものでしょうか。例えば、abcZdZcbaのような回文を考えてみます。これを、abcとZdZとcbaの3つに分けてみます。中心を含み、両端をZとする文字列ZdZは回文です。残ったabcとcbaは左右対称な文字列となります。よって、文字Zを含む回文というのは、「Zを中心とする回文」と「Zを両端にもつ回文の数」x「その回文の外側にある左右対称な文字列の数」で求めることが出来ます。

区間に含まれる回文の数

ある区間に含まれる回文の部分文字列の数は動的計画法によって求められます。

dpIn[i][j] := 区間[i, j)に含まれる回文の部分文字列の数 とします。

区間[i, j)に含まれる回文の部分文字列の数は、

dpIn[i][j] = dpIn[i + 1][j] + dpIn[i][j - 1] - dpIn[i + 1][j - 1] + (S[i]とS[j-1]を両端にもつ回文の数)

となり、S[i]とS[j-1]が同じ文字の場合、

(S[i]とS[j-1]を両端にもつ回文の数) = dpIn[i + 1][j - 1] + 1

となります。違う文字の場合は0です。

区間の外側の左右対称な文字列の作り方

ある区間の外側にある左右対称な文字列の数も動的計画法によって求められます。

dpOut[i][j] := 区間[0, i)に含まれる文字列と区間[j, N-1]に含まれる文字列が左右対称となる組み合わせの数とします。

dpOut[i][j] = dpOut[i - 1][j] + dpOut[i][j + 1] - dpOut[i - 1][j + 1] + (S[i-1]を左側に、S[j]を右側に、それぞれ持った時の組み合せの数)

となります。S[i-1]とS[j]が同じ文字の場合、

(S[i-1]を左側に、S[j]を右側に、それぞれ持った時の組み合せの数) = dpOut[i - 1][j + 1]

となります。違う文字の場合は0です。

仕上げ

上記の2回の動的計画法によって求まった組み合せからX[i]を計算することが出来ます。

実装例

public class PalindromicSubseq {

  public int solve(String S) {
    final long MOD = (long) (1e9 + 7);
    int N = S.length();
    char[] s = S.toCharArray();

    //dpIn[i][j] := 区間[i, j)に含まれる回文の数
    long[][] dpIn = new long[N + 1][N + 1];

    //長さ1の回文を数えています
    for (int i = 0; i < N; i++) {
      dpIn[i][i + 1] = 1;
    }

    for (int length = 2; length <= N; length++) {
      //区間[begin, end)に含まれる回文の個数を数えます
      for (int begin = 0; begin + length <= N; begin++) {
        int end = begin + length;
        dpIn[begin][end] = dpIn[begin + 1][end] + dpIn[begin][end - 1] - dpIn[begin + 1][end - 1];

        //この区間の両端が同じ文字だった時、その2文字を使った回文の個数は
        // dpIn[begin][end] += dpIn[begin + 1][end - 1] + 1 です
        if (s[begin] == s[end - 1]) {
          dpIn[begin][end] += dpIn[begin + 1][end - 1] + 1;
        }
        dpIn[begin][end] += MOD;
        dpIn[begin][end] %= MOD;
      }
    }

    // dpOut[i][j]
    // := 区間[0, i)に含まれる文字列と区間[j, N-1]に含まれる文字列が左右対称となる組み合わせの数
    long[][] dpOut = new long[N + 1][N + 1];
    dpOut[0][N] = 1;
    for (int length = N - 1; length >= 0; length--) {
      for (int i = 0; i + length <= N; i++) {
        int j = i + length;
        //区間[0, i)に含まれる文字列と[j, N-1]に含まれる文字列が
        // 対称になるような組み合せを求めます
        if (i > 0) {
          dpOut[i][j] += dpOut[i - 1][j];
        }
        if (j < N) {
          dpOut[i][j] += dpOut[i][j + 1];
        }
        if (i > 0 && j < N) {
          dpOut[i][j] -= dpOut[i - 1][j + 1];
          if (s[i - 1] == s[j]) {
            dpOut[i][j] += dpOut[i - 1][j + 1];
          }
        }
        dpOut[i][j] += MOD;
        dpOut[i][j] %= MOD;
      }
    }

    long[] X = new long[N];
    for (int target = 0; target < N; target++) {
      //targetが中心となるような回文の個数を数えます
      X[target] = dpOut[target][target + 1];

      //内側の回文の右端がtargetとなるような回文を数えます
      for (int j = 0; j < target; j++) {
        if (s[j] == s[target]) {
          //区間(j, target) に含まれる回文の数
          long palindromes = dpIn[j + 1][target];

          //[0, j)と(target, N-1] が対称になる組み合せ
          long outside = dpOut[j][target + 1];

          X[target] += (palindromes + 1) * outside;
          X[target] %= MOD;
        }
      }

      //内側の回文の左端がtargetとなるような回文を数えます
      for (int j = target + 1; j < N; j++) {
        if (s[target] == s[j]) {
          //区間(target, j) に含まれる回文の数
          long palindromes = dpIn[target + 1][j];

          //[0, target) と (j, N-1] が対称になる組み合せ
          long outside = dpOut[target][j + 1];

          X[target] += (palindromes + 1) * outside;
          X[target] %= MOD;
        }
      }
    }

    long ans = 0;
    for (int i = 0; i < N; i++) {
      ans ^= (X[i] * (i + 1)) % MOD;
    }
    return (int) ans;
  }
}

今回のご飯

RCOアドテク部ではエンジニアが成長できる勉強会イベントには支援があり（食べ物もその一部）、このプログラミングコンテストも勉強会に該当します。最近は体重が成長しているのでハンバーガーなんて食べている場合ではないのですが美味しかったです。