TopCoder SRM 446 DIV2 八月 16th, 2009
SRM446就是个悲剧。。。。比赛的时候在青岛yz家，借了他的本本来打，yz把我以前配置过的插件删了，只好重新弄，结果比赛开始后开了250p才发现有个隐蔽的地方没配置好，又重新配置插件……然后1000p，当时我愣是没看出广搜就行，因为不会算状态数╮(╯_╰)╭，于是写了个A*，本来敲完了交上去之后我在division summary里排第一，结果由于我对A*理解不够深(评估函数f(x)=g(x)+h(x)，f(x)相等时g(x)应该优先考虑)加上一句语句复制黏贴的时候黏贴到正确位置的下一行去了，于是就悲剧了，failed system test，division summary里的排名瞬间从1跌到31……还没完，过了几天发现rating降了，又一天后收到TC的E-MAIL得知违反了unused code rule，被判只得满分的20%，rating从1184瞬间被改判到984，比原来1045还低……反正这次亏大了，还不如不打呢，要再打N次才能进DIV1了，郁闷一下。
题解：
TopCoder SRM 446 DIV2 EASY 250p:水
TopCoder SRM 446 DIV2 MIDDLE 500p:水
TopCoder SRM 446 DIV2 HARD 1000p:搜索题……纯广搜就OK。先算一下状态数（方法从TC Forum里看来的），设A B C各有x y z个共n个，摆在一排，总共有n!/((x!)(y!)(z!))种摆法，然后再插两个“分隔符”进去成为三排，共有(n+2)!/(2*(x!)(y!)(z!))种，于是根据数据范围最多也就(12!)/(2*(3!)*(3!)*(4!))=277200种状态，宽搜完全可以过。不过C++纯广搜判重记录状态用string的set会TLE，得状态压缩一下，就用前面排成一排的状态来表示，最多12格，每格4种状态共4^12，不超过int，于是一个int的set就可以完成判重的任务了。当然也有别的办法压缩，反正总能在64位内搞定。hash也行，不过C++比较麻烦，hashmap不是标准STL，Java就太幸福了。
这题用A*或双向广搜可以快一些，而且常数NB的话也可以用string的set，似乎正好能过。当然状态压缩一下就更快了，system test里最坏情况大概在200~240ms。
PS:这次system test数据比较水，不加状态压缩的好多也都能Pass。我从TC Forum问来了一个20步的：{"BCB", "ACAC", "ABA"}，这个可以干掉很多未加状态压缩的A*（比如我的1000p代码的第二第三个版本TToTT），大家没事也可以去Practice Room里面找找没有直接字符串判重的，在先确定常数不小的情况下用这个数据challenge玩。
所有代码可参见Practice Room里我的代码。1000p用的是A*+状态压缩