Publié il y a 2021-03-19Mis à jour il y a 2023-06-30Kick Start22 minutes de lecture (Environ 3357 mots)0 visites

Kick Start Round F 2020解题记录

ATM Queue

解题思路

使用队列结构来模拟取钱队列的方式，但是Test Set 2超时了。

#include <iostream>
#include <queue>

using namespace std;

void cal(int T) {
    int N, X, A;
    cin >> N >> X;

    queue<pair<int, int>> Q;
    for (int i = 1; i <= N; ++i) {
        cin >> A;
        Q.push({A, i});
    }

    cout << "Case #" << T << ":";

    while (!Q.empty()) {
        auto p = Q.front();
        Q.pop();
        if (p.first <= X) {
            cout << " " << p.second;
        } else {
            p.first -= X;
            Q.push(p);
        }
    }
    cout << endl;
}

int main() {
    int T;
    cin >> T;

    for (int i = 1; i <= T; ++i) {
        cal(i);
    }

    return 0;
}

优化

观察可以得知，取相同次数就能够完成需求的所有人，他们的相对位置与初始一致。因此可以直接计算某人需要取多少次钱，然后进行排序即可。

#include <iostream>
#include <vector>
#include <algorithm>

#define UPDIV(A, X) (((A) + (X) - 1) / (X))

using namespace std;

void cal(int T) {
    int N, X, A;
    cin >> N >> X;

    vector<pair<int, int>> Q;
    for (int i = 1; i <= N; ++i) {
        cin >> A;
        Q.emplace_back(UPDIV(A, X), i);
    }
    
    sort(Q.begin(), Q.end(), [](const pair<int, int>& A, const pair<int, int>& B) -> bool {
        if (A.first != B.first) {
            return A.first < B.first;
        }
        return A.second < B.second;
    });

    cout << "Case #" << T << ":";

    for (const auto &q : Q) {
        cout << " " << q.second;
    }

    cout << endl;
}

int main() {
    int T;
    cin >> T;

    for (int i = 1; i <= T; ++i) {
        cal(i);
    }

    return 0;
}

Metal Harvest

解题思路

因为已知所有时间间隔不会重叠，因此直接对所有输入的时间间隔的$S_i$进行排序。

然后采用贪心法，从每个间隔的起点开始，使用二分查找搜寻第一个大于机器人工作结束时间点的时间间隔（即，$E_j > S_i + K\text{, 且}j > i$）；找到之后再次比较$S_j$和$S_i + K$的大小。如果$S_j > S_i + K$，那么说明该机器人最多可以工作到第$j - 1$个时间间隔；反之说明当前间隔$j$还需要一个机器人来处理。这样就可以知道当前机器人，最终能经过多少个时间间隔。

这样也超时了吗。。。

#include <iostream>
#include <vector>
#include <algorithm>

typedef long long ll;

using namespace std;

int binSearch(vector<pair<ll, ll>>& times, int start, int end, ll target) {
    int L = start;
    int R = end;
    int mid;

    while (L <= R) {
        mid = L + ((R - L) >> 1);

        if (times[mid].second <= target) {
            L = mid + 1;
        } else if (mid == start || times[mid - 1].second <= target) {
            return mid;
        } else {
            R = mid - 1;
        }
    }

    return -1;
}

ll cal (int N, int K) {
    vector<pair<ll, ll>> times(N);

    for (int i = 0; i < N; ++i) {
        cin >> times[i].first >> times[i].second;
    }

    sort(times.begin(), times.end(), [](const pair<ll, ll>& A, const pair<ll, ll>& B) -> bool {
        return A.first < B.first;
    });

    ll robot_end = 0;
    ll count = 0;

    int time_pos = 0;

    while (time_pos < N) {
        robot_end = times[time_pos].first + K;
        int pos = binSearch(times, time_pos, N - 1, robot_end);

        ++count;
        if (pos == -1) {
            break;
        }
        time_pos = pos;

        if (robot_end > times[time_pos].first) {
            times[time_pos].first = robot_end;
        }
    }

    return count;
}

int main() {
    int T, N, K;
    cin >> T;

    for (int i = 1; i <= T; ++i) {
        cin >> N >> K;
        cout << "Case #" << i << ": " << cal(N, K) << endl;
    }

    return 0;
}

优化

经过分析发现，上述方法忽略了一种极端情况。即当一个时间间隔非常大的时候，在该间隔内可能需要很多的机器人，但是如果对其中每一个机器人都调用二分查找的话，则会浪费大量的时间。

新增了一个计算$num = UPDIV(E_i - S_i, K)$，来计算出当前间隔需要多少个机器人。

#include <iostream>
#include <vector>
#include <algorithm>

#define UPDIV(A, X) (((A) + (X) - 1) / (X))

