2077_海底捞针.md

2077 海底捞针

本次 hackergame 正好撞上我开题答辩，所以没空参加。只是应 zzh 邀请做了这道据他说是 AI 的题。其实我真不会啥经典的机器学习方法，什么 Lasso 算法，喵喵喵？我只会深度学习一把梭。

这道题，题目中说“任意取了 31～4999 张图片并加权平均”，然后我也没仔细看示例代码，以为真的每张图片是加权的，我就这么做的……

我的想法很暴力，直接考虑用 PyTorch 里的 Adam 优化器来优化权重 $w$ 使 $ L_{\infty}(X_m - \Sigma w_i X_i)$ 最小（就是以当前权重得到的平均图像和 averaged.png 像素值之差的最大值）。

整理过的代码如下：

import numpy as np
import math
import torchvision
from PIL import Image
import torch

trainset = torchvision.datasets.CIFAR10(root='./data', train=True, download=True)
images = trainset.train_data  # 50000, 32, 32, 3
images = torch.from_numpy(images / 255.0).float().cuda()

avg = np.array(Image.open("averaged.png"))
avg = torch.from_numpy(avg / 255.0).float().cuda()

w = torch.zeros(images.shape[0], 1, 1, 1, device="cuda")
w.requires_grad = True

optimizer = torch.optim.Adam([w], lr=0.1)
scheduler = torch.optim.lr_scheduler.ReduceLROnPlateau(optimizer, patience=100)

loss = math.inf

while loss > 1.0 / 255.0:
    # 2300 epoches, ~1min with GTX1060
    optimizer.zero_grad()
    cur = (w.softmax(0) * images).sum(0)
    loss = (cur - avg).abs().max()

    loss.backward()
    optimizer.step()

    scheduler.step(loss)

with torch.no_grad():
    w = w.softmax(0).squeeze()
    argsort = w.argsort(descending=True)
    for idx in argsort[:100]:
        print(idx.item(), w[idx].item(), sep="\t")

在我的 GTX 1060 上，只需一分钟就能优化到小于 1 的像素差了。由于量化的影响，此时得到的加权平均图像也不是严格等于 averaged.png 的。

此时，可以观察一下输出的权重，会发现只有 33 张图的 $w_i$ 是比较大的（0.0198~0.0284），剩下的图权重都非常小（低于 0.0014）。这 33 张图的编号是：

7764 159 11875 27803 26499 11150 42358 2026 43145 22274 14712 3878 45626 17377 31948 32186 48116 26202 37445 1107 17130 16883 30136 37885 34493 11974 3721 47921 36462 24496 3857 39326 4303

然后我觉得可能就是没加权吧，就直接取这 33 张图做了个平均，结果还真是和 averaged.png 一毛一样！

所以就这么解出来了。