はじめに

今回は年始の駅伝を先回りして、競プロ典型90問から、「032 - AtCoder Ekiden」を解いてみたいと思います。
正直正月の駅伝見たことないけれど…。

はじめに
競プロ典型90問
032 - AtCoder Ekiden
おわりに

競プロ典型90問

atcoder.jp

032 - AtCoder Ekiden

問題の目的

かかる時間の最小値を求める。

問題の制約

嫌いな相手同士でたすきのやり取りが出来ない。

プログラムの方針

この問題は、 ①嫌いな相手を記録する ②制約の上で走る順番の全探索を行って最小値を探す
に分かれます。

①については、グラフ理論の隣接行列という考え方を使えば簡単に実装できます。

ここでは例を挙げて説明します。１さんは２さんと不仲で、２さんは３さんと不仲であると考えます。それをグラフで表したものが上の図となります。
この問題では不仲であればお互いにたすきをやり取りすることが出来ないので、無向グラフと呼びます。反対に向きが意味を持つグラフを有向グラフと呼びます。

プログラムでは、グラフを扱うことはできません。そこで図のようなリストを定義します。グラフと同じ意味を表していて、１さんと２さん、２さんと３さんとの間はFalseにしています。

次は②について考えていきます。今回は対象とするNが10以下と、比較的少ないです。なので10人が走る順番のすべての可能性を考えていきましょう。それは階乗を計算することで得られることが出来、itertoolsモジュールで計算して1通りずつ取得することが出来ます。

それぞれの組み合わせについて、全員ー１人分、後ろの人との関係性を、隣接行列を用いてチェックします。全員分の関係性をチェックして、不仲でなければその組み合わせは解答の候補となります。あとは全探索で最小のかかる時間を計算するだけです。以下がコードになります。

import itertools

n = int(input())
time_list = []
player_list = []

for i in range(n):
    time_list.append(list(map(int, input().split(" "))))
    player_list.append(i)

m = int(input())
adjacency_matrix = [[True for i in range(n)] for j in range(n)]

for i in range(m):
    x, y = map(int, input().split(" "))
    adjacency_matrix[x-1][y-1] = False
    adjacency_matrix[y-1][x-1] = False


min_time = 100000000
for v in itertools.permutations(player_list):
    time_sum = 0
    flag = True
    kukan = 0
    for w in range(len(v)-1):
        if adjacency_matrix[v[w]][v[w+1]] == True:
            time_sum += time_list[v[w]][kukan]
            kukan += 1
        else:
            flag = False

    time_sum += time_list[v[-1]][kukan]

    if time_sum < min_time and flag == True:
        min_time = time_sum

if min_time == 100000000:
    print("-1")
else:
    print(min_time)