AtCoder - 「ZONeエナジープログラミングコンテスト」 Cが想定解じゃなさそうだったので説明する

問題: https://atcoder.jp/contests/zone2021/tasks/zone2021_c

計算量としては公式解説の二分探索したほうが良い。

Cの問題を見た際、二分探索で $k$ 以上で作れるかという問題に帰着できるのでは?という考えは過ったものの、k以上できるかという判定に必要な計算量を勘違いしていたために別の手段を考えていた。

洞察

A,B,C,D,Eをグループ0,グループ1、グループ2に分割する事を考える。このグループの数は高々 $3^5 = 243$ しか存在しない。各グループに分類されたスコアでソートをすることを考える。これは、例えば $(A,C),(B,E),(D)$ というグループ分けになっているならば、$G0_i = min(A_i,C_i)$ , $G1_i = min(B_i,E_i)$ , $G2_i = min(D_i) = D_i$ として計算した各 $G0,G1,G2$でソートした配列を作ることになる。
このソートにかかるのは高々 $O(NlogN)$となる。

これで、各グループ分けで考えられる最大の要素を求めてやれば $O(3^5Nlog(N))$となり、十分に求められるのではないかと考えた。

他に考えたエッジケース

ある組み合わせ(A,B)に対して選んだヒーローPが別の組み合わせ(C)に対しても選ばれるケース

グループ (A,B)に対してソートしたものとグループCに対してソートしたものがあった場合に(A,B)に対して選択したPを入れた際に、Cも見ていたらPが強かったとなった時どうしたらよいか。

しかし、この場合で得られるスコアより、(A,B,C)の組み合わせを持つグループ分けの中のどれかのほうがスコアが少なくとも同等か高くなるはずである。

ここで、人数が少なかった場合に2名しか選ばないという事を避けるためにそういう場合はソートして2位の人を入れればよい。(1,2が既に入っていた場合は3位を入れる)

回答例

def calcScore(p1,p2,p3):
    a1,b1,c1,d1,e1 = p1
    a2,b2,c2,d2,e2 = p2
    a3,b3,c3,d3,e3 = p3
    return min(max(a1,a2,a3),max(b1,b2,b3),max(c1,c2,c3),max(d1,d2,d3),max(e1,e2,e3))

def solve(N: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]", E: "List[int]"):
    P = [(A[i],B[i],C[i],D[i],E[i]) for i in range(N)]
    G0 = [None] * N
    G1 = [None] * N
    G2 = [None] * N
    maxr = -1
    for gi in range(3**5):
    # 3進数的に考えて適当なグループ分けを考える
        gg0 = gi % 3
        gi //= 3
        gg1 = gi %3
        gi //= 3
        gg2 = gi %3
        gi //=3
        gg3 = gi %3
        gi //=3
        gg4= gi %3
    # 適当な枝狩り。(1,1,1,2,2)と(0,0,0,1,1)は一緒で無駄なので、少なくともAは0グループ目に入ってて、Bは2グループ目にないとしている。PyPyだとこれがないとACにならなかった
        if gg0 != 0 or gg1 == 2:
            continue
        g = (gg0,gg1,gg2,gg3,gg4)
        for i in range(len(P)):
            p = P[i]
            g0 = 10**9 + 1
            g1 = 10**9 + 1
            g2 = 10**9 + 1
            for j in range(5):
                if g[j] == 0:
                    g0 = min(g0,p[j])
                elif g[j] == 1:
                    g1 = min(g1,p[j])
                else:
                    g2 = min(g2,p[j])
            G0[i] = (g0,i,p)
            G1[i] = (g1,i,p)
            G2[i] = (g2,i,p)
        G0.sort(reverse=True)
        G1.sort(reverse=True)
        G2.sort(reverse=True)
        heros = [G0[0]]
        used = set()
        used.add(G0[0][1])
        for k in range(len(G1)):
            if G1[k][1] not in used:
                used.add(G1[k][1])
                heros.append(G1[k])
                break
        for k in range(len(G2)):
            if G2[k][1] not in used:
                used.add(G2[k][1])
                heros.append(G2[k])
                break
        s = calcScore(heros[0][2],heros[1][2],heros[2][2])
        maxr = max(s,maxr)
    print(maxr)