devout

水晶宫里奏霓裳,准拟岳阳楼上

一些有意思的题的解答,题目见 这里

5.

\[\int_{0}^{\pi/2}x\cot x\mathrm dx\]

法1:

\[ \begin{aligned} \int_{0}^{\pi/2}x\cot x\mathrm dx &= \int_{0}^{\pi/2}x\mathrm d\ln\sin x \\ &= x\ln\sin x\Big |_0^{\pi/2}-\int_0^{\pi/2} \ln \sin x \mathrm dx \\ &= -\int_0^{\pi/2} \ln \sin x \mathrm dx \end{aligned} \]

\(\ln\sin x\)\([0,\pi/2]\) 上积分是经典的问题。

\[I=\int_0^{\pi/2} \ln \sin x \mathrm dx\]

\[\int_0^{\pi/2} \ln \cos x \mathrm dx=I\]

\[\int_0^{\pi/2} \ln \sin 2x \mathrm dx=I\]

\[ \begin{aligned} I&=\int_0^{\pi/2} \ln \sin 2x \mathrm dx \\ &=\int_0^{\pi/2} (\ln 2+\ln\sin x+\ln\cos x) \mathrm dx \\ &= \frac{\pi}{2}\ln 2+2I \end{aligned} \]

整理有 \(I=-\dfrac{\pi}{2}\ln 2\),故

\[\int_{0}^{\pi/2}x\cot x\mathrm dx=\frac{\pi}{2}\ln 2\]

法2:

运用 Feynman 方法,设

\[I(a)=\int_0^{\pi/2}\frac{\arctan(a\tan x)}{\tan x}\mathrm dx\]

所求即 \(I(1)\)

\[ \begin{aligned} I^\prime(a)&=\int_0^{\pi/2} \frac{1}{1+a^2\tan^2 x}\mathrm dx \\ &=\int_0^{\pi/2}\frac{1}{(1+a^2\tan^2 x)(1+\tan^2 x)}\cdot \frac{1}{\cos^2 x}\mathrm dx \ (t:=\tan x) \\ &=\int_0^\infty \frac{\mathrm dt}{(1+a^2t^2)(1+t^2)} \\ &=\frac{1}{a^2-1}\int_0^\infty (\frac{a^2}{1+a^2t^2}-\frac{1}{1+t^2})\mathrm dt \\ &=\frac{1}{a+1}\cdot \frac{\pi}{2} \end{aligned} \]

同时我们有 \(I(0)=0\),因此我们知道

\[I(1)=\int_0^1 I^\prime(a)\mathrm da=\frac{\pi}{2}\ln 2\]

8.

\[\int_0^\pi x\sin^4 x\mathrm dx\]

经典方法

\[ \int_0^\pi x\sin^4 x\mathrm dx=\pi \int_0^{\pi/2}\sin^4x\mathrm dx \]

然后点火,得到 \(\dfrac{3}{16}\pi^2\)

11.

\[\int(\sqrt{2\ln x}+\frac{1}{\sqrt{2\ln x}})\mathrm dx\]

先换元设 \(t=\sqrt{\ln x}\)

得到

\[\sqrt 2\int (2t^2+1)e^{t^2}\mathrm dt\]

\(e^{t^2}\) 分部积分

\[\int e^{t^2}\mathrm dt=te^{t^2}-\int 2t^2e^{t^2}\mathrm dt\]

把右边积分挪到左边即得 \((2t^2+1)e^{t^2}\) 的积分,最后得到 \(x\sqrt{2\ln x}\)

13.

\[\int_0^{\frac{\pi}{2}+1}\sin(x-\sin(x-\sin(x-\cdots)))\mathrm dx\]

看到的时候是相当震撼的,实际上不要被他欺骗了。

\(t=\sin(x-\sin(x-\sin(x-\cdots)))\),则 \(t=\sin(x-t)\)

两边对 \(x\) 求导得到

\[\frac{\mathrm dt}{\mathrm dx}=\sqrt{1-t^2}(1-\frac{\mathrm dt}{\mathrm dx})\]

\[\mathrm dx=(1+\frac{1}{\sqrt{1-t^2}})\mathrm dt\]

然后对初始积分做换元,得到

\[\int_0^1 (t+\frac{t}{\sqrt{1-t^2}})\mathrm dt=\frac{3}{2}\]

18.

\[\int_0^\infty \frac{x+1}{x+2}\cdot \frac{x+3}{x+4} \cdot \frac{x+5}{x+6} \cdots \mathrm dx\]

\(A=\dfrac{x+1}{x+2}\cdot \dfrac{x+3}{x+4} \cdots \dfrac{x+2n+1}{x+2n+2}<\dfrac{x+2}{x+3}\cdot \dfrac{x+4}{x+5}\cdots \dfrac{x+2n+2}{x+2n+3}=B\)

\(A<\sqrt{AB}=\sqrt{\dfrac{x+1}{x+2n+3}}\)

同理 \(A>\dfrac{x+1}{x+2}\cdot \dfrac{x+2}{x+3}\cdot \dfrac{x+4}{x+5}\cdots \dfrac{x+2n}{x+2n+1}=C\)

\(A>\sqrt{AC}=\sqrt{\dfrac{(x+1)^2}{x+2n+1}}\)

由极限的夹逼性知,\(\lim_{n\to\infty}A=0\),故原积分为 \(0\)

19.

\[\int_{0}^{\pi/2}\frac{\sin 23x}{\sin x}\mathrm dx\]

经典方法

\[\frac{\sin (2k+1)x}{\sin x}=1+2\sum_{n=1}^k \cos 2nx\]

证明直接数归。

于是直接做完了,积分值为 \(\pi/2\)

磐越长烟浩浩,磐梯万里蝉嘶。梦麟曾记凤凰知,二三年多少事。

游形只见三渡,翻身最上川原。不向锦官向临安,独钓雪月江畔。

【前言】

那天是 3 月 18 日,下了很大的雪。

虽然会津的雪要到四月底才能完全化完,三月末的雪也是罕见的。

我从若松坐电车回家,电车上挤满了人,听说往郡山去的公路封路了。

空气中弥漫着灰尘的气息,竟有些好闻,人们伞上的雪水化作污泥低落在地板上。

横风从门缝中穿过,蹂躏着摇摇欲坠的车躯,唯有人间的温存可以点亮已经黑蓝的天空。

从车窗里往外一望,苍白的天底下,远近横着几个萧索的荒村,没有一丝活气。

我的心禁不住悲凉起来了。

啊!这不是我六年来所待过的会津?

我所记得的会津不全于此。

我的会津比现在好得多了。


到会津的第一天是在一个寒冷的冬日,那时年纪还小,我爸牵着我的手,走在昏黑的路上。

那时候我总觉得,到一个新的地方后,总觉得路灯是昏暗的。

我以为是人生地不熟带来的错觉,直到我再次回到北京,才发现这里的街道也是昏暗的。

我爸问我,感兴趣的研究方向是什么?我说:图论。

那时候我还不知道,不是有点有边的问题就是图论问题,比如说我想说的那个问题,他有另一个名字,叫做对称二叉树。


会津大作为计算机传统强校,自然经费是充足的,所以不必担忧空调电费的问题。

