Kick Start 2020B

KickStart是谷歌的线上笔试,每年会举办数轮,通过KickStart可以拿到工作面试名额。KickStart的有一定难度,但是又没有用到复杂的数据结构,是比较好的笔试筛选题。之前的题解在这里:

B轮的题目比A轮的题目还要简单一些,但是由于我第四题没做出来,所以排名直接是一千名开外了=,=。

1. Bike Tour

题目: 给一个数组H[N],找数出peak的数量,一个peak是指满足H[i-1]<H[i]>H[i+1]的i。

签到题,直接将i从下标1遍历到N-2判断就可以:

int solve(){
    int N;
    cin >> N;
    vector<int> h(N);
    for(int i=0; i<N; i++) cin >> h[i];
    int ret = 0;
    for(int i=1; i<N-1; i++) if(h[i]>h[i-1] && h[i]>h[i+1]) ret++;
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for(int i=1; i<=T; i++){
        int ret = solve();
        cout << "Case #" << i << ": " << ret << "\n";
    }
    return 0;
}

2. Bus Routes

题目: 有N趟公交,小明需要从第1趟坐到第N趟,第i趟公交在每X[i]天开一班,小明可以一天内坐多趟公交,如果他最晚得在第D天之前坐完公交到达目的地,那么他最晚在第几天出发?对于小数据集1<D<100;大数据集1<D<1e12。

数据范围有强烈的提示,应该用二分。但是我一开始并没有想到,还在想能不能用D减去出搭乘公交所用的时间,但是一想如果这样的话D的范围变化就没啥用了,所以这个方法应该不行。二分法将优化求解的问题转换为验证的问题,这个思维需要刻意训练一下才会容易想到,一般这样的题目有两个特点:

  • 寻找能够满足条件的最大值(或最小值),大于这个值就不满足条件,小于这个值就会满足条件。
  • 直接优化选出最大值比较困难,但是对于一个值,能比较快地判断是否能够满足条件,这样判断log(N)次就可以了,由于log(N)会很小,所以总体复杂度很可观。
bool valid(long start, vector<long>& X, long d){
    for(long x: X){
        if(start%x!=0) start = x*(start/x + 1);
        if(start > d) return false;
    }
    return true;
}

long solve(){
    long N, D;
    cin >> N >> D;
    vector<long> x(N);
    for(int i=0; i<N; i++) cin >> x[i];

    long l=1, r=1e12, mid;
    while(l<r){
        mid = (l+r+1)/2;
        if(valid(mid, x, D)) l=mid;
        else r=mid-1;
    }
    return l;
}

int main(){
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for(int i=1; i<=T; i++){
        long ret = solve();
        cout << "Case #" << i << ": " << ret << "\n";
    }
    return 0;
}

3. Robot Path Decoding

题目: 机器人在N*N的格子上接受指令移动,格子最右边与最左边相接,最上边与最下边相接。指令有上下左右四个,允许有嵌套如EEEE4(N)2(SS),最开始在(1,1)位置,求最后机器人所在的位置。

如果直接每步模拟移动肯定会超时,机器人的移动有这样的性质:最终的位置与中间的移动的顺序无关。所以我们只需要数向四个方向移动了多少步就可以,由于会有嵌套,所以要用一个栈存当前的倍率。

const int mod = 1e9;

int count(char target, string &s){
    long ret = 0;
    stack<long> times;
    times.push(1);
    for (int i=0; i<s.size(); i++){
        char c = s[i];
        if(c==target) ret = (ret + times.top()) % mod;
        else if(c>='2' && c<='9') {
            times.push(((c-'0') * times.top()) % mod);
            i += 1;
        }
        else if(c==')') times.pop();
    }
    return ret;
}

void solve(){
    string s, d="NSWE";
    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};
    cin >> s;
    long r=0, c=0, n;
    for(int i=0; i<4; i++){
        char cha = d[i];
        //cout << cha << " " << count(cha, s)<<endl;
        n = count(cha, s);
        r = (r + n*dr[i]+mod) % mod;
        c = (c + n*dc[i]+mod) % mod;
    }
    cout <<c+1<<" "<<r+1<<endl;
}


int main(){
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for(int i=1; i<=T; i++){
        cout<<"Case #"<<i<<": ";
        solve();
    }
    return 0;
}

