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: 2017年09月25日08時04分52秒
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)

ログイン: