一つでもpath上に黒がある個数を、総数ーpath上がすべて白く塗る個数と置き換えて包除原理を使う。 m 個の path の中から i 個を選ぶ方法は itertools.combinations を使い、1つの path が通る辺の集合を辺１つずつに番号を座圧の要領でつけていき、2進数表…

女子の選びだけ itertool で nCp 通り全列挙して男子の選び方を貪欲に選んでいく。 collection.Counter で most_common(q) とかして選んでいたら TLE したので普通にリストに入れていって上から q 番目まで取ったらいけた。 import sys input = sys.stdin.re…

今回の反省と学び 19C10 ≒ 46000 くらいの全探索が通ること。（総数が19C10 なのは分かっていた） 重複組み合わせの itertools が用意されていること。 itertools 使うときは順列の要素がデフォルト時は 0 から始まるので注意 次は5完する。 import sys inpu…

B - Buildings are Colorful! 制約が小さいのでビルの選び方を n-1Ck-1 通り全探索して間に合う 選んでないビルもビルの最大値に関わることがあることに注意 n,k = [int(i) for i in input().split()] a = [int(i) for i in input().split()] if k == 1: pri…

ワーシャルフロイド法で解く問題 街の通り方は順列で全探索した 計算量は最大(200**3 + 8!) くらいで pypy3 で 330ms def warshall_floyd(d): #d[i][j]: iからjへの最短距離 for k in range(n): for i in range(n): for j in range(n): d[i][j] = min(d[i][j…

N = 8 なら順列を小さい順にすべて列挙して p, q と一致するものがあるか調べても余裕で間に合う (８！ = 40320) list の == は中身の順番まで完全に一致していると True を返すおまけ set の == は順番は関係なく中身の種類さえ合っていれば True を返す [1…