TopCoder SRM614 DIV1 MEDIUM - CycleColoring

Source

TopCoder SRM614 DIV1 MEDIUM (525pt)
Problem Statement

問題概要

以下の無向グラフを考える．
$N$ 個のサイクル $C_0,C_1,\ldots,C_{N-1}$ がある．
サイクル $C_k$ は $V_k$ 個のノードからなり，ノードは順番にラベルが $v_{k,0}, v_{k,1}, \ldots, v_{k,V_k-1}$ と付けられている．
ここで，$v_{k,i}$ とは $v_{k,\ i+1\ {\rm mod}\ V_k}$ とは「実線で表される枝」で繋がっている．
また，各サイクルもサイクルになっている．
サイクル $C_i$ の $F_i$ 番目のノード $C_{i,\ F_i}$ と サイクル $C_{i+1\ {\rm mod}\ N}$ の $T_i$ 番目のノード $C_{i+1\ {\rm mod}\ N,\ T_i}$ は「破線で表される枝」で繋がっている．
$K$ 色の色があるとき，各ノードを以下の条件1～2を満たすように色を塗る方法はいくつあるかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題．

  1. 「実線で表される枝」に繋がっているノードは違う色で塗らなければいけない
  2. 「破線で表される枝」に繋がっているノードは同じ色で塗らなければいけない

解法

同じサイクルの中での塗り方，全体での塗り方の2ステップに分けてDPする．
1ステップ目では，あるノードを起点として，何個先のノードまでの色の塗り方を，2端点のノードが同じ色の場合，違う色の場合のパターン数を計算する．
2ステップ目（全体）では，破線の枝が繋がっているノードのみに着目して，同様のDPをし，1ステップ目のDPの結果を用いる．
起点のノードの色（あるいは，起点，終点の色）を固定してしまい，他の色はすべて同一視することで，状態数が少なくなる．
1ステップ目が $O(\max V_k)$，2ステップ目が $O(N)$．

C++によるスパゲッティなソースコード

// #includeなどは略しています

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define M 1000000007

ll dp_in[1000100][3];
ll dp_out[100][2];

ll mul2(ll a, ll b){
  return (a*b)%M;
}

ll mul3(ll a, ll b, ll c){
  return (((a*b)%M)*c)%M;
}

ll mul4(ll a, ll b, ll c, ll d){
  return (((((a*b)%M)*c)%M)*d)%M;
}

class CycleColoring {
public:
int countColorings(vector <int> cnt, vector <int> from, vector <int> to, int K) {
  int i, j, k, n;
  int bef, aft, x, y;
  ll res;

  n = cnt.size();

  dp_in[0][0] = 1; dp_in[0][1] = dp_in[0][2] = 0;
  REP(i,1,1000100){
    dp_in[i][0] = (dp_in[i-1][1] + dp_in[i-1][2] * (K-2)) % M;
    dp_in[i][1] = (dp_in[i-1][0] + dp_in[i-1][2] * (K-2)) % M;
    dp_in[i][2] = (dp_in[i-1][0] + dp_in[i-1][1] + dp_in[i-1][2] * (K-3)) % M;
  }

  dp_out[0][0] = 1; dp_out[0][1] = 0;
  rep(i,n){
    dp_out[i+1][0] = dp_out[i+1][1] = 0;

    bef = to[(i+n-1)%n];
    aft = from[i];

    x = (aft - bef + 3 * cnt[i]) % cnt[i];
    y = cnt[i] - x;

    dp_out[i+1][0] += mul3(dp_out[i][0], dp_in[x][0], dp_in[y][0]);
    dp_out[i+1][1] += mul4(dp_out[i][0], dp_in[x][1], dp_in[y][1], K-1);

    dp_out[i+1][0] += mul3(dp_out[i][1], dp_in[x][1], dp_in[y][1]);
    dp_out[i+1][1] += mul3(dp_out[i][1], dp_in[x][0], dp_in[y][0]);
    dp_out[i+1][1] += mul4(dp_out[i][1], dp_in[x][1], dp_in[y][1], K-2);

    dp_out[i+1][0] %= M;
    dp_out[i+1][1] %= M;
  }

  res = dp_out[n][0] * K;
  res %= M;
  return res;
}

}

Current time: 2024年04月25日05時01分18秒
Last modified: 2014年03月31日19時20分51秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM614 SRM_Div1_Medium Dynamic_Programming
トップページに戻る

Logged in as: unknown user (not login)

ログイン：