Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2013-07-13

ACM-ICPC 2013 Tokyo Domestic 問題F

| 20:49 | はてなブックマーク -  ACM-ICPC 2013 Tokyo Domestic 問題F - cafelier@SRM

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 1つにできる
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法 と呼ばれる構文解析アルゴリズムですね。全部分区間の処理が済んでいれば全体の処理も書き換え1回分だけ考えればいい、という区間DP

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

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/cafelier/20130713
 | 

presented by cafelier/k.inaba under CC0