typedef long long ll;

using namespace std;

int binSearch(vector<pair<ll, ll>>& times, int start, int end, ll target) {
    int L = start;
    int R = end;
    int mid;

    while (L <= R) {
        mid = L + ((R - L) >> 1);

        if (times[mid].second <= target) {
            L = mid + 1;
        } else if (mid == start || times[mid - 1].second <= target) {
            return mid;
        } else {
            R = mid - 1;
        }
    }

    return -1;
}

ll cal (int N, int K) {
    vector<pair<ll, ll>> times(N);

    for (int i = 0; i < N; ++i) {
        cin >> times[i].first >> times[i].second;
    }

    sort(times.begin(), times.end(), [](const pair<ll, ll>& A, const pair<ll, ll>& B) -> bool {
        return A.first < B.first;
    });

    ll robot_end = 0;
    ll count = 0;

    int time_pos = 0;

    while (time_pos < N) {

        ll num = UPDIV(times[time_pos].second - times[time_pos].first, K);

        robot_end = times[time_pos].first + num * K;
        int pos = binSearch(times, time_pos, N - 1, robot_end);

        count += num;
        if (pos == -1) {
            break;
        }

        time_pos = pos;

        if (robot_end > times[time_pos].first) {
            times[time_pos].first = robot_end;
        }
    }

    return count;
}

int main() {
    int T, N, K;
    cin >> T;

    for (int i = 1; i <= T; ++i) {
        cin >> N >> K;
        cout << "Case #" << i << ": " << cal(N, K) << endl;
    }

    return 0;
}

Painters’ Duel

解题思路

博弈类型的题实在是不熟悉，因此主要思路参考了文章：[Google Kickstart 2020][校招笔试][Round F]全部题目+题解

整体方法来说就是暴力穷举，通过递归的方式，让A和B做一次最佳的决策，然后再进一步分析后续的可能。如果当前最佳策略存在多种，那么就遍历所有可能，寻找出最佳的结果。因此关键在于什么样的策略是最佳的决策。

对于这道题，A的最优策略就是走尽可能多的房间，B的最优策略就是让A走尽可能少的房间。因此当A走出一步的时候，B要找出当前所有可能的下一步中得分最少的选择；而A则需要在所有当前所有可能的下一步中，找出得分最多的选择（在B的阻碍之下）。

所以题目就抽象成了：

遍历A当前所有的下一步 $ Next_A_i $
然后进一步遍历B基于 $ Next_A_i $ 的所有下一步 $ Next_B_i $
从所有的 $ Next_B_i $ 中，找出使得得分最少的那一个 $ Next_B $
因此A当前所有的下一步均有一个最少得分 $ MIN_i $ ，A再从中选出得分最高的下一步。

这里出题人给的样例范围确实很巧妙，暴力法竟然没有超时。但是优化的话，很容易联想到剪枝和记忆化。

#include <iostream>
#include <vector>
#include <algorithm>

#define BLOCK 0
#define FREE  1
#define MAXDIRS 4

typedef long long ll;

using namespace std;

class Solution {
public:
    Solution() {
        cin >> S >> RA >> PA >> RB >> PB >> C;

        free.resize(S * S, FREE);

        for (int i = 0; i < C; ++i) {
            int x, y;
            cin >> x >> y;

            free[transform(x, y)] = BLOCK;
        }

        free[transform(RA, PA)] = BLOCK;
        free[transform(RB, PB)] = BLOCK;

    }

    int solve() {
        return trace(RA, PA, RB, PB);
    }

private:
    // turn = true -> A
    // turn = false -> B
    int trace(int RA_, int PA_, int RB_, int PB_) {
        int maxPossible = 1 << 31;
        bool FLAGA = false;

        for (int dirA = 0; dirA < MAXDIRS; ++dirA) {
            int Next_RA = RA_;
            int Next_PA = PA_;

            if (canGo(dirA, Next_RA, Next_PA)) {
                FLAGA = true;

                free[transform(Next_RA, Next_PA)] = BLOCK;
                int minPossible = 0x3f3f3f3f;
                bool FLAGB = false;

                for (int dirB = 0; dirB < MAXDIRS; ++dirB) {
                    int Next_RB = RB_;
                    int Next_PB = PB_;

                    if (canGo(dirB, Next_RB, Next_PB)) {
                        FLAGB = true;

                        free[transform(Next_RB, Next_PB)] = BLOCK;
                        // 此处之所以不累加得分是因为，A走了，B也走了，那就抵消了
                        minPossible = min(minPossible, trace(Next_RA, Next_PA, Next_RB, Next_PB));
                        free[transform(Next_RB, Next_PB)] = FREE;
                    }
                }

                if (!FLAGB) {
                    // painter B can't go
                    minPossible = 1 + trace(Next_RA, Next_PA, RB_, PB_);
                }

                free[transform(Next_RA, Next_PA)] = FREE;
                maxPossible = max(maxPossible, minPossible);
            }
        }

        if (!FLAGA) {
            // painter A can't go
            int minPossible = 0x3f3f3f3f;
            bool FLAGB = false;

            for (int dirB = 0; dirB < MAXDIRS; ++dirB) {
                int Next_RB = RB_;
                int Next_PB = PB_;

                if (canGo(dirB, Next_RB, Next_PB)) {
                    FLAGB = true;

                    free[transform(Next_RB, Next_PB)] = BLOCK;
                    // A走不了，所以B每走一次得分都要-1
                    minPossible = min(minPossible, -1 + trace(RA_, PA_, Next_RB, Next_PB));
                    free[transform(Next_RB, Next_PB)] = FREE;
                }
            }

            maxPossible = minPossible;

            if (!FLAGB) {
                // painter A, B can't go
                return 0;
            }
        }

        return maxPossible;
    }



private:
    int S, RA, PA, RB, PB, C;

