競プロ典型90問: 032 - AtCoder Ekiden（★3）

https://gyazo.com/a36bb6ed920265bdaa63403bd8ad67ea

【32 日目】

昨日の解説と今日の典型問題です。制約が N ≦ 10 と非常に小さいです！

なお、AtCoder ジャッジには 15 時頃に追加される予定です。（31 日目と同様、入力形式・入出力例は GitHub を参照のこと） #競プロ典型90問 pic.twitter.com/gai3NDpMSg

— E869120@公開アカウント (@e869120) May 4, 2021

hr.icon

https://gyazo.com/a6e5e9509eee85c82d25ce9fc3b0f971

【33 日目】

昨日の解説と今日の典型問題です。難易度は ★2 で、初級者向けの問題となっています。なお、AtCoder ジャッジには 15 時頃に追加される予定です。（32 日目と同様、入力形式・入出力例は GitHub を参照のこと） #競プロ典型90問 pic.twitter.com/FhnFTuKsXt

— E869120@公開アカウント (@e869120) May 5, 2021

全探索

$ \mathcal{O}(N! \times N)

bit DPによる別解

code:py

inf = 10**9

n = int(input())

a = list(map(int, input().split())) for _ in range(n)

m = int(input())

ng = [False*n for _ in range(n)]

for _ in range(m):

x, y = map(int, input().split())

ngx-1y-1 = ngy-1x-1 = True

# dplastfinished: 走り終わった人のbit表現がfinished、最後に走った人がlastのとき、かかる時間の最小値

# lastのほうが値域が小さいので先にもってきている

dp = [inf*(1 << n) for _ in range(n)]

# 初期化(各人が1区を走ったとき)

for last in range(n):

dplast1 << last = alast0

# dp更新用関数

def chmin(last, finished, time):

if time < dplastfinished:

dplastfinished = time

for finished in range(1 << n):

interval = bin(finished).count("1") # 次の走者が何区か

for last in range(n):

dp_prev = dplastfinished

if dp_prev == inf:

# lastがfinishedに含まれていない場合？

continue

for current in range(n):

if finished >> current & 1:

# すでに走っている

continue

if nglastcurrent:

# NGペア

continue

chmin(current, finished | 1 << current, dp_prev + acurrentinterval)

ans = min(dpx-1 for x in range(n))

if ans == inf:

ans = -1

print(ans)

from Submission #22323491 - 競プロ典型 90 問

#競プロ典型90問