ABC119-C Synthetic Kadomatsu

atcoder.jp

気楽に書くことに決めたので連続更新、競技プログラミング以外をやるべき状況だが、、、 今回は旧ABCのC問題。Cの中では最難関級っぽいのでどうせ実装系だろうと思いコーディングの練習にしようと思って解いた。 長さA,B,Cの竹を3~8本の竹を組み合わせて作りたい。操作は1本の竹の長さを+1or-1できる(コスト1)。または２つの竹をくっつける(コスト10)。ここで最小操作コストを計算。 それぞれの竹をA,B,Cのどれに使うか、またはどれにも使わないか固定する。 そうするとそれぞれのグループ内での最小コストのための操作はグループ内の竹を全て結合してそれぞれの長さになるまで+-1でいい。 コードは以下

n,a,b,c=[int(i) for i in input().split()]
ts = [a,b,c]
ls = []
for _ in range(n):
    ls.append(int(input()))
r = 10**18
for i in range(4**n):
    xs = [[] for _ in range(4)]
    for j in range(n):
        k, i = i%4, i//4
        xs[k].append(ls[j])
    ir = 0
    for l in range(3):
        if len(xs[l]) == 0:
            ir = 10 ** 18
            break
        ir += 10*(len(xs[l])-1) + abs(ts[l]-sum(xs[l]))
    r = min(r, ir)
print(r)

多分ポイントはそれぞれの竹をA,B,Cのどれに使うか、または使わないかを固定するときに4ⁿの全探索が必要、1~4**nをそれぞれ4進数すればいい。

for i in range(4**n):
    ls = []
    for j in range(n):
        k, i = i%4, i//4
        ls.append(k)

割とすぐ解けた。ちゃんと測ってないけど15分くらい？上の式を脳死で書ければもっと早くなったと思う。