保存されている過去のバージョンの一覧

2014年08月13日04時26分43秒
2014年08月13日03時50分49秒

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: 2024年04月19日10時15分13秒
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)

ログイン：