Hatena::Grouptopcoder

TopCoder煮ブログ

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

2013-10-06

HexagonalBoard (SRM 593 Div1 Easy)

| 21:42 | HexagonalBoard (SRM 593 Div1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - HexagonalBoard (SRM 593 Div1 Easy) - TopCoder煮ブログ

方針は http://topcoder.g.hatena.ne.jp/nitoyon/20131005/1380995960 で固まっていたので、あとは書くだけ。

単純ミスで 1 回、System Test 落ちたあと、再提出で pass。ダメな感じ。

あと、最大 3 色だというところの証明がパッと出てこない。

#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;

// -xx
// x*x
// xx-
int neighbor[][2] = {{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1}};

class HexagonalBoard {
    bool visited[50][50];
    int color[50][50];
    vector<string> b;
    int N;
public:
    int search(int x, int y, int col) {
        visited[y][x] = true;
        color[y][x] = col;
        int ret = 1;
        for (int i = 0; i < 6; i++) {
            int xx = x + neighbor[i][0];
            int yy = y + neighbor[i][1];
            if (xx < 0 || yy < 0 || xx >= N || yy >= N) {
                continue;
            }
            if (b[yy][xx] == 'X') {
                ret = max(ret, 2);
                if (visited[yy][xx]) {
                    if (color[yy][xx] != -col) {
                        ret = 3;
                    }
                } else {
                    ret = max(ret, search(xx, yy, -col));
                }
            }
        }
        return ret;
    }

    int minColors(vector <string> board) {
        b = board;
        N = b.size();
        memset(visited, 0, sizeof(visited));
        memset(color, 0, sizeof(color));
        int ret = 0;

        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                if (b[y][x] == 'X' && !visited[y][x]) {
                    ret = max(ret, search(x, y, 1));
                }
            }
        }
        return ret;
    }
};

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;
    }
};