じゅぴろの日記(⋈◍＞◡＜◍)。✧♡

AtCoder Regular Contest 105　C - Camels and Bridge

問題リンク

解説

$pre _ S := 集合Sが渡れない最長の距離の橋$

としましょう。

これは $O(2^ n (n + M))$ で前計算できます。

後は全探索です。

グループ分けをしたときに、前のグループとのorで伸ばさないといけない距離が前計算からわかります。

計算量は全体で

$O ( 2 ^ n (n+M) + n!2 ^ {n-1} n ^ 2)$ です

提出コード