实验室坐西朝东,冬冷夏冷,气候宜人。在这样优美的环境里,自然是少不了 30 度制热的空调。

并且这个空调还非常智能,知道热空气会上升,因此制热时一定要朝下吹。

这样自然是带来了更多温暖,只是苦了坐在空调出风口正下方的同学,是谁呢?

于是我自己解释说:会津本也如此,——虽然没有进步,也未必有如我所感的悲凉,这只是我自己心情的改变罢了,因为我这次离开,本没有什么好心绪。


会津大作为计算机传统强校,自然经费是充足的,所以有大把的钱来请老师来做 Guest Lecture.

其中印象最深的就是此前的学长 \(\mathfrak z\) 君了。

\(\mathfrak z\) 君的课确实是有实力的,只是当时太菜,实在听不懂,现在只记得一件趣事了。

\(\mathfrak z\) 君点其了 \(\mathcal P\) 君回答问题,然后在她上黑板演算的时候,拿出了手机对着她。

我们都觉得是偷拍,但是系主任愿意为其争辩:“读书人的事情,能叫偷拍吗...”

系主任说的很有道理,但是我的心不认同。

当然,我们仍未知道 \(\mathcal P\) 君知不知道这件事的发生。


夕阳西下,我依偎在他的肩上,寻求他的赞扬。

看台是空旷的,只有我们两个人,但是操场是更空旷的,一个人也没有。

“接下来的路要怎么走?”

那片运动场坐落在盆地的边缘,直接面对的就是青山。

山上的坟头遥不可及,只能看到零星两点。

当时的我们都坚信着,有一天会在胜利的彼岸相遇。

就这样,没有一丝迷惘的相信着。


分居两地是痛苦的,虽然会津和筑波坐火车也不过是三个半小时的路程,但是繁重的精神压力依旧将我们分开,这对于身体和心灵都是一种折磨。

又一次见到他的时候,他是成功者,我是失败者。

再一次见到他的时候,我是成功者,他是失败者。

最后一次见到他的时候,我是成功者,他是失败者。

我曾给他写信,他也曾给我回信,回信上是电报体一般的简短。

后来的某一天,我收到了他的最后一封信。

我静静的把信烧了,看着墟烟缓缓上升最后消失在粉红色的天空里。


夕阳西下,我想依偎在他的肩上,将脸埋入他温暖的胸膛,手抚过他低垂的发迹。他强颜欢笑,最后一次与我吻别。

我有许多话,想要连珠一般涌出:数据结构,stack,deque,Au,T/P,……但又总觉得被什么挡着似的,单在脑里面回旋,吐不出口外去。

“我们回不去了吗?”

我似乎打了一个寒噤。我就知道,我们之间已经隔了一层可悲的厚障壁了。

我也说不出话。

一个人哭着,走在回家的街头,是什么让曾经温柔的他变成这样?

那晚,我久久不能入眠,脑海里回想出这样一幅图景。


深蓝的天空中挂着一轮金黄的明月,下面是海边的沙地,都种着一望无际的金黄的菜花。

其间有一个少年,头戴项圈,手拿一把钢叉,向一匹猹尽力的刺去,那猹则将身一扭,反从他的胯下逃走了。

这个少年便是他,我第一次见到他的时候,还是我刚到会津一日无聊参观核电站遗址的时候,那时他正在浪江的归还困难区里面刺猹。(归还困难区:福岛核电站事故后部分核污染清理无法达标的地区,目前属于封锁状态)

他那时的活力现在去了哪里?

是因为他在归还困难区里待久了,核辐射照多了吗?

自然不是。

那晚,我的悲戚最终化为二字,命运。

为什么是命运?或许是因为他去了筑波,如果他不去的话,是不是就不会被命运捉弄了呢?

我和他一样选择了这条道路,我似乎已经看到了我不可避免的结局——在痛苦中让最后一丝灵魂被无情剥去。


于是我开始逃课,只需要混到毕业就好了。

我去徒步六十里越,我去荡舟猪苗代湖。

我带着你,你带着钱,我们去环游世界。

这样的生活多么的美好?

大概生活本是无边无际的,只是我们总是将其中的一部分定义为生活。

大概生命的意义也是无限的,只是我们有时太过忙碌,没有时间停下来扪心自问,生命的意义是什么?

只是我们有时太过轻松,于是化作一句我的生命没有意义。

生活就像光子,本身是充满随机和可能的,你从某个角度去观测他的时,他才被限定于某个偏振的方向。


【正文】

这次又在 ssf 考试,大概有始有终吧。

第一次参加 NOIP 普及组也是在这里,当时 chenzida 就坐我旁边,虽然当时还不认识。

记得考前教练说过,想不出来题了就多去上厕所,换一换思路。

记得 NOI2021 的时候看到一个老哥上厕所的时候拿着试题册在那里想,我觉得他就没有理解到上厕所的作用——上厕所的时候是没法思考的。

说回 NOIP2018,当时上厕所的时候看到的是一片荒芜的工地,现在这里已经是高楼林立的小区了,时间过得真快。

进门的时候看到了 liqingyang,他是爱,是暖,是希望,是北京的红太阳。

考场里 8:32 才发试题密码,真的抽象。

扫了一眼题,然后写,T1T2 很快就过了样例,希望不会锅。

然后发现 T3 T4 暴力刚好加起来 71 分,271 正是我第一次参加提高组(当时还是6道题)的分数,感觉有始有终也挺好的。于是打完暴力直接润了,还剩两个半小时,来写游记。

希望不要挂分,要不然就成小丑了。

顺带一提这次还带了很多吃的,想学习 ClCN 曾经的某篇博客的精神。

但是我开始写之后一个监考老师经常在我旁边转悠,不知道是不是觉得我是个奇怪的人。


【后记】

在这最后的几十分钟里,让我尽量理性的分析一下会津大这段经历。

我想,我还是爱会津大的,没有会津大的这段日子,我可能会成为如今被我称为”愚昧“的那一类人,在他人规定的测度下将生命定义为其中一个方向。

感谢会津大,让我能够站在一个比大部分人高的视角活出我的生命,让我拥有选择我的方向的权利。

当然,还有你。

我现在依旧时时想起你,浪江初遇的日子仿佛就在昨天。

不知道你现在在哪里,过的怎么样。

我时时想,我对你的爱是不是只是一个幸运的人对不幸的人的愧怍。

但相信不管是你,还是 \(\zeta\) 君,\(\ell\) 君,\(y\) 君,\(\gamma\) 君,\(\Upsilon\) 君,\(\mathcal Y\) 君或是没有来得及写下名字的每一个人,都能够自己定义出生命的意义。


【尾声】

主啊,我还有 500 英里就要回家。

疾驰在最上川原,风在我耳边嘶吼,与身旁的新干线竞速,我几乎就要成功。

我要去一个没有观测者的地方,那里没有外界的浮华,只有内心的赤诚。

那里左边是平原,右边是裂谷。

那里没有向左的不甘与向右的不敢,没有向左看的自信与向右看的自卑。

君だけがいるんだ。

对乌托邦不屑一顾者,终将落入自己的乌托邦。

1
2
3
4
5
6
7
# include <cstdio>
using namespace std;
int main()
{
printf("Goodbye World!\n");
return 0;
}

2023.11.18

