前言

去年懵懵懂懂，一个人从头自闭到尾，到最后也没对上判题器，复赛第十遗憾离场。今年的开端也是十分不顺，我们提交的第一发线上14s，这时候前排已经有0.x的成绩了，一度陷入深深的自我怀疑之中。好在队友十分carry，多核输出的感觉真的挺爽，后来慢慢找到节奏，一路从二十多名到霸榜、守榜，拿下成渝第一、全国第三的初赛成绩，这段经历甚至比之后的决赛更加有趣。

开源地址：https://github.com/Chadriy/CodeCraft2020

放题

• 本端账 ID和对端账 ID为一个32位的无符 整数
• 转账金额为一个32位的无符 整数
• 转账记录最多为28万条
• 每个账 平均转账记录数< 10
• 账 A给账 B最多转账一次

三、初步思路
很自然的，意识到这个题目的核心是搜索，所以朴素DFS即可完成任务（万万没想到这就是官方的std），最后对所有结果进行去重和排序。
由于搜索中存在大量冗余，而且输出中环路按字典序输出，可以联想到去重和排序并不是必须的。考虑1->2->3->4->1的一条环路，在以2为起点时，同样有等价的环路2->3->4->1->2。在搜索中，这两次是冗余的。同理可推导知：在搜索过程中，邻接点中只需要遍历比起点id大的节点，这样即可省去去重；在搜索前对邻接表排序，即可省去排序。
这两个朴素的trick加上DFS就是我们的baseline，线下我记得有一个100w和一个300w的数据，我们前者都跑了好几十分钟的样子- -。之后陆续找了一些论文，都没有找到除了搜索之外的思路。

正赛

一、失落的开局
隐约记得放榜那天，第一发跑了14s的样子，那时候榜单前排已经有0.x级别的选手了，之后是深深的挫败感。正当我们几个人以为今年又是一轮游的时候，小白兔队的martin在知乎上开源了一个base。（开源的一般都很朴素吧），抱着这样的想法我们拉下来，跑了2.x。
心情复杂.jpg。
好累呀要不要弃赛。
如果今年还是solo的话，我可能就这样战术转移了。但是今年队友蔡总十分carry，关键时刻稳住了心态。在开源base中提到了反向搜索的概念，由于环路的起点终点重合，因此可以建立反向图，并通过反向搜索1-2层来替代正向搜索的最后部分。
在此后的很长一段时间里，我都以为正向搜索与反向搜索是数学等价的，区别只在于实现。此时我们的DFS是递归写法，大数据集很容易就爆栈。就在这样的不安中，我们把反向加到了两层，线上几次二分达到了2.x的分数。
这时候魔法少女出现了，同时把上限拉到了0.2x，之后的一周里我们都是深深的懵逼。就这样初赛过半，我们仍然没有进0.x。

PS：
1、反向搜索提速的原因是根据meet in the middle定理，搜索复杂度降到了根 N；
2、memcpy16字节提速的原因是，开O3被编译成仅两条汇编指令，走cacheline；
3、仅靠逻辑和底层，提升了100倍让我至今感觉很魔幻；