解いた問題のソースコードと解説など。


POJ 2923 Realocation

問題

n個の荷物とその荷物を目的に運ぶための車が2台ある。荷物の重量はそれぞれw[i]であり、車が一回で運ぶことのできる重量はそれぞれc1,c2までである。2台の車は常に同時に動かすとする。荷物をすべて動かすのに2台の車を最低何回動かせばよいか答えよ。

やりかた

nが10以下とちいさいのでbitdpでいける。dp[S]を荷物のうち集合Sを運ぶための最小回数とする。Sの状態から次の移動で車1に残りの荷物のうちTを運ばせ、車2にUを運ばせるとしたときdp[S|T|U] = min(dp[S] + 1, dp[S|T|U])という漸化式を解いていく。

制限時間が厳しいので、車1と2が運ぶ候補をSとは無関係に全列挙すると間に合わない。すでに運んだ荷物の状態Sの補集合に対する部分集合を列挙して車1が運ぶ候補Tとし、SとTの和集合(すでに運んだ荷物と車1が今回運ぶ荷物)の補集合に対する部分集合を列挙して車2は運ぶ候補Uとした。

以下ソース。

int n, c1, c2;
int sum[1 << 10];
int dp[1 << 10];

int rec(int S){
    if(__builtin_popcount(S) == n) return 0;
    if(dp[S] != -1) return dp[S];

    int IS = ~S & ((1 << n) - 1);

    int ans = INF;
    for(int T = IS; ; T = (T - 1) & IS){
        if(sum[T] > c1) continue;

        int H = S | T;
        int IH = ~H & ((1 << n) - 1);
        for(int U = IH; ; U = (U - 1) & IH){
            if((T + U) != 0 && (sum[U] <= c2)){
                ans = min(ans, rec(S | T | U) + 1);
            }
            if(U == 0) break;
        }
        if(T == 0) break;
    } 
    return dp[S] = ans;
}

int main(){
  int T;
  int w[10];
  scanf("%d", &T);
  for(int j = 0; j < T; j++){
    scanf("%d %d %d", &n, &c1, &c2);
    for(int i = 0; i < n; i++) scanf("%d", &w[i]);

    for(int S = 0; S < 1 << n; S++){
      int s = 0;
      for(int i = 0; i < n; i++) if(S >> i & 1) s += w[i];
      sum[S] = s;
    }
    FILL(dp, -1);
    printf("Scenario #%d:\n%d\n\n", j + 1, rec(0));
  }
  return 0;
}

数日来、気落ちすることが多いので競技プログラミングをして心を落ち着けています。

Get up! 明日のSUPER ST@R!