4. Wandering Robot

题目: 机器人在W列H行的网格上行动,最开始在(1,1)位置,最终要到达最右下角(W,H)位置,每一步有一半的概率向右走一格,有一半的概率向下走一格,如果走到最下面一行,就会只朝右走;如果走到最右边一列,就会只朝下走。这个网格中间有一个矩形区域的洞,机器人如果掉到洞里就失败了,求机器人成功到达最右下角的概率。小数据集1<W,H<300,大数据集1<W,H<100000。

最先想到的是动态规划来做,到达格子(i,j)的概率等于到达(i-1, j)的概率的一半加上(i, j-1)的概率的一半,但是在最右边和最下边的时候要特殊算一下,我就是这里掉坑了,所以连小数据集都没过。这个方法的时间复杂度位O(WH),空间复杂度可以做到O(min(W,H))。

实际上,我一开意识到到动态规划会超时,所以就在想能过大数据集的方法。这个问题有这样几个性质:

  • 到达终点的概率等于1减掉坑的概率,掉坑的概率等于到达坑的左边和上边边缘的概率。
  • 另一种想法,机器人到达某些格子后,必定能能够到达终点,我们用这些点把终点围起来,算到达这些点的概率就可以。如取下图中的绿色格子就可以,这样斜着取(而非竖着取)的原因是绿色格子之间的概率不会有交叠,直接把到每个格子的概率累加起来就可以了。
  • 如何算到绿色格子的概率呢?可以直接用公式算:假如从开始向右移动r格,向下移动d格,到达绿色格子,那么概率为 \(C_{r+d}^d/2^{r+d} = \frac{(r+d)!}{r!d!2^{r+d}} \)。但是如果绿色格子在最下面一行或者最右边一列,需要特殊考虑一下(我当时没考虑到特殊情况)。

critical_points

好的,总体的思路就是计算到绿色格子的概率加起来就是结果了,但是在计算的时候需要算\((r+d)! \)与\( 2^{r+d} \),用double是存不下的,所以可以先取log再算取幂,即\( \frac{(r+d)!}{r!d!2^{r+d}} = 2^{log_2{(r+d)!} -log_2{d!}-log_2{r!}- (r+d)} \),这个方法确实没能够想到,是比较有用的策略。

const int S=100010*2;
double mdp[S];
double logA[S];

// 动态规划方法
double dp_solve(){
    int w, h, l, u, r, d;
    cin >> w >> h >> l >> u >> r >> d;
    memset(mdp, 0, sizeof(double)*(w+1));

    mdp[1] = 2;
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            if(i>=u && i<=d && j>=l && j<=r) mdp[j]=0;
            else mdp[j] = ((i==h? mdp[j-1]: mdp[j-1]/2) + (j==w? mdp[j]: mdp[j]/2));
        }
    }
    return mdp[w];
}

double inline step(int r, int d){
    return pow(2.0, logA[r+d]-logA[r]-logA[d]-r-d);
}

// 拆解方法
double solve(){
    int w, h, l, u, r, d;
    cin >> w >> h >> l >> u >> r >> d;
    double ret = 0;

    for(int col=l-1,row=d+1; col>=1&&row<=h; col--,row++){
        if(row==h) for(int ncol=1; ncol<=col; ncol++) ret += step(ncol-1, row-2)/2;
        else ret += step(col-1, row-1);
    }
    for(int col=r+1,row=u-1; col<=w&&row>=1; col++, row--){
        if(col==w) for(int nrow=1; nrow<=row; nrow++) ret += step(col-2, nrow-1)/2;
        else ret += step(col-1, row-1);
    }

    return ret;
}


int main(){
    ios::sync_with_stdio(false);
    int T;
    cin >> T;

    logA[0] = 0;
    for(int i=1; i<S; i++) logA[i] = logA[i-1] + log2(i);

    for(int i=1; i<=T; i++){
        double ans = solve();
        cout<<"Case #"<<i<<": " <<ans<<endl;
//        ans = dp_solve();
//        cout<<"Case #"<<i<<": " <<ans<<endl;
    }
    return 0;
}

总结来说,前三题比较简单,做的比较顺利,第四题难一些,但是小数据集没做出来比较可惜。在总的思路上和官方题解一致,也漏了关键点,大数据集做不出来也算合理。