    vector<int> free;  // 1代表free，0代表block

    int transform(int x, int y) {
        return (x - 1) * (x - 1) + y - 1;
    }

    // dir = 0 -> UP
    // dir = 1 -> DOWN
    // dir = 2 -> LEFT
    // dir = 3 -> RIGHT
    bool canGo(int dir, int& X, int& Y) {
        int CP_X = X;
        int CP_Y = Y;

        switch (dir) {
            case 0:
                if (CP_Y % 2 || CP_X == 1) {
                    return false;
                } else {
                    --CP_X;
                    --CP_Y;
                }
                break;
            case 1:
                if (CP_X == S || CP_Y % 2 != 1) {
                    return false;
                } else {
                    ++CP_X;
                    ++CP_Y;
                }
                break;
            case 2:
                if (CP_Y == 1) {
                    return false;
                } else {
                    --CP_Y;
                }
                break;
            case 3:
                if (CP_Y == CP_X * 2 - 1) {
                    return false;
                } else {
                    ++CP_Y;
                }
                break;
            default:
                return false;
        }

        if (free[transform(CP_X, CP_Y)] == BLOCK) {
            return false;
        }

        X = CP_X;
        Y = CP_Y;
        return true;
    }
};

int main() {
    int T;
    cin >> T;

    for (int i = 1; i <= T; ++i) {
        Solution A;
        cout << "Case #" << i << ": " << A.solve() << endl;
    }

    return 0;
}

Yeetzhee

分析

这题让我回忆起了，学习概率论的痛苦回忆。。。

先对Sample case#1进行分析，$N=3, M = 6, K = 2$，要分成两组，一组数量是1，另一组数量是2。

Pommel投了第一个骰子
Pommel投了第二个骰子
如果前两次结果相同，且都为$x$，那么第三次的结果一定要与$x$不同。

由现有条件可以得知，每次投骰子是独立的，并且结果是满足二项分布的（即，点数与$x$相同，和与$x$不同两种情况）。

这里解释一下，每个概率$p$是如何计算的。对于每个确定的投掷次数$X_i$，其概率满足N重伯努利分布，即投掷$X_i$次，恰好最后一次成功的概率。
$$
P(X = X_i) = \binom{X_i - 1}{0}p^0(1 - p)^{X_i - 1} \cdot p
$$

因此当前投出合法点数的数学期望为：
$$
E(X) = \lim_{n \to \infty} \left (\sum_{i=0}^{n} p \left (1 - p \right )^{n-1} \right ) = \frac{1}{p}
$$

投掷次数$X_i$	1	2	3	…	n
概率$P(X = X_i)$	$\frac{5}{6}$	$\frac{5}{6} \times \frac{1}{6}$	$\frac{5}{6} \times (\frac{1}{6})^2$	…	$\frac{5}{6} \times (\frac{1}{6})^{n-1}$

代入计算可得$E(x) = 1.2$

如果前两次结果不同，那么第三次的结果必然是前两次结果中的一个，此时的$p=2/6$，同样代入计算可得$E(x) = 3$。
因此总的期望为$1 + 1 + 1.2 \times \frac{1}{6} + 3 \times \frac{5}{6} = 4.7$，其中$\frac{1}{6}$为前两次结果相同的概率，$\frac{5}{6}$为前两次结果不同的概率。

所以对于分组数大于2的情况，每一个骰子的结果都可以分成“合法”和“非法”两种结果，也就意味着其符合二项分布。

