Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2013-10-06

MayTheBestPetWin (SRM 593 Div1 Medium)

| 23:37 | MayTheBestPetWin (SRM 593 Div1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - MayTheBestPetWin (SRM 593 Div1 Medium) - TopCoder煮ブログ

時間をかけても全く分からないので http://topcoder.g.hatena.ne.jp/kojingharang/20131006#1381050540Java 2 位の uwi さんのソースで理解した。

  • 選手 n ごとに最速タイム A[n] と最低タイム B[n] が分かっている (2 <= N <= 50, 1 <= A <= 10,000, 1 <= B <= 10,000)。
  • 2 つのチーム S, T に分けてリレーを行う。チームの人数は違ってもよい。
  • 一番緊迫する試合を見たいので、とりうる時間差が最小となるようなチームわけにしたい。このときの時間差を求める。

総当りで実装すると、すべてのチーム分けに対して

max(|S fast - T slow|, |S slow - T fast|)

の最小値を求めればよい。2 ^ 50 通りなので爆発して総当りは不可能。


SumA, SumB を計算しておく。

次のようにする。

  • SumA = ΣA = A[0] + A[1] + ... + A[n-1]
  • SumB = ΣB = B[0] + B[1] + ... + B[n-1]
  • C[i] = A[i] + B[i]

とする。

    int calc(vector <int> A, vector <int> B) {
        int SumA = 0, SumB = 0;
        int N = A.size();

        // SumA, SumB を計算
        for (int i = 0; i < N; i++) {
            SumA += A[i];
            SumB += B[i];
        }

ここで数式変換。

|S fast - T slow| = |ΣA[s] - ΣB[t]|
                  = |(SumA - ΣA[t]) - ΣB[t]|
                  = |SumA - ΣC[t]|
|S slow - T fast| = |ΣB[s] - ΣA[t]|
                  = |(SumB - ΣB[t]) - ΣA[t]|
                  = |SumB - ΣC[t]|
(s in S, t in T)

となる。

あとは、ΣC[t] のとりうる値が分かればよい。イメージで言ってしまえば、SumA, SumB のなるべく中間の値を取るようにグループ T を選びましょう、という問題になる。

DP

といっても、グループ T の取り方はたくさんある。ここで DP が登場。時間をキーに DP する。

ΣC[t] のとりうる範囲は 0~SumA + SumB の中に限定される。この範囲の bool な配列 dp をつくって、とりうるなら true、とらないなら false として調べていく。

  • すべての選手がチーム S にいるケースでは ΣC[t] は 0。dp[0] のみを true にしておく。
  • 選手 0 がチーム S に参加する可能性を考えると、ΣC[t] は 0 か C[0] をとりうる。dp[0+C[0] ] を true にする。
  • 選手 1 がチーム S に参加する可能性を考えると、ΣC[t] は 0, C[0], C[1], C[0] + C[1] をとりうる。dp[0+C[1] ] と dp[C[0]+C[1] ] を true にする。

こんな感じで 0~SumA + SumB の範囲について、ΣC[t] がとりうる範囲のフラグを立てていく。

        // 時間をキーにした dp 配列を準備
        // C[i] = A[i] + B[i] が取る得る値かどうかを格納する
        bool* dp = new bool[SumA + SumB + 1];
        memset(dp, 0, sizeof(bool) * (SumA + SumB + 1));
        dp[0] = true;
        for (int n = 0; n < N; n++) {
            for (int i = SumA + SumB; i >= 0; i--) {
                if (dp[i]) {
                    dp[i + A[n] + B[n]] = true;
                }
            }
        }

すべての選手を列挙したら、dp 配列には ΣC[t] がとりうる値のみフラグがたった状態になっている。

最小値を求める

ΣC[t] の範囲内のすべての値について max(|SumA - ΣC[t]|, |SumB - ΣC[t]|) を計算する。この最小値が求めるべき値となる。

        // C[i] のそれぞれの値について、
        // max(|S fast - T slow|, |S slow - T fast|) を求める。
        // その中での最小値を調べる
        int ret = SumA + SumB;
        for (int i = 0; i <= SumA + SumB; i++) {
            if (dp[i]) {
                int maxdiff = max(abs(SumA - i), abs(SumB - i));
                ret = min(ret, maxdiff);
            }
        }

おしまい。自力で分かる気がしない・・・。

以下、ソース。


#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#define _USE_MATH_DEFINES
#include <math.h>
#include <string.h>
using namespace std;

class MayTheBestPetWin {
public:
    int calc(vector <int> A, vector <int> B) {
        int SumA = 0, SumB = 0;
        int N = A.size();

        // SumA, SumB を計算
        for (int i = 0; i < N; i++) {
            SumA += A[i];
            SumB += B[i];
        }

        // 時間をキーにした dp 配列を準備
        // C[i] = A[i] + B[i] が取る得る値かどうかを格納する
        bool* dp = new bool[SumA + SumB + 1];
        memset(dp, 0, sizeof(bool) * (SumA + SumB + 1));
        dp[0] = true;
        for (int n = 0; n < N; n++) {
            for (int i = SumA + SumB; i >= 0; i--) {
                if (dp[i]) {
                    dp[i + A[n] + B[n]] = true;
                }
            }
        }

        // C[i] のそれぞれの値について、
        // max(|S fast - T slow|, |S slow - T fast|) を求める。
        // その中での最小値を調べる
        int ret = SumA + SumB;
        for (int i = 0; i <= SumA + SumB; i++) {
            if (dp[i]) {
                int maxdiff = max(abs(SumA - i), abs(SumB - i));
                ret = min(ret, maxdiff);
            }
        }

        return ret;
    }
};