SRM 646 Div2 (練習)

結果

oox (練習)
Editorial http://apps.topcoder.com/wiki/display/tc/SRM+646

kmjpさんの解法(TopCoder SRM 646 Div2 Hard TheFootballDivTwo - kmjp's blog)を参考にしました.場合分けがすごい苦手だということが分かりました.

[Easy: TheConsecutiveIntegersDivTwo ]

問題

整数の配列numbersと整数kが与えられる.次の操作を繰り返して,numbers内のk個の要素を連続する整数に変更したい.操作とは,numbers内の1つの要素を選び,その要素に1を加えるか1減らすことである.
操作の最小回数を求めよ.

解法

kが1ならば操作の必要がないので0を返します.kが2ならばnumbersをソートして任意の隣り合う要素同士の差分の絶対値が最小のものを見つけます.同じ要素同士の場合は注意が必要です.

ソースコード
class TheConsecutiveIntegersDivTwo {
public:
    int find(vector <int> numbers, int k) {
        if (k == 1)
            return 0;

        sort(numbers.begin(), numbers.end());
        int res = INT_MAX;
        const int n = numbers.size();

        for (int i = 0; i < n - 1; ++i) {
            if (numbers[i] == numbers[i + 1])
                res = min(res, 1);
            else
                res = min(res, abs(numbers[i] - numbers[i + 1]) - 1);
        }

        return res;
    }
};

[Medium: TheGridDivTwo ]

問題

ジョンは格子状の原点に立っている.いくつかの格子点にはブロックがあり通ることが出来ない.ジョンは1秒単位で上下左右のブロックの無い格子点に移動することが出来る.k秒以内に出来る限りx座標が大きくなるように移動したい.その時のx座標を求めよ.

i番目のブロックの座標はx[i], y[i]である.
 1 \le k \le 10^3, 0 \le x.size(), y.size() \le 47, -10^3 \le x_i, y_i \le 10^3

解法

kが小さいので原点から幅優先探索をします.

ソースコード
const int dx[] = {0, 1, 0, -1};
const int dy[] = {-1, 0, 1, 0};
const int MAX_H = 2010;
const int MAX_W = 2010;
const int sx = MAX_W / 2;
const int sy = MAX_H / 2;
const int isBlock = -2;

class TheGridDivTwo {

    int board[MAX_H][MAX_W];

public:
    int find(vector <int> x, vector <int> y, int k) {
        const int n = x.size();

        memset(board, -1, sizeof(board));
        for (int i = 0; i < n; ++i)
            board[y[i] + sy][x[i] + sx] = isBlock;

        queue<pair<int, int>> que;
        que.push(make_pair(sy, sx));
        board[sy][sx] = 0;

        while (!que.empty()) {
            pair<int, int> now = que.front();
            que.pop();

            for (int d = 0; d < 4; ++d) {
                int nx = now.second + dx[d];
                int ny = now.first + dy[d];

                if (board[ny][nx] == isBlock)
                    continue;
                if (board[ny][nx] == -1 ||
                    (board[now.first][now.second] + 1 < board[ny][nx])) {
                    board[ny][nx] = board[now.first][now.second] + 1;
                    if (board[ny][nx] <= k)
                        que.push(make_pair(ny, nx));
                }
            }
        }

        int res = -1001;
        for (int i = MAX_W - 1; i >= 0; --i) {
            for (int j = 0; j < MAX_H; ++j) {
                if (board[j][i] >= 0 && board[j][i] <= k) {
                    res = i - sx;
                    break;
                }
            }
            if (res != -1001)
                break;
        }

        return res;
    }
};

[Hard: TheFootballDivTwo ]

問題

トーナメントを行う.ある時点で,あなたのチームはyourScore点持っており,各々のiに対して,scores[i]点を持っているチームがnumberOfTeams[i]チームいる.したがって,トーナメントの総参加チームはsum(numberOfTeams + 1)である.
それぞれのチームは残り2戦ある(同じ対戦者かもしれない).試合に勝つと3点,負けると0点がもらえる(引き分けは無し).最終ランキングは総合得点の最も高いチームから1位,2位・・・とする.
すべての結果の中で,あなたのチームの順位が最も良くなる時の順位を答えよ.

解法

kmjpさんの解法通りですが,場合分けを理解するのに苦労したので自分が分かりやすいように解釈したことを書きます.

総チーム数をN+1とします.
N個の箱とN個のボールがあります.すべてのボールを箱の中に入れていきますが,各々の箱は最大で2個のボールを入れることが出来ます(箱をチーム,ボールを得点3に対応する).
次にそれぞれの箱をcnt1, cnt2, cnt3, cnt4の4つのグループに分けていきます.

  • cnt1グループ: すべて負けようがyourScore+6を超すチーム
  • cnt2グループ: すべて勝ってもyourScore+6を超えないチーム
  • cnt3グループ: 1勝したらyourScore+6を超すチーム
  • cnt4グループ: 2勝したらyourScore+6を超すチーム

f:id:tatanaideyo:20150129024304p:plain
自分のチームの順位が悪い方に変動しないように箱にボールを入れていきます.
cnt1グループとcnt2グループに属している箱にボールを2個入れても順位が悪い方に変動しないので,入れられるだけ入れます.また,cnt4グループに属する各々の箱にボール1個を入れても変わりません.この時,残りのボールはN-2*(cnt1-cnt2)-cnt4個あります.これが0以下ならば,自分のチームの順位を変動せずにすべてのボールを入れることが出来たので順位はcnt1となります.
f:id:tatanaideyo:20150129033748p:plain
残りのボールの個数をresとします.cnt3とcnt4に属するどの箱にいれてもチームの順位は変動します.しかし,cnt3の1つの箱を一杯するのにボールは2個必要になりcnt4の箱にボールを入れるよりもお得になります.場合分けが簡単になるようにcnt3のグループのすべての箱が一杯で,cnt4の箱に入れていくことから考えます.この条件は,cnt3のすべての箱にボールが一杯であるので res \ge 2 \times cnt3 という条件になります.この時の順位はcnt1,cnt3,cnt4の埋まっている箱の数となります.
f:id:tatanaideyo:20150129033209p:plain

最後に,cnt3の箱に入れる場合です.最後はだいぶ端折りすぎました orz
f:id:tatanaideyo:20150129034537p:plain

ソースコード
class TheFootballDivTwo {
public:
    int find(int yourScore, vector <int> scores, vector <int> numberOfTeams) {
        const int n = numberOfTeams.size();
        int cnt1 = 0, cnt2 = 0, cnt3 = 0, cnt4 = 0, sum = 0;

        yourScore += 6;
        for (int i = 0; i < n; ++i) {
            if (scores[i] > yourScore) {
                // cnt1 := すべて負けようがyourScoreを超すチーム数
                cnt1 += numberOfTeams[i];
            }
            else if (3 + scores[i] > yourScore) {
                // cnt3 := 1勝したらyourScoreを超すチーム数
                cnt3 += numberOfTeams[i];
            }
            else if (6 + scores[i] > yourScore){
                // cnt4 := 2勝したらyourScoreを超すチーム数
                cnt4 += numberOfTeams[i];
            }
            else {
                // cnt2 := 2勝してもyourScoreを越せないチーム数
                cnt2 += numberOfTeams[i];
            }

            sum += numberOfTeams[i]; // 全チーム数 - 1
        }

        int ans = cnt1 + 1;
        // 順位が変動しないように分配した後の残りの分配すべき勝利数
        int res = sum - 2 * (cnt1 + cnt2) - cnt4 - 1;
        if (res >= 2 * cnt3)
            ans += cnt3 + (res - 2 * cnt3);
        else if (res > 0)
            ans += (res + 1) / 2;

        return ans;
    }
};