最近的周赛,就没有不 outage 的,是越来越多的失业大军来 DDoS 吗?

周赛遇到了一道数组中所有 pair 的绝对值求和的问题 2731. Movement of Robots,直觉上 O(N^2) 的方式会 TLE,后来转换思路,发现有序数组用 O(N) 就可以做到了。

直觉上的做法,是在模拟 abs 运算:

1for i in range(N):
2    for j in range(i + 1, N):
3        res += abs(nums[i] - nums[j])

通过归纳这个过程,可以发现:

1N1 - N0, N2 - N0, N3 - N0, N4 - N0
2         N2 - N1, N3 - N1, N4 - N1
3                  N3 - N2, N4 - N2
4                           N4 - N3

对于 index i, 在 - 号左边会出现 i 次,因为有 i 个数比它小;在 - 号右边会出现 N - 1 - i 次,因为有 N - 1 - i 个数比它大。 那么我们可以直接用乘法计算了:

1sum(
2    nums[i] * (i - (N - 1 - i))
3    for i in range(N)
4)

那么为什么只有对有序数组才能得到这样的 O(N) 优化呢?

因为要求的是 abs,如果出现了逆序我们不知道某一步应该是 Ni - Nj 还是 Nj - Ni,会导致计数错误。

在做 JNI 的时候,Kotlin 与 Rust 传递复杂结构,需要手动赋值每一行属性,非常繁琐。 想到也许可以用 Protocol Buffer 作为中间载体,依赖自动生成的类。

效果倒是可以,input 和 output 都使用 ByteArray 了,两边各自反序列化一次就行。 但是吧,10 个属性的结构,在 Rust 下面生成的文件也就 60 行,在 Java 里有足足 2500+ 🤯

Protobuf java generate to large methods

只能说,凡事皆有代价。

archinstall 脚本还挺香,完整保留了 Win 11 分区和引导。

碰到的唯一需要调整的地方是,安装完毕提示 “Would you like to chroot into the newly created installation and perform post-installation configuration?” 我直接无视就重启了。

最好 chroot 然后添加 bootloader config,修改后 bootctl list 确认一下。大概率碰到的问题是,选了 linux-zen 的 kernel,和默认的 vmlinuz-linux & initramfs-linux.img 匹配不上。

用了 10 年的 Arch 了,之前都是 zsh 一行行敲命令安装,再也不想回去了。

一想到人类其实也被多巴胺奴役着,搞一个 super AI 管理社会,感觉也差不多?

对于程序员和开发人员来说,如果完成某项任务所需要付出的努力对他们是个挑战,却又恰好还在力所能及的范围内,他们就会觉得很有乐趣。因此,趣味性是一个峰值效率的标志。

……

乐趣是一个符号,意味着效能、效率和高产。

——「UNIX 编程艺术」