CodeChef September Challenge 2012

8.03 / 10 …

。。。似乎本月题目的整体质量有所下降?。。。。
不过 Knight Moving && Annual Parade 对我来说还是十分困难。。)
(某种程度上说 Knight Moving 对我来说更加困难。。。

Level 1:

Racing Horses:
签到题,略。

Kisses & Hugs: 数列
开始错推成 http://oeis.org/A002620
。。。后来发现题目读的不对。。所以应该是这个。。http://oeis.org/A027383

Three is Crowd: 数列。。
http://oeis.org/A050231
取补集后得到 Tribonacci。。之后矩阵乘。。

Chef World:数列。。。。
先写了个暴力。。。http://paste.ubuntu.com/1185570/
F[n] = 0, 5, 18, 44, 96, 195, 380, 719, 1332 ..
发现 OEIS 里面没有记载。。。。。。
手推后得到…一个四阶线性递推数列。。(常数注意。。
(常数优化两处。。一个是矩阵乘法里面。另一个是先预处理出所有 A 的 k 次幂。。

ChefTown Parade: 给定一个排列,问其中连续 k 项排序后恰好布满一个长度为 k 的区间的区间数。。
。。注意 nlogn 的算法会 TLE 。稍作整理后可以得到一个基于单调队列的算法。

Queries About Numbers: 数论。。
。第二问和第三问是对称的。。因式分解即可。。

Lights:。。写了一个暴力二分。。居然过了。(求更好算法。。。

Level 2:

Annual Parade:
给定一副有向图,每条边有一个权值,要求用若干个路径和环对图进行覆盖,每条边可以使用任意多次。。
没有覆盖的点产生额外的 C 代价,如果是路径则也要产生额外的 C 代价进行返回。。
现在共 T 组询问,对每组询问不同的 C 值。。返回最小代价。
——————
感到这里的 C 很不自然,第一印象是最大权闭合子图,于是开始尝试网络流建模,不过似乎无法解决每条边可以使用任意多次的问题。。
。。只要对原图求传递闭包后,问题就转换成了哈密顿圈覆盖,对于不存在的边,用 C 赋值上即可。

。对哈密顿圈覆盖。使用 KM 的话。。至此就得到了 O(Tn3) 的算法。。。
之后考虑不同 C 之间的冗余。。。那么如果对询问进行排序,如果当前某对匹配的权值是 C,那么对于更大的 C。。一定也是这组匹配。。
于是对询问离线处理。。仍然得到了 O(Tn3)。。但是 n 的规模会逐渐减小。。。

但是仍然各种 TLE 。。。
赛后对 CLJ 的代码 使用了初级鹰眼术。。。

发现我这一步误区了。。(。。。我这里似乎一直认为对于二分图最有匹配问题。。用特定的 KM 算法总是比费用流来的有效。
。但是这题里使用费用流可以逐步推流。。从而在不同的询问之间得到很自然的优化。。。

Knight Moving:
给定两组步长,(AX, AY), (BX, BY),问从 (0, 0) 开始出发到 (n, m) 结束。。
。有多少种不同的移动方案。。(无解或者无穷解或者有限解。。。
——————————————————
不同的移动方案定义为某一步所到达的格子不同。。。所以对于 AX == BX && AY == BY 的情况要单独处理。。。
。。除此之外还有各种各样的情况。。总之此题远比其看起来要复杂。。> <。

附加题:

Simultaneous Nim:
。。给定一组亦或和为 0 的数。。要求分割出尽可能多的组。。
使得每组内的亦或和同样为 0 .。。
——————————
写个暴力判断相同位置就能得到 0.03 分。。。
(。。ACRush 从第二天就开始狂刷这道题。。。而且我前面的题目没做完 。完全没动力做附加题啊。。。。
。。。后来最后几个小时实在没办法。。又回到这个题。。想了一个算法。。根据数字的最高为进行分组。。
然后从高组向下递降。。打印最高位为 0 (也就是亦或和为 0 )的所有组合。。。不过最后当然是没调出来啦。
。。。。。

External link:

http://www.codechef.com/SEP12/