题解 | #Spring Outing# 自底而上求解博弈

这个博弈题很类似于“海盗分金”问题，从前往后考虑是行不通的，应该自底而上求解每轮的结果。如果我们从第1轮入手，并不知道，后面将会出现什么样的结果，从而无法确定每个voter的策略。

但是，我们先假设投票能够进入最后一轮（cantidate K）。如果这轮赞成不过半，那么最终投票结果一定为0。所以在这轮中，voters的策略是可以轻松得出的，即：

认为 K 好于0的 voters 会投赞成票，其他人会投反对票。

据此，我们可以得出进入最后一轮的情况下，最终的投票结果是K还是0。

有了第最后一轮的结果，我们就可以继续往前推。在倒数第二轮中，认为最后一轮结果（0或K）好于 K-1 的 voters ，会投赞成票。再据此计算出第K-1轮的结果。以此类推，算出第1轮的投票结果即为最终答案。

我们需要频繁比较两个不同的candidate在某一个voter中的位置先后。为了加快效率，需要将每个candidate在每个voter的名次记录下来，避免对preference的频繁遍历。

def solve():
    n, k = [int(x) for x in input().split()]
    rank = [[0] * (k+1) for _ in range(n)]
    for i in range(n):
        preference = [int(x) for x in input().split()]
        for j in range(k + 1):   # 存每个candidate在每个voter的名次
            rank[i][preference[j]] = j
    ans = 0        # 遍历到i时，ans代表i+1轮的结果
    for i in range(k, 0, -1):   # 从第k轮开始，直到第1轮
        total = 0
        for j in range(n):
            total += rank[j][i] < rank[j][ans]  # 第j个voter认为i好于ans
        if (total << 1) > n:
            ans = i
    print(ans if ans else "otaku")
while 1:
    try:
        solve()
    except EOFError:
        break