https://www.acmicpc.net/problem/15686

🥚質問する

🥚入力/出力

🍳コード#コード#

1番コード(時間:880ミリ秒)

import itertools
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(n)]


def get_chicken_dist(r1, c1, r2, c2):
    # 치킨 거리 = 집과 가장 가까운 치킨집 사이의 거리 = |r1-r2| + |c1-c2|
    return abs(r1-r2) + abs(c1-c2)


# 집과 치킨집의 좌표를 추출
home = []
chicken = []
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            home.append((i, j))
            continue
        if city[i][j] == 2:
            chicken.append((i, j))

# m개의 치킨집 조합을 구성
combis = list(itertools.combinations(chicken, m))

ans = 1000000

# 치킨집을 combi 조합으로 남겨놓았을 때, 도시 전체의 치킨거리
for combi in combis:
    # 도시의 치킨 거리 = 모든 집의 치킨 거리의 합
    city_dist = 0
    # 각 집에서의 치킨거리
    for target_home in home:
        tmp_dist = 1000000
        for j in range(m):
            # 가장 가까운 치킨집까지의 거리
            tmp_dist = min(tmp_dist, get_chicken_dist(
                target_home[0], target_home[1], combi[j][0], combi[j][1]))
        # city_dist에 target_home의 치킨거리 더함
        city_dist += tmp_dist

    ans = min(ans, city_dist)

print(ans)

2番コード(時間:536ミリ秒)

import itertools
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(n)]

# 치킨 거리 = 집과 가장 가까운 치킨집 사이의 거리 = |r1-r2| + |c1-c2|
def get_chicken_dist(r1, c1, r2, c2):
    return abs(r1-r2) + abs(c1-c2)


# 치킨집과 집의 좌표를 추출
home = []
chicken = []
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            home.append((i, j))
            continue
        if city[i][j] == 2:
            chicken.append((i, j))

# 집, 치킨집의 개수
n_home = len(home)
n_chicken = len(chicken)

# chicken_dist[i][y] = 집 i에서 치킨집 y로의 치킨 거리
chicken_dist = [[0]*n_chicken for _ in range(n_home)]
for i in range(n_home):
    for j in range(n_chicken):
        chicken_dist[i][j] = get_chicken_dist(
            home[i][0], home[i][1], chicken[j][0], chicken[j][1])


# 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때
# 도시의 치킨 거리의 최솟값을 출력
if n_chicken == m:
    print(sum(map(min, chicken_dist)))
elif n_chicken > m:
    # 폐업시킬 치킨집 n_chicken - m개의 조합을 구함
    combis = list(itertools.combinations((
        [x for x in range(n_chicken)]), n_chicken-m))

    # 각 조합에 맞추어 폐업시켜보면서 min_dist 갱신
    min_dist = 1000000
    for combi in combis:
        # 조합에 따라 폐업시킨 후의 chicken_dist
        new_chicken_dist = []
        for i in range(n_home):
            tmp_row = []
            for j in range(n_chicken):
                # 조합에 들어있는 치킨집은 폐업 -> new_chicken_dist에 포함시키지 않는다
                if j in combi:
                    continue
                tmp_row.append(chicken_dist[i][j])
            new_chicken_dist.append(tmp_row)
        # min_dist 갱신해
        min_dist = min(min_dist, sum(map(min, new_chicken_dist)))
    # 출력
    print(min_dist)

🧂アイデア

実装する

軒のフライドチキン店のm個の組み合わせをそれぞれテストし、町全体のフライドチキン距離の最小値

を求めた.

Pythonのitertoolsを使って維持するm個のフライドチキン店のセット

を見つけました

1番コード

mのチキン屋セットをゲットした後、各セット都市のチキンストリートを探します.その結果、最も少ない都市フライドチキン距離が出力されます.

minで値

の更新を続行

2番コード

chicken dist[i][j]:家iからフライドチキン屋jまでのフライドチキン距離をリストに保存

itertoolsを利用して休業するチキン屋のセットを見つけた後(維持するチキン屋のセットを見つけても同じ)

chick distで休業していたチキン屋の柱を除いたnew chikcine distを作ります.

new chicken distの各行の最小値は、組み合わせで得られる都市全体のフライドチキン距離の最小値である.すべての組合せについてこの操作を繰り返し、最終的に最小の都市フライドチキン距離を出力します.