cafelier@SRM

ACM-ICPC 2013 Tokyo Domestic 問題F

その他 | 20:49 |

ACM-ICPC 2013 国内予選 の問題Fを解いてみたよ。

O(n^3m^3 + (n^3+m^3)r|x|).

#include <iostream>
#include <vector>
#include <set>
#include <tuple>
using namespace std;

// x∈dp[i][j]  ⇔  A[i..j) を書き換えまくったら x １つにできる
vector<vector<set<int>>> make_rewritability_table(
  const vector<int>& A, const vector<tuple<int,int,int>>& R)
{
  const int N = A.size();
  vector<vector<set<int>>> dp(N, vector<set<int>>(N));
  for(int i=0; i<N; ++i)
    dp[i][(i+1)%N].insert(A[i]);

  for(int k=2; k<=N; ++k)
  for(int i=0; i<N; ++i)
  for(int m=1; m<k; ++m)
  for(auto& rule : R) {
    int x1,x2,y; tie(x1,x2,y) = rule;
    if(dp[i][(i+m)%N].count(x1) && dp[(i+m)%N][(i+k)%N].count(x2))
      dp[i][(i+k)%N].insert(y);
  }
  return dp;
}

// 高速化のため set<int> を int のビット表現に変換
vector<vector<int>> as_bitset(const vector<vector<set<int>>>& table)
{
  vector<vector<int>> bit_table(table.size(), vector<int>(table[0].size()));
  for(int i=0; i<table.size(); ++i)
  for(int k=0; k<table[i].size(); ++k)
  for(int v : table[i][k])
    if(v > 0)
      bit_table[i][k] |= 1<<v;
  return bit_table;
}

// A[ao]が先頭に来るようにAを回転したもの vs B[bo]以下略
// を書き換えまくって作れる最長共通列を考える。
//
// A[as..ae] と B[bs..be) が同じ数 1 つに書き換えられるときに
// (as,bs)==>(ae,be) という長さ 1 の辺を引いた DAG を考えて、
// DAG の最長経路を求めればよい。
int solve_rotated(const vector<vector<int>>& rA, int ao,
                  const vector<vector<int>>& rB, int bo)
{
  const int N = rA.size(), M = rB.size();
  vector< vector<int> > dp(N+1, vector<int>(M+1, -99999));
  dp[N][M] = 0;
  for(int ae=N; ae>=1; --ae)
  for(int be=M; be>=1; --be)
  for(int as=0; as<ae; ++as)
  for(int bs=0; bs<be; ++bs)
    if(rA[(as+ao)%N][(ae+ao)%N] & rB[(bs+bo)%M][(be+bo)%M])
      dp[as][bs] = max(dp[as][bs], 1 + dp[ae][be]);
  return dp[0][0];
}

// 回転は最初に全部やれば十分なので、
// 全通りの回し方を考えて solve_rotated に投げる
int solve(const vector<int>& A, const vector<int>& B,
          const vector<tuple<int,int,int>>& R)
{
  vector<vector<int>> rA = as_bitset(make_rewritability_table(A, R));
  vector<vector<int>> rB = as_bitset(make_rewritability_table(B, R));

  int best = -1;
  for(int ao=0; ao<A.size(); ++ao)
  for(int bo=0; bo<B.size(); ++bo)
    best = max(best, solve_rotated(rA, ao, rB, bo));
  return best;
}

// 入出力
int main()
{
  for(int N,M,R; cin>>N>>M>>R, N|M|R; )
  {
    vector<int> A(N); for(int& Ai: A) cin>>Ai;
    vector<int> B(M); for(int& Bi: B) cin>>Bi;

    vector<tuple<int,int,int>> P;
    for(int i=0,ID=-1; i<R; ++i)
    {
      int K; cin>>K;
      vector<int> X(K); for(int& Xi: X) cin>>Xi;
      int Y; cin>>Y;

      // 左辺が長いルールは、左辺が長さ2になるように分解する
      // 例: a b c d -> e ==> {a b -> -1,  -1 c -> -2,  -2 d -> e}
      for(int k=0; k+1<K; ++k)
        P.emplace_back(k?ID-k:X[0], X[k+1], k==K-2?Y:ID-k-1);
      ID -= K-2;
    }

    cout << solve(A, B, P) << endl;
  }
}

各所で指摘されているけれど make_rewritability_table() は、CYK法 と呼ばれる構文解析アルゴリズムですね。全部分区間の処理が済んでいれば全体の処理も書き換え１回分だけ考えればいい、という区間DP。

入力列の長さに関する影響だけを考えて O(n^3) であると書かれることが多いのですけど、よほど実装を工夫でもしない限り、書き換え規則のサイズ|G|まで考慮にいれるとこれが掛かって O(n^3・|G|) なので、回転の扱いをさぼるために solve_rotated の中で毎回計算し直したりすると意外と時間がかかったりする。