ABC119 C - Synthetic Kadomatsu

AtCoder DFS Python3

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
INF = float('inf')


def dfs(N, current, A, a, B, b, C, c, L):
    if N == current:
        if a == 0 or b == 0 or c == 0:
            # 竹を１つも使用していない場合
            return INF
        return abs(A-a) + abs(B-b) + abs(C-c)

    # 竹を使用しない場合
    w = dfs(N, current+1, A, a, B, b, C, c, L)
    # 竹を各A, B, Cのどれかに使用する場合
    # ただし、合成魔法を使用しない場合(加算する竹a,b,cが0のとき)には+10しない
    x = dfs(N, current+1, A, a+L[current], B, b, C, c, L) + 10*(a != 0)
    y = dfs(N, current+1, A, a, B, b+L[current], C, c, L) + 10*(b != 0)
    z = dfs(N, current+1, A, a, B, b, C, c+L[current], L) + 10*(c != 0)
    return min(w, x, y, z)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, A, B, C = il()
    L = [ii() for _ in range(N)]

    print(dfs(N, 0, A, 0, B, 0, C, 0, L))


if __name__ == '__main__':
    main()

考え方

全探索で回答を求める問題です。
各竹に対して、取りうる選択を全て試して、最小のMPを求めます。

  • 回答概要
    • 足し算と引き算は計算の順番が変化しても答えが一意になるため、使用する竹の順番は考慮しない
    • ケース数が少ないため、発生しうるケースを全探索する

まず、竹の使用順と各魔法について考えます。
延長魔法で必要なMPは目的の竹の長さ - 今の竹の長さで求めることが出来ます。
また、短縮魔法についても同様です。
そのため、延長魔法と短縮魔法は目的の竹の長さと今の竹の長さの差の絶対値を取ればよいことがわかります。

各魔法を使用した際の消費MPは全て加算によって計算されます。
したがって、魔法を使用する順を変えても、最終的に必要なMPは変化しません。
（魔法を使用する順番を考慮する必要はない）

次に、各N(3 <= N <= 8)本の竹が取りうる選択について考えます。
竹を使用するときの選択肢は、
「使用しない」「竹Aを作るために使用する」
「竹Bを作るために使用する」「竹Cを作るために使用する」
の4通りです。
したがって、全てのケースを試しても4 ^ 8 = 65536通りなので全探索で回答を求めます。