Google CodeJam 2015 Round1B 总结

五一假期,和lch一起打了Google CodeJam 2015 Round1的第二场。由于我第一场已经晋级,第二场看不到题目了,所以就借lch的账号读了读题。

这次的题目比较坑,全部是贪心题。第一题如果细节没有考虑清楚就会WA,第三题又是那种第一感觉就没思路的题目,不过lch最终还是第一题过了大数据,二三题过了小数据,以50分300多名的成绩进入Round2了。

A.Counter Culture

题目大意:

对一个数$i$,有两种操作:

  1. 将$i$加$1$
  2. 将$i$反转

问把$14变成$n$最少的步数是多少。

通过手动模拟,可以发现规律。

如果我们要达到的数是一个$k$位数,那么我们首先应该把$14变成一个$k$位数,之后再变到$n$。

而为了快速的增加位数,一个明显最优的策略就是将当前数的最后一位变成$9$,然后通过反转,把$9$放到前面,之后再不停的加$1$。

通过观察:$1 -> 19 -> 91 -> 109 -> 901 -> 1009 -> 9001$

我们发现, $901$ 变成$1009 -> 9001$,并不如变成$1099-> 9901$好。

那么我们可以得出第二个结论:在变到某个数时(位数相同),应该将这个数分成两半,先将当前数的后半段变成目标数的前半段反转之后的数,之后将当前数反转,然后将当前数变到目标数。

至此,总体思路已经有了,先不停地增加位数,直到位数相等,之后根据结论二,求出最终结果。

需要注意的是,如果目标数的最后一位是$0$,由于将位数增加够之后,第一位必然是$1$,因此无法达到末尾是$0$的情况,对这种情况,先将目标数减一正常求出结果,之后再加一。

另外,如果要求的是数前半段是$’1000’$的形式,则不需要反转。

B.Noisy Neighbors

题目大意:给出$r×c$的网格,在网格中选$n$个格子,使得这些格子相邻的边最少。

这也是一道贪心的题目。

首先我们可以发现,对格子进行黑白染色,如果$n \leq \frac{r*c}{2}$,那么通过只选一种颜色的格子,可以做到没有相邻的边。

如果$n > \frac{r*c}{2}$,贪心的策略是,分两种情况,一种是填满黑色的格子,之后选白色的格子填使答案最小,另一种是先填满白色的格子,之后选黑色的格子填使答案最小。

这两种情况中较小的那个即为答案。

当时以为只有优先填黑色格子才是最优的,然而发现按照这样做,样例都不对。于是就以为贪心是错的。没有想到分情况讨论……

C.Hiking Deer

题目大意:有一只鹿绕着一个圆走一圈,它可以在任意时刻改变速度为任意值。在这个圆上还有一些人,给出他们的初始位置(角度),和走完一圈的时间,这些人会永远在这个圆上走。问这只鹿在走一圈的过程中至少会有几次和人相遇。

这道题真的是一点思路都没有……如果我比赛中遇到的话也是只能写写有两个人的时候的小数据。

后来看官方的analysis,才明白是如何贪心的。

首先,我们可以发现,鹿并没有必要在中途改变速度。

那么我们先考虑一个人的情况。如果鹿跑的足够快,在人到达原点之前就走完了一圈,那么他和人相遇的次数为1,如果它跑的慢了一点,在人第一次到达原点和第二次到达原点之间跑完一圈,那么它就不会与人相遇,如果它再慢一点,在人第二次到达原点和第三次到达原点之间跑完一圈,那么它还是会与人相遇一次,如果再慢,就是两次、三次,以此类推。

基于此,我们可以通过计算所有人到达原点的时间,对这个时间进行排序,之后枚举鹿到达原点的时间,如果鹿是第一次和这个人相遇,则减少一次相遇次数,之后每次相遇都增加一次相遇次数。在这个过程中取最小值即可。

这个算法ans的初始值为n,它的含义是,鹿最开始以极短的时间跑完一圈,超过了所有人。

由于每个人只会有一次减一的操作,之后的全都是加一,因此在$ans$大于$2×n$之后就没有必要继续找了。

排序可以用set,每个人每次只往set里添加他当前到达原点的时间,在把它取出来之后再将这个时间加上这个人跑一圈的时间放入set中。