In this post, we're interested in finding any or all rational solutions of the following equation: \[ ax^2 + by^2 + c = 0, \] or alternatively, all integer solutions to the Legendre equation: \[ \begin{equation} ax^2 + by^2 + cz^2 = 0, \label{eq:legendre} % \tag{Legendre Equation} \end{equation} \] where \(abc \neq 0\).
转眼间 2024 年快已经过去了……隔了好久没写娱乐相关的文章了，随便写几个作为今去年的年终总结得了……（然后震惊地发现我上次写游戏已经是四年前了……）
（可能有略微剧透，手动狗头）
前几天和 hls bibi 了一下。hls 推荐了 这个视频 给我。我是以一个批判的角度看视频的，就像我之前 review paper 一样，先把屁股坐住了再来找论据，所以大部分观点都是 biased 的，可能就是在 nitpicking。
The cost for Power Ups has changed since version 0.7, so this post is no longer applicable.
\(\newcommand{\eps}{\varepsilon} \newcommand{\R}{\mathbb{R}}\) Vampire Survivors is a game released in early access near the end of 2021. It received 110k recommendations in one month, which is pretty amazing given its minimal aesthetics and seemingly low production costs. I also played it a lot back then, but I won't talk about its gameplay here. Instead, this post discusses the (old) Power Up mechanism and some of the math behind it.
The Power Up mechanism in Vampire Survivors is similar to Kingdom Rush's Upgrades, where you spend the gold earned during gameplay to make permanent gains (e.g., increase move speed by x%). As per the notes in Fandom, the cost for a Power Up is defined as: \[ Price = \text{InitialPrice} \cdot (1 + \text{Bought}) \cdot \left(1 + \frac{\text{TotalBought}}{10} \right), \] where \(\text{InitialPrice}\) is the initial price of the Power Up, \(\text{Bought}\) is the number of purchased ranks for this Power Up, and \(\text{TotalBought}\) is the total number of purchased ranks among all Power Ups. What's interesting is that the order in which you buy Power Ups actually matters!
Intuitively, we should purchase expensive Power Ups first. For example, IGN recommends maxing out Power Ups with the highest initial costs first. However, this is not optimal. Suppose we have two Power Ups, A and B. A has 5 ranks with an initial price of 1, while B has only 1 rank with an initial price of 2. If we max out A first, the total price is: \[ 1 \times 1 + 1.1 \times 2 + 1.2 \times 3 + 1.3 \times 4 + 1.4 \times 5 + 1.5 \times 2 = 22, \] and if we max out B first, the total price is: \[ 1 \times 2 + 1.1 \times 1 + 1.2 \times 2 + 1.3 \times 3 + 1.4 \times 4 + 1.5 \times 5 = 22.5. \]
So, here is our central topic today:
What is the optimal order for buying all Power Ups?
几个星期前，我和朋友们去了趟湾区的后花园 Lake Tahoe，这里就随便写点东西记录一下。由于时间比较短，我们只过了一个周末，所以显得这篇文章尤为流水帐 23333
很多文件格式都是以一个 Magic number 开始，例如 Java 编译后的字节码文件就是以 CAFEBABE 开头。Wikipedia 上还有一个 表，里面放了很多好玩的 magic number，例如 DEADBEEF （还有个音乐播放器叫这个名字）和 FEE1DEAD （linux 的 reboot syscall 中用到）。于是我就心血来潮，能不能整出类似的看起来像英文词组的 magic numbers 。
试证明：如果一个大矩形能被有限个小矩形（大小不一定相同）平铺，且小矩形至少一条边为整数，则大矩形至少有一条变为整数。
解答
注意到积分 \[\int_{a}^b e^{2 \pi i x} \mathrm{d} x = e^{2 \pi i a} \left(e^{2 \pi i (b - a)} - 1 \right)\] 为 0 当且仅当 \(b - a \in \mathbb{Z}\)。对于平面上一个矩形区域 \(R\)，我们考虑如下积分：\[I(R) = \iint_R e^{2\pi i (x + y)} \mathrm{d} x \mathrm{d} y,\] 这个积分值为 0 当且仅当 \(R\) 至少有一边长为整数。令 \(R^*\) 为大矩形，\(R_{1, \dots, n}\) 为小矩形，则有 \[I(R^*) = \sum_{i} I(R_i) = 0,\] 故 \(R^*\) 至少有一条边长为整数。
事实上这个题还有很多种证明方法（14 种！），但我最喜欢的还是这个基于积分的证明。
参考资料：
今年上半年，ydl 找到我，说他和 maggie 订婚了，诚邀我去 Hawaii 参加婚礼。这我怎么能不参加呢？况且我还没去过 Hawaii，自然应该趁这个机会小小旅游一下。这里就随手记一下流水帐。这次旅游之后，终于知道 Hawaii, O'ahu, Waikiki, Honolulu 之间的关系了……
后来发现一个有趣的 trivia：夏威夷的 state fish 叫做 Humuhumunukunukuapua'a，虽然看起来很长，但是读起来非常有节奏感 23333
听说今年这两道题比较简单，我就来蹭蹭热度了。 P1 是一个不太难的题，但是我很可能把它想复杂了；P5 是一个非常巧妙的 brainteaser 。
求所有实数 \(\alpha\) 满足：对任意正整数 \(n\)，整数 \(\sum\limits_{i=1}^n \lfloor i \alpha \rfloor\) 均为 \(n\) 的倍数。
解答
令 \(S\) 表示所有满足要求的 \(\alpha\) 构成的集合。先来个小观察：如果 \(\alpha \in S\)，那么 \(2 + \alpha \in S\)：对于任何 \(n \in \mathbb{N}^+\)，有 \[\sum_{i=1}^n \lfloor i (\alpha + 2) \rfloor = \sum_{i=1}^n \left( \lfloor i \alpha \rfloor + 2i \right) = \sum_{i=1}^n \lfloor i \alpha \rfloor + n (n + 1)\]
于是我们就只需要研究 \([0, 2)\) 里的 \(\alpha\) 即可。
综上所述，\([0, 2) \cap S = \{0\}\)，故 \(S = \{2k: k \in \mathbb{Z}\}\).
（这个对 \(\alpha \in \mathbb{Q}\) 的讨论好丑好想优化掉……）
憨豆特工在一个 2024 行 2023 列的方格表上做游戏。方格表中恰有 2022 个方格各藏有一个坏人。初始时，憨豆不知道坏人的位置，但是他知道除了第一行和最后一行之外，每行恰有一个坏人，且每列至多有一个坏人。
憨豆想从第一行移动到最后一行，并进行若干轮尝试. 在每一轮尝试中，憨豆可以在第一行中任意选取一个方格出发并不断移动，他每次可以移动到与当前所在方格有公共边的方格内。（他允许移动到之前已经到达过的方格。）若憨豆移动到一个有坏人的方格，则此轮尝试结束，并且他被传送回第一行开始新的一轮尝试。坏人在整个游戏过程中不移动，并且憨豆可以记住每个他经过的方格内是否有坏人。若憨豆到达最后一行的任意一个方格，则游戏结束。
求最小的正整数 \(n\)，使得不论坏人的位置如何分布，憨豆总有策略可以确保他能够经过不超过 \(n\) 轮尝试到达最后一行。
解答
以下给出一个 \(n = 3\) 的构造。所有的图里蓝色为坏人，黄色表示可行路径。
我们先确定第二行的坏人在哪里。这一步直接扫就好了。有两种情况：
至于 \(n\) 为啥不能小于 3：我们就考虑一个 adversarial 的放坏人的方式，
又是一年 SIGYAO30。今年 SIGYAO30 在 Chicago，一来是因为之前美东美西都举办过 SIGYAO30 了，二来去年商定举办地点的时候，刚好 Chicago 有三个人，于是我们就决定放在 Chicago 了。事实上，我对芝加哥 downtown 印象挺好的，现代的城市，干净的街道，便捷的生活，低廉的物价，丰富的娱乐，多样的美食，就是冬天有点冷，南边不安全……
七年前才毕业，到现在居然已经毕业七年了。上次在芝加哥还是上次。半年不见，如隔六月。这次来芝加哥体验了好多游客项目，我在芝加哥住了一年半，但凡我稍微出门逛逛，也不至于一点也没逛。
A 点左上方的点没有坏人是因为 A 点是我们从上往下扫找到的第一个坏人。