Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-28

SRM453.5 div1 (過去問)

19:34

Medium - PlanarGraphShop

交差するエッジの無い無向グラフを planar graph と呼ぶ. planar graph のコストを, ノード数^3 + エッジ数 ^ 2 と定義する. コストが整数 N ぴったりになるには, 最小でいくつの planar graph が必要か.

すべての種類の planar graph のコストを求める問題と, 求まったコストの集合を利用して必要なグラフ数を求める問題に分割しました. まずコストの求め方ですが, Nが高々50000なので, コストが50000以下になるすべてのグラフを探索します. 手計算により, エッジの数の範囲は [0, ノード数+ノード数-3] と求まりました. この結果を items という配列に保存しました. 次に, 2番目のグラフ数を求める問題には, ナップザック問題風の考え方のdpを利用しました. 一次元の配列 dp をつくり, dp[i] には N=i のときに必要なグラフ数が入ります. dp[i] は (j <= i) となるすべてのj二ついて, items[j] + dp[i-j] を求めて, その最小値が値となります.

ローカルでのテストでは, インプットが大きいとだいぶ時間がかかっていたので, TLEがやばいかなと思っていたんですが, サーバでテストしてみると意外と間に合いそうだったので, このまま提出しました. システムテストでは, 今のところ実行時間は大丈夫なんですが, 返り値がふつうに間違っていたところがあったので, どこかにバグが有るようです. 明日デバッグします.

class PlanarGraphShop {
public:
  int bestCount(int N) {
    int ret = 0;
    vector <int> items(50001, 0);
    vector <int> dp(N+1, INT_MAX);
    
    // calculate costs of planar graphs (generate items)
    items[1] = 1;
    for (int nodes=1; nodes<=36; nodes++)
      for (int edges=0; edges<=nodes + nodes - 3; edges++) {
        int cost = (int)pow((double)nodes, 3) + (int)pow((double)edges, 2);
        if (cost > 50000) continue;
        items[cost] = 1;
      }

    // knapsack
    dp[0] = 0;
    for (int i=1; i<=N; i++) {
      for (int j=1; j<=i; j++)
        if (items[j] == 1)
          dp[i] = min(dp[i], items[j] + dp[i-j]);
    }

    ret = dp[N];
    return ret;
  }
};