首都师范大学附属中学 笃行楼403-18

期中考试地理死在了“常识”题上。

所以回去研究了一下潮汐的问题(

实际上海面是等势面,地球和太阳组成的系统和地球和月球组成的系统是类似的,我们仅分析地球和月球组成的系统。

这里面主要有这么几个势能:地球引力势,月球引力势,地月系转动势,地球自转势。

设地球质量为 \(M\),月球质量为 \(m\),月球质心到地球质心的矢量为 \(\vec d\),用 \(v\) 表示 \(\vec v\) 的模,以地球为原点,分析位置 \(\vec r\) 的势能情况

引力势很简单,\(\varphi_{earth}=-G\dfrac{M}{r},\varphi_{moon}=-G\dfrac{M}{|\vec r+\vec d|}\)

接下来是地月系转动势,虽然常说月球绕着地球转,但是实际上他们是绕着整个系统的质心转动。

设地月质心到地球的矢量为 \(\vec s\),设地月转动角速度为 \(\omega_{rot}\)

\(G\dfrac{Mm}{d^2}=Ms\omega_{rot}^2\)

地球表面的所有物体运动均需要角速度为 \(\omega_{rot}\),实际上忽略自转的情况下,他们的轨迹都是一个半径相同的圆,因此地球和月球的旋转系中的惯性是一个常数场,他的大小为 \(s\omega_{rot}\dfrac{\vec d}{d}\),选取恰当的零势面,得到 \(\varphi_{rot}=G\dfrac{m\vec d\cdot \vec r}{d^3}\)

接下来是地球自转的转动势,设地球自转角速度为 \(\omega_{aut}\),则 \(F=r\omega_{aut}^2,\varphi_{aut}=-\frac{1}{2}\omega_{aut}^2r^2\)

所以我们得到了海平面方程:

\[-G\frac{M}{r}-G\frac{m}{|\vec r+\vec d|}-G\frac{m\vec d\cdot \vec r}{d^3}-\frac{1}{2}\omega_{aut}^2r^2=C\]

考虑赤道平面的潮高,设 \(\theta=\langle \vec r,\vec d\rangle\),则有

\[\varphi(r,\theta)=-G\frac{M}{r}-G\frac{m}{\sqrt{r^2+d^2+2rd\cos \theta}}-G\frac{mr\cos\theta}{d^2}-\frac{1}{2}\omega_{aut}^2r^2=C\]

\(r(0)=r_0,r(\theta)=r_0+\Delta r\),则上面的方程可以写作

\[\varphi(r_0+\Delta r,\theta)=\varphi(r_0,0)\]

因为 \(\Delta r \ll r\),所以可以取 \(\varphi(r,\theta)\)\(\dfrac{\Delta r}{r_0}\) 的一次项近似,这样可以得到一个 \(A\Delta r=B\) 的形式。

因为 \(\varphi(r,\theta)\) 中都是 \(\varphi_i(\vec r)\) 的形式,所以提取出 \(\Delta r\) 之后,\(A\) 中每一项都是 \(\dfrac{\mathrm d\varphi_i(\vec r)}{\mathrm dr}\) 的形式,这刚好是加速度的相反数,而这些势能中,除了地球重力加速度产生的 \(g=9.8 m/s^2\) 以外,其他的加速度均远小于这个,因此在展开的时候只需要展开第一项的地球引力势能,其他的都可以用 \(r_0\) 来近似替代 \(r_0+\Delta r\)

\(-G\dfrac{M}{r_0+\Delta r}=-G\dfrac{M}{r_0(1+\dfrac{\Delta r}{r_0})}\sim -G\dfrac{M}{r_0}+G\dfrac{M\Delta r}{r^2}\),这里用到的是 \((1+x)^k\sim 1+kx(x\to 0)\).

因此得到方程

\[-G\frac{M}{r_0}+G\frac{M\Delta r}{r_0^2}-G\frac{m}{\sqrt{r_0^2+d^2+2r_0d\cos\theta}}-G\frac{mr_0\cos\theta}{d^2}-\frac{1}{2}\omega_{aut}^2r_0^2 \\ = -G\frac{M}{r_0}-G\frac{m}{d+r_0}-G\frac{mr_0}{d^2}-\frac{1}{2}\omega_{aut}^2r_0^2\]

化简可得

\[G\frac{M\Delta r}{r_0^2}=G\frac{m}{\sqrt{r_0^2+d^2+2r_0d\cos\theta}}-G\frac{m}{d+r_0}-G\frac{mr_0(1-\cos\theta)}{d^2}\]

将左右对 \(\dfrac{r_0}{d}\) 展开到平方项,化简得到

\[\Delta r=-\frac{3mr_0^4}{2Md^3}(1-\cos^2\theta)\]

所以潮汐的最高点在 \(\theta=0,\pi\) 处,最低点在 \(\pi/2,3\pi/2\) 处。

也就是说仅由地月作用就已经产生了一个“椭圆”的潮汐形状,而太阳引起的潮汐也是这个形状。

这也就不难解释为什么初一和十五是大潮了,因为此时日地月处于同一直线上,月球引起的潮汐和太阳引起的潮汐叠加形成大潮,而初七和二十三则形成小潮。

2.3

首先有

\[OPT\geq \frac{1}{m} \sum w_i\]

同时对于最长的链 \(\ell\)

\[OPT\geq \sum_{i\in \ell}w_i\]

考虑在 \([a_i,b_i]\) 时段每一个 processor 都在工作。

\[|\cup [a_i,b_i]|\leq \frac{1}{m}\sum w_i\leq OPT\]

同时对于 \((b_{i+1},a_{i+2})\) 里面的每一个工作,他一定有 \((b_i,a_{i+1})\) 里的前序,否则他就可以在 \((b_{i},a_{i+1})\) 里处理。

所以这些位置的长度之和不超过最长链,不超过 \(OPT\)

所以是 2-approximation.

2.5

取欧拉序,依次连边

2.10

考虑第一次最优选择是 \(e_1\) ,第二次最优选择是 \(e_2\)

\[f(S+e_1+e_2)+f(S)\leq f(S+e_1)+f(S+e_2)\]

整理得

\[f(S+e_1+e_2)-f(S+e_1)\leq f(S+e_2)-f(S)\leq f(S+e_1)-f(S)\]

所以 \(f\) 的选择是“凸”的。

所以他满足 2.6 中的条件

\[f(S+e)-f(S)\geq \frac{1}{k}(f(O)-f(S))\]

所以就得到了 \((1-1/e)\)-approximation

2.11

  1. 和 2.10 类似

假设存在一个 \((1-1/e+\epsilon)\)-approximation,我们给出一个 Set Cover 的 \(O(n^{O(\log\log n)})\) 的做法。

显然 Set Cover 可以很快转化成 Coverage Problem

我们可以从 \(1\)\(m\) 调用这个算法,设第一次得到一个大于 \((1-1/e+\epsilon)m\) 的返回值时,记录 \(k_0\),显然 \(OPT\geq k_0\)

然后把覆盖的这些位置全部都扔掉,然后再调用,再扔掉,最多调用

\[\ell\leq \log_{1/(1-\frac{1}{e}+\epsilon)}n<\ln n\]

次,最后得到的近似解 \(\leq \ell k_0\leq c\ln n\cdot OPT(c<1)\)

2.16

CF600F

濯足夜滩急,晞发北风凉。

惧怕着、惧怕着,北风来了,期中考的脚步近了。

Day 1

上午语文,错了两个选择。

出来 \(\zeta\) 君讲简答题讲的头头是道,感觉很不妙,要被 \(\zeta\) 君吊打了。

下午英语,头一次见到英语放第一天。

出来之后一对答案,前面都没错,感觉又行了。

下午无心复习,去 appralg 去了。

Day 2

上午先考数学。

看到第八题有点害怕,算了一会算出来了,但是大概会比较难。

第十题一眼回想起 \(xyc\) 射天狼,于是尝试 \(\gcd\) 证明了证明,感觉 2 个找不出来,随便胡了一会选了个 3

第十五题的 4 看上去挺对的,但是不会证,因为选择比较难所以觉得后面题也比较难,而且已经过去了快 50 分钟,就直接感性理解了一下把 4 也给选了。

然后就很慌,奋笔疾书的写。

导数怎么两个题都是 \(\zeta\) 条件啊(

写到了最后一道题,一看表还剩 40 分钟

是这选择抽象还是大题抽象啊(

21 一看第二问不会做,有点慌。

然后仔细想了五分钟发现斜线上一定是交替的,但是这怎么写啊(

然后想表述方法想了好久,最后直接答题卡上画了个矩阵给他穿了个串。

写完已经只剩下不到 15 分钟了。

于是就说直接写第三问能拿多少就拿多少吧。

感觉就直接上面有和他一样的和右边有和他一样的就分别扔进俩集合,然后再容斥一下,我怎么做完了?

于是写着写着就写完了 21.

出考场有人举出了 15 的 2 个的例子,死啦。

出考场发现 21(3) 小锅了,第一行和最后一列实际上是不能选的所以是 \(6\times 9\) 而不是 \(6\times 10\),不过大体思路还是对的,所以看能扣几分了。

然后地理。

地理一上来 5,6 两个题直接搞蒙了,纠结了好久,是跟随自己的内心还是不跟随,随后决定还是选了一个当时就觉得要错的答案。

这样做的代价也是惨重的,因为我花了 30 多分钟做选择。

然后大题就奋笔疾书。

不是你画图题怎么 8 分啊,为什么气温特征给 7 分,象屋给 6 分,论述题咋写啊。

写到最后都想要弃疗了,但是最后还是让不属于我的思想在答题卡上流淌到了最后一课。

下午很自闭,写了写物理化学,然后 appralg

Day 3

物理,看到第四题我差点做错就知道要出事。

11 题算了好久,感觉和算出来的结果和物理定律不符,但是还是决定相信自己算的。

后面的题好像还好,不是,最后一题是什么玩意。

出来一对选择发现 11,12 全算错了,直接自闭。

最后一科考化学,写到 14 的时候满脑子都是物理的事情,让自己静心了两分钟然后果然发现自己之前 14 做错了。

后面的题感觉还好吧。

下午找 hdq 讨论 11 题,讨论过程中,发现我 18(3) 也算错了,感觉真真要死了(

为什么考的全是课上讲的啊。

Day 4

回家玩了一整天,还看了电视剧 《对手》,感觉很好看。

Day 5

\(111+141+142+94(90)+100(92)+91(69)=679\)

感觉考的真的抽象,最后赋分也真的抽象。

Set Cover

Set Cover 是指给定 \(n\) 个元素 \(E=\{e_1,\cdots,e_n\}\) 以及 \(m\) 个集合 \(S_1,\cdots,S_m\subseteq E\),每个集合有代价 \(w_1,\cdots,w_m\),要求从这些集合中选出 \(k\) 个集合 \(S_{i_1},\cdots,S_{i_k}\) 使得 \(\cup_{j=1}^k S_{j_k}=E\),且 \(\sum_{j=1}^k w_{i_k}\) 最小。

Set Cover 是经典的 NP-complete 问题,同时在近似上也是经典的 LOG-APX-complete 问题。

关于 Set Cover 的 LOG-APX-hard 的证明可以参见 Fiege'98 的论文。

下面我们给出一个 Set Cover 的 \(H_n\)- 近似。

\(H_n\)-Approximation

Set Cover 的近似是非常易于入门的。

我们考虑一个自然的贪心,即每次选择一个“平均代价最小的集合”,把他加到集合中。

具体来说,初始我们选择的集合的集合 \(I=\emptyset\),设 \(\hat S_k\) 表示 \(S_k\) 中现在还没有覆盖的元素的集合,我们每次选择

\[\ell=\operatorname{argmin}_{|\hat S_k|>0} \frac{w_k}{|\hat S_k|}\]

并将他放入 \(I\) 中,再从所有 \(\hat S_k\) 中去掉 \(\ell\),直到我们选出了一个覆盖。

这个过程显然可以在多项式时间内实现,下面我们证明 \(\sum_{k\in I}w_k\leq H_n\cdot OPT\).

直觉上来讲,对于一个最优的覆盖 \(O\), \(\sum_{k\in O}w_k=OPT\),在 \(O\) 中一定存在一个集合的平均代价不超过 \(OPT/n\),覆盖了第一个之后,相应的,\(O\) 中一定存在一个集合平均代价不超过 \(OPT/(n-1)\) 来覆盖第二个,以此类推就得到了我们这个算法得到的结果 \(\leq OPT\cdot(1+\frac{1}{2}+\cdots+\frac{1}{n})\)

下面是严谨的证明:设加入 \(k\) 个集合之后还剩下 \(n_k\) 个元素没有被覆盖,则

\[\min_{|\hat S_k|>0}\frac{w_k}{|\hat S_k|}\leq \min_{k\in O \wedge |\hat S_k|>0}\frac{w_k}{|\hat S_k|}\]

根据盐水原理,右边小于等于

\[\frac{\sum_{k\in O\wedge |\hat S_k|>0}w_k}{\sum_{k\in O}|\hat S_k|}\leq \frac{OPT}{n_k}\]

\[\sum_{k\in I}w_k\leq \sum_{j=1}^k \frac{n_j-n_{j+1}}{n_j}OPT\leq H_n\cdot OPT\]

即完成了我们的证明。

Further Application

Set Cover 是(比较少有的) LOG-APX-complete 的问题,所以往往需要证明 LOG-APX-hardness 时往往需要从 Set Cover 来规约。比如 Steiner Tree 等问题的 hardness 可以通过非常简单的规约来解决。

同时这种调和级数的证明方法也可以用在 Steiner Tree Variants 的 \(O(\log n)\) Approximation 的正确性的证明。

习题:

对于两个集合 \(A,B,A\cap B=\emptyset\)\(B\) 中每个元素有代价 \(w_k\),对于 \(i\in A,j\in B\) 有额外代价 \(c_{i,j}\),选取 \(B\) 的一个非空子集 \(E\),最小化

\[\sum_{i\in E}w_i+\sum_{i\in A}\min_{j\in E}c_{i,j}\]

通过证明这个问题是 LOG-APX-hard 并给出一个 \(O(\log n)\) 近似算法,证明他是 LOG-APX-complete。

明日风回更好,今朝露宿何妨?

北京的冬天不像会津的冬天那样来的缓慢,也不像退役一样。

记得 \(\ell\) 君曾经对我说过,人不是一下子退役的,人是一点一点退役的。当时我并不曾理解他话中的含义。

但是我要告诉 \(\ell\) 君的是,北京的冬天不是一点一点来的,是一下子来的。

昨天下了一场雨,一场秋雨。

地理试卷曾经说过,一场秋雨一场寒。

昨天早上出门的时候下起了蒙蒙细雨,天是黑暗的,这正是我喜欢的天气。

进校门的时候感受到了一丝寒意,没有带伞,雨就落在我的帽上。

下雨天可以让人深思,这是 \(\ell\) 君喜欢的,也是我喜欢的。

寒冷的天气可以让人警醒,这是我喜欢的。

于是我拉着 \(\zeta\) 君去走一走,因为这难道不是 Golden Days 吗?

\(\zeta\) 君是无法理解 Golden Days 的美的,所以他没有去走一走。

他问了一个问题,为什么喜欢寒冷。

我回答,寒冷可以让人警醒。

他又问,为什么喜欢警醒。

我回答不上来了。


地理试卷曾经说过,垂死病中惊坐起,我的秋裤在哪里。

回家之后,我就为第二天翻出了秋裤。

第二天自然是冷的,只是早上并没有会津的冬天冷的厉害。

地理试卷告诉我们,这是因为雪的反射率大。

直到升旗的时候,我才重新感受到北京冬天的威力。

因为北京的冬天不是一点一点来的,是一下子来的。

地理试卷曾经说过,北京在冬天常刮西北风。

但是今天不是刮的西北风,而是刮得东南风,我为什么知道是因为我们上操站的位置刚好是操场的迎风坡。

地理试卷曾经说过,迎风坡降水多,阳坡光照充足

但是今天的迎风坡没有降水,阳坡也没有充足的光照,只有大量的狭管效应。


回班之后自然是五指僵曲不能动,于是找 \(\zeta\) 君闲聊,亦各言其志也已矣。

大概之前在想,怎么样能追求自己的快乐,就像山人江伟或者浩海尼奥一样,这似乎显然和经济上的充盈是矛盾的。

但是 \(\zeta\) 君狠狠地点醒了我,似乎瞬间(暂时的)压力就烟消云散了。

\(\zeta\) 君说,今天不是 Golden Days。

我曾经不这么认为,因为今天的天气让人警醒。

我现在也不这么认为,因为人是需要警醒的。

但是人为什么要警醒?


下午是山人江伟的课,他讲了讲他买彩票的故事。

他非常喜欢一把(?)唐朝的古琴,想要买,但是这个琴在 2003 年的时候拍卖出了 800 万,他自然是买不起的。

于是他从 00 年开始买彩票,一次买 10 注,这样如果中了钱就够了。

他买了十年,到了 2010 年,这个琴又一次被拍卖了,这次拍出了 1.5 亿的高价。

于是他从此以后一次买 100 注。

可惜他现在没有中大奖。

大概如果他中了大奖的话,他应该也不会去买那把琴,而是会选择辞职吧。

但是我是小人,山人江伟是君子,我想他的精神是高尚的。

\(\zeta\) 君说,我很世俗。

但是我不这么觉得。

Description

对于 \(A,B\in \mathbb F_2^n\),定义 \(A\cdot B=\sum_{i=1}^n a_ib_i\),并定义 \(T_n=\{A\in\mathbb F_2^n|A\cdot A=3\}\)

证明:对于互不相同的 \(A_1,A_2,\cdots,A_{n+1}\in T_n\), \(\exists 1\leq i<j\leq n+1\) 使得 \(A_i\cdots A_j=1\).

Solution

\(A_k(i)\) 表示 \(A_k\)\(x_i\) 的值。

\(B_k=\{i=1,2,\cdots,n|A_k(i)=1\}\),即 \(A_k\) 中每个元素的值为 1 的下标位置。

由抽屉原理,\(n+1\)\(A_k\) 代表 \(n+1\) 个颜色的小球,每个颜色有三个小球,放入 \(A_k(i)=1\) 的三个位置(抽屉)中,则存在一个抽屉中有至少两个不同颜色的小球,即 \(\exists 1\leq i<j\leq n+1\) 使得 \(A_i\cdot A_j>0\)

因为 \(A_i\cdot A_j\in \{0,1,2\}\)

  • \(A_i\cdot A_j=1\),则命题成立.
  • 否则 \(\forall A_i\cdot A_j\neq 0,A_i\cdot A_j=2\).

假设 \(\forall A_i\cdot A_j\neq 0,A_i\cdot A_j=2(*)\)

引理1: 对于互不相同的 \(i,j,k\),若 \(A_i\cdot A_j=A_j\cdot A_k=2\),则 \(A_i\cdot A_k=2\)

证明: 不妨设 \(A_j(1)=A_j(2)=A_j(3)=1,A_i(1)=A_i(2)=1\),因为 \(A_j\cdot A_k=2\),所以 \(A_k(1),A_k(2)\) 中至少有一个为 \(1\),故 \(A_i\cdot A_k\neq 0,A_i\cdot A_k=2\). \(\Box\)

即我们可以把 \(A_i\) 分成若干组 \(E_1,E_2,\cdots,E_m\),每一组内的任意两个元素的点乘恰好为 2,而不同组的元素的点乘为 0.

形式化的:设 \(C_k=\{j=1,2,\cdots,n+1|A_j\cdot A_k=2\}\),则 \(\forall j\in C_k,C_j=C_k\),而 \(\{C_k\}_{k=1}^n\) 中所有不同的元素构成 \(\{E_k\}_{k=1}^m\)

\(D_j=\cup_{i\in E_j}B_i\),即 \(E_j\) 中某个元素在该位上为 1 的下标集合(\(E_j\) 覆盖的下标位置)

引理2: \(\forall i\neq j,D_i\cap D_j=\emptyset\),即 \(E_i\)\(E_j\) 覆盖的下标无交集。

证明: 反证法:若 \(D_i\cap D_j\neq \emptyset,\) 则存在 \(k\in E_i,\ell\in E_j\) 使得 \(B_k\cap B_\ell\neq \emptyset\),即 \(A_k\cdot A_\ell \neq 0\),则 \(A_k\cdot A_\ell=2\),与 \(k,\ell\) 在不同的 \(E_i,E_j\) 中矛盾。 \(\Box\)

引理3: \(|D_k|\geq |E_k|\),即大小为 \(\sigma\) 的一个集合 \(E_k\) 至少覆盖了 \(\sigma\) 个位置。

证明:

对于 \(\sigma\leq 2\),不难证明。

\(E_k=\{e_1,e_2,\cdots,e_\sigma\}\),

不妨设 \(B_{e_1}=\{1,2,3\}\),即 \(A_{e_1}=1,1,1,0,\cdots\)

因为 \(A_{e_2}\cdot A_{e_1}=2\),不妨设 \(B_{e_2}=\{1,2,4\}\)

则对于 \(\sigma=3,4\)\(\{1,2,3,4\}\subseteq D_k\)\(|D_k|\geq \sigma\)

对于 \(\sigma\geq 5\)

\(B_{e_3}\cap B_{e_1}\neq \{1,2\}\),则不妨设 \(B_{e_3}=\{1,3,4\}\)

\(B_{e_4}\) 只能等于 \(\{2,3,4\}\)。(类似第二问证明)

此时不存在合法的 \(B_{e_5}\)

\(B_{e_1}\cap B_{e_3}= \{1,2\}\),不妨设 \(B_{e_3}=\{1,2,4\}\)

\(B_{e_4}\cap B_{e_1}=\{1,2\}\),否则无法同时满足 \(A_{e_2}\cdot A_{e_4}=A_{e_3}\cdot A_{e_4}=2\),则不妨设 \(B_{e_4}=\{1,2,5\}\)

以此类推,\(B_{e_k}\) 唯一确定,不难发现此时 \(|D_k|=\sigma+1\),引理3即证。 \(\Box\)

应用引理3,对于所有的 \(E_k\) 求和,得到

\[n=\sum_{k=1}^m |D_k|\geq \sum_{k=1}^m |E_k|=n+1\]

的矛盾,即假设 \((*)\) 不成立,原命题成立。

Dirichlet 问题

Dirichlet 问题是指对于实值函数 \(V\in C([0,1])\),求常微分方程

\[ (DP) \left\{\begin{matrix} -u^{\prime\prime}(x)+V(x)u(x)=f(x) & x\in [0,1]\\ u(0)=u(1)=0 & \end{matrix}\right. \]

的解。

我们接下来会证明,当 \(V\geq 0\) 恒成立的时候,\((DP)\) 恒有唯一解。

唯一性

\(\color{red}定理1\) 假设 \(V\geq 0\)\(f\in C([0,1]),u_1,u_2\in C^2([0,1])\)\((DP)\) 的解,则 \(u_1=u_2\)

证明:

\(u=u_1-u_2\),则 \(u\) 满足

\[\left\{\begin{matrix} -u^{\prime\prime}+Vu=0 \\ u(0)=u(1)=0 \end{matrix}\right.\]

\[ \begin{aligned} 0&=\int_0^1 [-u^{\prime\prime}+Vu]\bar u\mathrm dx \\ &= -\int_0^1 u^{\prime\prime}\bar u\mathrm dx+\int_0^1 V|u|^2\mathrm dx \text{ (分部积分)}\\ &= -u^\prime(x)\bar u(x)\Big |_0^1 +\int_0^1 u^\prime\bar u^\prime\mathrm dx+\int_0^1 V|u|^2\mathrm dx \ (\bar u(0)=\bar u(1)=0) \\ &= \int_0^1 |u^\prime|^2\mathrm dx+\int_0^1 V|u|^2\mathrm dx\geq \int_0^1 |u^\prime|\mathrm dx \end{aligned} \]

所以 \(u^\prime =0,u\) 为常函数, \(u=u(0)=0\).

\(V=0\) 的情况

我们先考虑 \(V=0\).

\(\color{red}定理2\) 定义

\[ K(x,y)=\left\{\begin{matrix} (x-1)y & 0\leq y\leq x\leq 1 \\ (y-1)x & 0\leq x\leq y\leq 1 \end{matrix}\right. \in C([0,1]\times [0,1]) \]

并定义运算 \(A\)

\[Af(x)=\int_0^1 K(x,y)f(y)\mathrm dy\]

\(A\in\mathcal B(L^2([0,1]))\) 为 compact symmetric 算子,且对于 \(f\in C([0,1]),Af\) 是常微分方程

\[ \left\{\begin{matrix} -u^{\prime\prime}(x)=f(x) & x\in [0,1]\\ u(0)=u(1)=0 & \end{matrix}\right. \]

的唯一解。

注:实际上在下面的证明过程中,我们并不依赖 \(K(x,y)\) 具体是多少,定理成立只需要 \(K(x,y)\) 有界实值即可,但这里明确给出 \(K\) 是因为这个就是解决 Dirichlet 问题的 Kernel。

证明:

先证 \(A\) 是紧(compact)的:设 \(C=\sup_{[0,1]\times [0,1]} K(x,y)\)

\[ \begin{aligned} |Af(x)| &= |\int_0^1 K(x,y) f(y)\mathrm dy| \\ &\leq C\int_0^1 |f(y)|\mathrm dy (\text{ Cauchy-Schwarz 不等式}) \\ &\leq C(\int_0^1 1^2)^{1/2}(\int_0^1 |f(y)|^2 \mathrm dy)^{1/2} \\ &= C ||f||_2 \end{aligned} \]

\(Af\) 一致有界,同理对于 \(\forall x,z\)

\[|Af(x)-Af(z)|\leq \sup_{y\in [0,1]} |K(x,y)-K(z,y)|\cdot ||f||_2\]

\(Af\) 是连续的

有了这两个性质,运用 Arzela-Ascoli Theorem 就可以证明 \(A\) 是紧的。

接下来证明 \(A\) 是对称(symmetric)的

\[ \begin{aligned} \langle Af,g \rangle_2 &= \int_0^1 \Big[ \int_0^1 K(x,y)f(y)\mathrm dy\Big] \overline{g(x)}\mathrm dx (\text{ 交换积分次序}) \\ &= \int_0^1 f(y) \overline{\Big[\int_0^1 \overline{K(x,y)} g(x)\mathrm dx \Big]}\mathrm dy \\ &= \int_0^1 f(y) \overline{\Big[\int_0^1 K(x,y) g(x)\mathrm dx \Big]}\mathrm dy \\ &= \langle f,Ag \rangle_2 \end{aligned} \]

\(A\) 是对称的。

不难验证 \(u=Af\) 确实是函数的一个解。

\(V\neq 0\) 的情况

首先给出一个 sketch。

问题等价于求解 \(-u^{\prime\prime}=f-Vu\),即求 \(u=A(f-Vu)\),即求 \((I+Av)u=Af\).

\(u\) 写作 \(u=A^{1/2}v\),注意我们这里只是一个 sketch,我们接下来会证明 \(A^{1/2}\) 存在且为紧且对称的(说明他有逆)

则原来的问题转化成

\[A^{1/2}(I+A^{1/2}VA^{1/2})v=Af\]

\[(I+A^{1/2}VA^{1/2})v=A^{1/2}f\]

我们接下来要做的就是证明 \(A^{1/2}\) 是存在的,但这还不足以说明问题,因为我们还需要求出 \(v\),这需要 \((I+A^{1/2}VA^{1/2})\) 是可逆的,

\(\color{red}引理3\) \(NULL(A)=\{0\}\),且 \(A\) 存在一组无穷特征值 \(\{\lambda_k\}_k\) 即其对应的正交单位特征向量 \(\{u_k\}_k\) 满足

\[\left\{\begin{matrix} u_k(x)=\sqrt 2\sin 2k\pi x & \\ \lambda_k=\dfrac{1}{k^2\pi^2} & \end{matrix}\right. \forall k\in\mathbb N\]

证明:

因为 \(NULL(A)=\overline{Range(A)}^\bot\),只需证明 \(\overline{Range(A)}=L^2([0,1])\) 即可。

\(u\)\([0,1]\) 上的多项式,取 \(f=-u^{\prime\prime}\),此时 \(Af=0\) 是唯一的 \((DP)\) 的解,故 \(Range(A)\) 包含所有的 \([0,1]\) 上的多项式。

因为 \([0,1]\) 上的多项式是致密的,且任意一个连续函数可以用多项式来逼近 (Weierstrass Approximation Theorem)

\(\overline{Range(A)}=L^2([0,1])\).

接下来我们求解 \(A\) 的各个特征值。

\(\lambda\neq 0,Au=\lambda u\),则 \(u=\dfrac{1}{\lambda}A\Rightarrow u=A(\dfrac{1}{\lambda}u) \Rightarrow -u^{\prime\prime}=\dfrac{u}{\lambda}\),这是最基本的常微分方程,他的解是三角级数 \(u=A\sin \dfrac{1}{\sqrt\lambda}x+B\cos\dfrac{1}{\sqrt \lambda}x\)

因为 \(u(0)=0\),所以 \(B=0\),因为 \(u(1)=0\),所以我们要求 \(\dfrac{1}{\sqrt\lambda}\in \mathbb N\pi\),故 \(u(x)=A\sin k\pi x\),为了满足 \(||u||_2=1\),我们可以解得 \(A=\sqrt 2\).

接下来我们证明 \(A^{1/2}\) 存在,且是紧且对称的。

\(\color{red}引理4\) 对于 \(f\in L^2([0,1])\) 且有傅里叶级数表示

\[ \left\{\begin{matrix} f(x)=\sum_{k=1}^\infty c_k\sqrt 2 \sin k\pi x & \\ c_k=\int_0^1 f(x)\sqrt 2\sin k\pi x\mathrm dx & \end{matrix}\right. \]

定义算子 \(B\)

\[Bf(x)=\sum_{k=1}^\infty \frac{1}{k\pi }c_k\sqrt 2\sin k\pi x\]

\(B\)\(L^2([0,1])\) 上为紧且对称的有界算子,且 \(B^2=A\).

证明: \(B^2=A\) 不难验证,剩下的咕咕咕

接下来我们对于实值函数 \(V\in C([0,1])\) 定义 \(m_Vf=Vf\),则 \(m_V\in\mathcal B(L^2([0,1]))\) 且是对称的(\(V\) 是连续有界的故 \(m_V\) 有界,\(V\) 是实值函数故 \(m_V\) 是对称的)

\(\color{red}引理5\) \(T=Bm_V B\) 满足 1)\(T\) 是紧且对称的 2) \(T\in\mathcal B(L^2([0,1]),C([0,1]))\)

证明:

因为 \(B\)\(m_V\) 都是紧且对称的,所以 1) 可以直接得出。

对于 2),我们只需要证明 \(B\in\mathcal B(L^2([0,1]),C([0,1]))\).

延续此前对 \(f\) 的傅里叶级数表示的记号,

\[Bf=\sum_{k=1}^\infty \frac{c_k}{k\pi}\sqrt 2\sin k\pi x,\] \[\frac{c_k}{k\pi}\sqrt 2 \sin k\pi x| \leq \frac{|c_k|\sqrt 2}{k\pi}\leq \frac{|c_k|}{k},\] \[\sum_{k=1}^\infty \frac{|c_k|}{k}\leq (\sum_j \frac{1}{k^2})^{1/2}(\sum_{k}|c_k|^2)^{1/2}=\frac{\pi}{\sqrt 6}||f||_2\]

Weierstrass M-test\(|Bf(x)|\leq \dfrac{\pi}{\sqrt 6} ||f||_2\),即证明 \(B\) 是有界的。

\(\color{red}引理6\) \(I+Bm_VB\) 可逆

根据 Fredholm Alternative,一个紧对称算子的逆算子存在当且仅当他的零空间是平凡的。

假设 \((I+Bm_VB)g=0\),则

\[ \begin{aligned} 0 &=\langle (I+Bm_VB)g,g\rangle \\ &= ||g||_2^2+\langle Bm_VBg,g\rangle (\text{ B 是对称的}) \\ &= ||g||_2^2+\langle m_V Bg,Bg\rangle \\ &= ||g||_2^2+\int_0^1 V|Bg|^2\mathrm dx \\ &\geq ||g||_2^2 \end{aligned} \]

所以 \(g=0\)\(NULL(I+Bm_VB)=\{0\}\)\(I+Bm_VB\) 可逆。

\(\color{red}定理7:\) 对于 \(V\in C([0,1])\)\(V\geq 0\) 的实值函数和 \(f\in C([0,1])\),存在唯一 \(u\in C^2([0,1])\) 为常微分方程

\[ (DP) \left\{\begin{matrix} -u^{\prime\prime}(x)+V(x)u(x)=f(x) & x\in [0,1]\\ u(0)=u(1)=0 & \end{matrix}\right. \]

的解。

证明:

\(v=(I+A^{1/2}m_VA^{1/2})^{-1}A^{1/2}f,u=A^{1/2}v\),则

\[ \begin{aligned} u+A(Vu) &=A^{1/2} v+A^{1/2}[A^{1/2}m_VA^{1/2}]v \\ &= A^{1/2}(I+A^{1/2}m_V A^{1/2})v \\ &= Af \end{aligned} \]

两边同时求二阶导,得到

\[u^{\prime\prime}-Vu=-f\]

整理即得

\[-u^{\prime\prime}+Vu=f\]

不难验证 \(u\) 也满足边界条件,故存在唯一的

\[u=A^{1/2}(I+A^{1/2}m_VA^{1/2})^{-1}A^{1/2}f\]

解决 Dirichlet 问题。

前言

波神留我看斜阳,唤起层层细浪。

高三也不过是这样,在银杏叶黄的烂漫的季节,骑车回家的路上总能望见绯红的轻云,但银杏叶下也缺不了成群结队的“高考”的速成班,手里拿着致密的复习资料,桌上凌乱的堆着书本和卷子,形成一座富士山。也有摒弃一切杂念,专心学习,于外界断绝一切联系的,宛如未出闺阁的小姑娘一般,还要在电子词典中摆弄摆弄秀发,实在标致极了。

ocw 的课程里有几门可以看,有时还值得去思考思考;倘在中午,407 里面的几间电脑倒也还可以用一用的。但到傍晚,晚自习的教室里就容不下接水的同学了。问问上晚自习的同学,答道:那是在打牌。

到别的地方去看一看,如何呢?

我就往会津的计算机专门学校去,从东京出发,不就便到一处驿站,写到:日暮里。不止怎地,我到现在还记得这名目。其次却只记得郡山了,这是去若松新干线能坐到最远的地方。会津是一个市镇,并不大;冬天冷的厉害,还没有中国的学生。

从此就见到许多有趣的先生,首先进来的是一个身高不高戴黑框眼镜的先生,身材不高,神采奕奕,一站到讲台上,便用急促的一开始让人不适应的声音做起了自我介绍:“我就是叫做山人江伟(Yamabito Erai)的...”

山人先生担任的是国文课,国文课曾经有另一位女先生,但是名字总被认成是男生,据同桌竞宇小五郎君称今日(10.26)是上一位先生的生日,小五郎君还给她送了礼物。

山人先生是喜欢分享自己的生活的,一日他说道“我每日吃两餐饭,早餐吃八个馅饼。”我们自然是笑而不信也的,只是后来一日我去找他,发现他正拎着8个韭菜盒子(和馅饼差不多大)往宿舍走。

另一位有趣的先生是任化学的浩海尼奥(Koukai Amaoku)先生,浩海先生是一位英俊帅气且幽默的先生。大约发生在他身上的事情过于的多了,以至于这里地方太小,写不下,这里姑且举出一二。

一日浩海先生点同学回答问题,曰“我点名并不是为了为难大家,只是让大家共同进步尔。”

然后点了嘉齐太郎君,曰“太郎君,你先来说,你脸皮最厚。”

会津大的校园是相当狭小的,东西 672 步,南北 596 步,就已经走到头了,以至于连一个小操场都无法塞进去。但是与狭小的校园相对的,食堂相当的气派,以至于偶尔点外卖的同学们都会被通报。

食堂门口常常能看到一位不知是讲师还是学生的男子,总是呆呆地盯着一处不动,后来一问才知道原来是系主任。因为平时学习较为刻苦,所以成绩多少还是不错的,因此也常常与系主任聊天,得知我不是本地人(虽然会津大本地人并不多)之后,他神秘兮兮的跟我说:“你知道吗,从东京到若松有四种走法。”

我当然是知道的,第一条坐东北新干线到郡山,再换磐越西线;第二条坐上越新干线到浦佐,再换只见线,途中要翻越谷川岳和六十里越峠,在日本已经足以算是险要的地势;第三条坐上越新干线到新潟,再坐另一个方向的磐越西线;第四条如果你有闲心,完全从浅草坐东武特急直接到鬼怒川温泉,再转乘会津铁道。早在我在若松住的前三个月里,我就已经把这一带可以坐过的铁路线都坐了一遍。

但是我不明白为什么他要和我说这个。

系主任非常喜欢发表讲话,毕竟这是计算机专门学校,他所讲的话的往往是令人热血沸腾的。记得第一次集会,系主任在台上高喊“你们的理想是什么?”台下我身边被感染的同学们则以“图灵奖”高声回应。我突然感到了一层可悲的厚障壁,为什么图灵奖能够作为人生的理想呢?人生的理想应该是一种境界,而不是一种成就。比起拿图灵奖,或许证明 \(P\neq NP\) 的那 \(10^6\) 美刀(获得了富足的境界)更吸引我。

作为计算机传统强校,我在来若松之前就读过了会津大一位教授 Viglietta 的几篇论文,对他非常的崇拜。因此我更加崇拜与系主任的成就,想必是某些我无法理解的学说,于是怀着好奇的心情,从各方小道消息才打探到他的名字,可惜现在太过于久远,只记得他姓谷口(Taniguchi),名字好像读作 Shiisa 还是什么。只记得把他的名字输入到了 google 搜索框里,原来他是东京都江东区青海町的一名政/府工作人员。

于是我在思考,为什么系主任是系主任,为什么 Viglietta 是 Viglietta。

或许有必要讲一讲会津地区的风景。这里冬天的雪景是极美的,盆地周边环绕的就是大大小小的滑雪场。向南坐上一个小时的火车可以到鬼怒川温泉,是有名的度假胜地,而这里其实已经算是东京都市人的娱乐范围了。向北去没有火车,但是坐上半个小时的汽车,穿过长长的跨越县境的隧道,可以到最上川平原和山形地区,我每每在梦里听见最上川的名字,都为这个气派的名字所折服。但是最美的风景一定要向西走,只见线和磐越西线都是有名的观景路线。

在这样美丽的风景里是让人沉醉的,可惜这里的樱花不如代代木的樱花开的烂漫,春天便少了一分色彩。

会津大本来不大,学生自然也不多,但是因为不多我们也建立了非常牢靠的关系。我们这个课题组一共五人,我,\(y\) 君,\(\gamma\) 君,\(\Upsilon\) 君 和 \(\mathcal Y\) 君。

先说说 \(y\) 君,\(y\) 君大约确实是一位极好的人,十分机灵活泼,可爱极了,在各种小事上也能看出他天真的一面。 \(y\) 君自然是聪明的,不必提他的思维能力,他对事物也有独到的看法。有时羡慕他对事物独到的看法,有时又对他过往的经历感到好奇,到底是什么样的事情能够塑造一个这样的他。

\(\gamma\) 君大约是和 \(y\) 君关系不错的,且写得一手好文章。 \(\gamma\) 君年纪不及我,但有时在属于他这个年纪的笑容中展现的是不属于他这个年纪的痛苦。

\(\Upsilon\) 君大约也潜藏着忧郁的内心,和 \(\mathcal Y\) 君以及一位叫做 Shirapikari 君的(拥有炫酷名字)的同学交往甚密。

\(\mathcal Y\) 君与前面三人的显著的不同的一点在于,他是一个自信的人,至少他在一些场合是一个自信的人。大约在 cts 里,自信并不是一件坏事,但是也并不能算是一件好事。或许有时候他过于自信了,或许有时候他发现自己的内心被窥探了,或许有的时候他和系主任聊天,或许有的时候他追求至上的地位,或许他不知道自己努力的意义在于什么,或许他希望得到的只是来自他人的肯定,或许他坚持的目的只是不被家长批判,或许他是一个矛盾的人,这样的矛盾塑造了一个矛盾的他。


在会津大的时间是短暂的,8 月底福岛开始排核废水,自然赶快被家长召回了故乡。虽然若松也是福岛县下属的市镇,但是需要横跨整个福岛县才能到核电站。说道核电站,他旁边的浪江町私认为名字是极美的,曾在课余时间去过几次,从代行巴士上可以看到曾经被称作核电站的地方。

离开的心情自然是复杂的,最后一次在阿贺川滨漫步,最后一次坐上在磐梯山间穿行的火车,最后一次路过猪苗代湖畔,最后一次在 Hayabusa/Komachi 上飞驰,最后一次坐上成田特慢。

会津若松是一个美丽的地方,但是我不会再回去。

正文

OI 生涯最后一次 CSP,痛失 AK,感觉挺遗憾。

upd: \(100+100+100+95\)

后记

会津大门前有两棵树,一棵是樱花树,另一棵也是樱花树。

最后一次见到系主任和 \(y,\gamma,\Upsilon,\mathcal Y\) 四君是在 CSP 之后。

系主任在食堂门口呆呆的望着什么。

\(y\) 君,\(\gamma\) 君和 \(\Upsilon\) 君依旧想死。

\(\mathcal Y\) 君也开始想死了。

在这之后过去了很多年,\(y\) 君和 \(\gamma\) 君曾成为了会津大扛把子的人物,他们的故事至今是坊间奇谈。

\(\Upsilon\) 君去向不知所踪,听说去了遥远的地方,\(\mathcal Y\) 君和她爱过的女孩在一个风雪交加的夜晚逃出了会津,上一次他向我们发来消息,他在种子岛东岸的一个小渔村里。

至少四君依然活的好好的,但是他们依然想死。

我又一次坐在往东北去的火车上,这一次沿着滦河北上,山水之间夹杂的是金黄的麦野。想起浪江在核辐射的滋养之下肆意生长的油菜花田也是如此,又想起我和四君一起沿 121 号国道往最上川去的事,那也是在一场梦里,我们在道の站偶然相遇,然后各自散开。

于是我不禁问,我是他们中的哪一个?

-完-

0%