巡回セールスマン

AtCoder abc274 参加メモ

キーエンスプログラミングコンテスト2022(AtCoder Beginner Contest 274) - AtCoder B - Line Sensor 二重ループでカウント #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #define endl '\n' int main() { int h,w; cin >> h ></bits/stdc++.h>…

AtCoder ABC 180 E - Traveling Salesman among Aerial Cities

問題 E - Traveling Salesman among Aerial Cities 解法 巡回セールスマン問題。 ナイーブな全探索では $O(N{!})$ かかるため、 $ n=17 $ では時間切れになる。 そこでbitDPと呼ばれる手法を使う。 bitDPでは計算量が $ O(N{^2}2{^n})$ となるため今回の制約…