TopCoder SRM629 DIV1 MEDIUM - CandyCollection

Source

TopCoder SRM629 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

キャンディがある.
形は $N$ 種類あり,味も $N$ 種類ある.
ただし,味は食べてみるまでわからず,買うときは,形を指定して,その形のキャンディを何個か買うことができる.
また,全体では,ちょうど $2N$ 種類のキャンディがあり,同じ形のキャンディはちょうど $2$ 種類の味があり,同じ味のキャンディもちょうど $2$ 種類の形がある.
それぞれ $2N$ 種類のキャンディについて,個数 $C_k$ が与えられる.
一つも食べる前に,確実に全ての味を揃えるためには,最小で何個のキャンディを買えば良いかを求める問題.

解法

各形に対して,味 $i$ が $x$ 個,味 $j$ が $y$ 個あるとすると,$x+1$ 個買うと味 $j$ は必ず手に入り,$y+1$ 個買うと味 $i$ は必ず手に入る.
また,ノード(ノードは味,枝は形を意味する)数 $N$ のグラフで,$i$ と $j$ を枝で結んだものを考える.
全てのノードは次数 $2$ なので,サイクルの集まりになっている.
サイクルごとに分けて考える.
各ノードでは,繋がっている枝のどちらかを用いて,そのノードを買わなくてはいけない,という関係になっている.
また,枝は,どちらかのノードだけ買う,両方のノードを買う,の $3$ 通りのコストが付けられている.
サイクルになっているので,適当にどこかでぶった切ってDPして,全てのノードを買うための最小コストを求めれば良い.
ぶった切る場所を全部試すと $O(N^2)$.
最初のノードを買ったかどうかを状態に加えると $O(N)$ でも計算できる.

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

#include<bits/stdc++.h>
using namespace std;

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

#define INF 1000000000

int N;
int edge[1100][11], cost[1100][11], cost1[1100][11], cost2[1100][11], es[1100];

int vis[1100];
int arr[1100], arr1[1100], arr2[1100], sz;

int dp[1100];

class CandyCollection {
public:
int solve(vector <int> Type1, vector <int> Number1, vector <int> Type2, vector <int> Number2) {
  int i, j, k, cur, loop;
  int res = 0, tmp;

  N = Type1.size();

  rep(i,N) es[i] = 0;
  rep(i,N){
    j = Type1[i];
    k = Type2[i];
    edge[j][es[j]] = k;
    edge[k][es[k]] = j;
    cost[j][es[j]] = cost[k][es[k]] = max(Number1[i], Number2[i]) + 1;
    cost1[j][es[j]] = cost2[k][es[k]] = Number1[i] + 1;
    cost2[j][es[j]] = cost1[k][es[k]] = Number2[i] + 1;
    es[j]++; es[k]++;
  }

  rep(i,N) vis[i] = 0;

  rep(k,N) if(!vis[k]){
    vis[k] = 1;

    if(edge[k][0]==k){ res++; continue; }

    if(edge[k][0]==edge[k][1]){
      tmp = min(cost[k][0], cost[k][1]);
      tmp = min(tmp, cost1[k][0]+cost2[k][1]);
      tmp = min(tmp, cost2[k][0]+cost1[k][1]);
      res += tmp;
      vis[edge[k][0]] = 1;
      continue;
    }

    sz = 0;
    cur = k;
    vis[k] = 1;
    for(;;){
      if(vis[edge[cur][0]] && vis[edge[cur][1]]){
        if(edge[cur][0]==k) arr[sz] = cost[cur][0], arr1[sz] = cost1[cur][0], arr2[sz++] = cost2[cur][0];
        if(edge[cur][1]==k) arr[sz] = cost[cur][1], arr1[sz] = cost1[cur][1], arr2[sz++] = cost2[cur][1];
        break;
      }

      if(vis[edge[cur][0]]==0) i = 0;
      else                     i = 1;

      arr[sz] = cost[cur][i];
      arr1[sz] = cost1[cur][i];
      arr2[sz] = cost2[cur][i];
      sz++;
      cur = edge[cur][i];
      vis[cur] = 1;
    }

    tmp = INF;
    rep(loop,sz){
      rep(i,sz+1) dp[i] = INF;
      
      dp[0] = min(arr2[0], arr1[sz-1]);
      dp[1] = min(arr[0], dp[0]+arr1[0]);
      REP(i,1,sz){
        dp[i] = min(dp[i], dp[i-1] + arr2[i]);
        dp[i+1] = min(dp[i+1], dp[i] + arr1[i]);
        dp[i+1] = min(dp[i+1], dp[i-1] + arr[i]);
      }
      tmp = min(tmp, dp[sz-1]);
      rep(i,sz-1){
        swap(arr[i], arr[i+1]);
        swap(arr1[i], arr1[i+1]);
        swap(arr2[i], arr2[i+1]);
      }
    }
    res += tmp;
  }

  return res;
}

}

Current time: 2017年09月21日04時56分14秒
Last modified: 2014年08月13日04時26分43秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM629 SRM_Div1_Medium
トップページに戻る

Logged in as: unknown user (not login)

ログイン: