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

問題 D - Squares 解法 解説: Editorial - HHKB Programming Contest 2020 上記解説手順で解いてみる #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) typedef long long ll; const int mod = 1000000007; // mintは省略 https://github.com/atcoder/ac-library int main() { int t; cin >> t; REP(i,t) {…</n;i++)></bits/stdc++.h>

問題 D - Patisserie ABC 解法 公式解説が詳しいのでそこに書いてある通り。 https://img.atcoder.jp/abc100/editorial.pdf $ x,y,z $ の3要素の正方向と負方向の組み合わせは $ 2 ^ 3 $ 通り。 それぞれの組み合わせで $ x,y,z $ の合計が大きいものから $ …

問題 D - Good Grid 解法 $ (i+j) \% 3 $ なので条件を満たすために使う色は3色のみ 事前に $ (i+j) \% 3 $ を3パターンに塗ったときのそれぞれのコストを計算しておく 全ての色の組み合わせについて調べる(全探索)。$O(N{^3})$ となるが $ C=30 $ の制約に…