这道题的难点在于如何表示状态。因为经过上述的分析，可以发现，我们不关心某个分组的数字具体是几，仅关心新骰子的数字与某个已有分组一致，还是不同。因此可以设$k_i$表示第$i$个分组的骰子数。假设$K=3$，第一次一定是$[1, 0, 0]$，第二次的结果可以是$[2, 0,0]$也可以是$[1, 1, 0]$（前者代表两次的结果相同，后者代表第二次与第一次的结果不同）。

同时我们也不关心，分组之间的顺序。如$[1, 2, 2]$与$[2, 1, 2]$是等价的。

因此我们可以用一个排好序的分组数量来唯一的标识一个状态。

假设$M = 4, K = 2$：

如骰子序列$[1, 2, 2]$，其状态为$[0, 0, 1, 2]$。如果新增一个骰子1，那么状态会变为$[0, 0, 2, 2]$，合法。
如骰子序列$[1, 1, 2]$，其状态为$[0, 0, 1, 2]$。如果新增一个骰子2，那么状态会变为$[0, 0, 2, 2]$，合法。
而骰子序列$[1,1,3]$，其状态为$[0, 0, 1, 2]$。如果新增一个骰子2，那么状态会变为$[0, 1, 1, 2]$，不合法。

解题思路

经过上述的分析，其实很容易联想到回溯和动态规划。

整体思路参考了“Lee215”的文章https://mp.weixin.qq.com/s/Mvpe3p0GQ8N0Os4o8Zs2mQ。

这是一个迭代期望的问题，当前状态$S$进入下一状态$S’$，存在一个“投到特定点数的骰子次数的数学期望”，还有一个“所有可能的下一状态$S_{i}^{‘}$距离胜利的期望次数的均值”，两者的和即是当前状态距离胜利次数的数学期望。

之所以要对“所有可能的下一状态距离胜利的期望次数”取均值，这是因为进入每一个下一状态$S_{i}^{‘}$都有各自的概率$p_i$，将其概率$p_i$与距离胜利的期望次数相乘再求和，即是“所有可能的下一状态距离胜利的期望次数的数学期望”。

#include <iostream>
#include <vector>
#include <map>

typedef long long ll;

using namespace std;

class Solution {
public:
    Solution() {
        cin >> N >> M >> K;

        A.resize(M, 0);
        status.resize(M, 0);  // 初始状态为全0

        for (int i = M - K; i < M; ++i) {
            cin >> A[i];
        }

        StatuMemo[A] = 0.0;
    }


    double dfs() {
        if (StatuMemo.count(status)) {
            return StatuMemo[status];
        }

        int valid = 0;  // 记录总共有多少个合法点数
        int i = 0;  // 骰子的点数
        int j = 0;
        double res = 0.0;  // 距离胜利的期望步数

        while (i < M) {
            j = i;

            while (j + 1 < M && status[j + 1] == status[i]) {
                // 由于状态内的数字顺序是可以随意调换的，因此区间[i, j]中如果都是值都一样，那么我们选择最右侧的那个
                // 这一步可以理解成，我们对已有的分组进行升序排序，如果我们选择了相等分组中最右的那个，就省去了排序这一步
                ++j;
            }

            if (status[j] + 1 <= A[j]) {
                // 可以理解成我投掷了一个点数j，那么其组内的骰子数没有超出我们目标的要求
                // 即，状态合法
                ++status[j];
                valid += j - i + 1;  // 因为区间[i, j]在投掷前，数量一致，也就意味着无论选了其中的哪个都是合法的

                res += dfs() * (j - i + 1);  // 累加所有状态距离胜利的期望步数

                --status[j];
            }

            i = j + 1;
        }

        double E = M * 1.0 / valid;  // 即当前投到合法状态的期望次数
        res = res * 1.0 / valid + E;  // 对下一个合法状态距离胜利的期望步数求平均值（即求期望），再加上当前进入下一个合法状态所需的期望次数

        StatuMemo[status] = res;

        return res;
    }


private:

    int N, M, K;

    vector<int> A;

    vector<int> status;
    map<vector<int>, double> StatuMemo;  // 存储状态status到离最终状态仍需投骰子次数的数学期望

};

int main() {
    int T;
    cin >> T;

    cout.precision(7);
    cout.setf(std::ostream::fixed);

    for (int i = 1; i <= T; ++i) {
        Solution A;
        cout << "Case #" << i << ": " << A.dfs() << endl;
    }

    return 0;
}

Kick Start Round F 2020解题记录

https://rlyown.github.io/2021/03/19/Kick-Start-Round-F-2020解题记录/

Author

Chaos Chen

Posted on

2021-03-19

Updated on

2023-06-30

Licensed under

#Kick Start 2020

Kick Start Round F 2020解题记录

ATM Queue

解题思路

优化

Metal Harvest

解题思路

优化

Painters’ Duel

解题思路

Yeetzhee

分析

解题思路

Author

Posted on

Updated on

Licensed under

Commentaires

Catalogue