問題 D - Decayed Bridges 解法 ぱっと見でUnionFindだろうなと思ったが、少々工夫が必要だった。 橋の削除操作は難しいため、逆順から橋を追加していく操作を考える 橋が一つもない状態の不便さは $ {}_n C_2 $ で求まる 橋を追加後の不便さは、次で求まる …

問題 D - AtCoder Express 2 解法 列車の区間L-Rを二次元座標として考える。 Q個のクエリを求める必要があるが、都度計算すると間に合わない。 二次元累積和を使って前計算しておくことで、Q個のクエリに対して高速に答えを出す。 #include <bits/stdc++.h> using namespace</bits/stdc++.h>…

問題 E - Queen on Grid 解法 DP + 累積和。 dp配列は、 dp[i][j] = {i,j}地点に到達できる場合の数 で考える。 するとdp[i][j] は以下のように3方向のdpの累積を足すと求められる。 dp[i][j] = dp[i][j-1] + dp[i][j-2] ... + dp[i][0] + dp[i-1][j] + dp[i…

問題 D - We Love ABC 解法 ? があると複雑なため、まずは ? 抜きで考えてみる。 素朴に3重ループでA->B->Cとなるパターンを総当りしてみる。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) using ll = long long; int main() { string s; cin >> s; int n = s.size(); ll ans = 0; REP(i,n) {</n;i++)></bits/stdc++.h>…

問題 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 $ の制約に…

問題 D - Xor Sum 2 解法 全探索すると $O(N{^2})$となり間に合わないため、計算量を減らす工夫が必要になる。 この問題は単調増加する区間の数え上げなので、尺取り法の要領で解くことができる。 #include <bits/stdc++.h> using namespace std; using ll = long long; #de</bits/stdc++.h>…

問題 D - Grid Components 解法 $ h, w $ は 100以下という条件なので、$ h = 100, w = 100 $ で固定して考える $ 1 \leq A \leq 500, 1 \leq B \leq 500 $ の制約であれば、100x100 の 半分 50x50 の領域に500個の連結成分を作ることは可能 上記を前提とし…

問題 D - People on a Line 解法 以下の有向グラフを作り、DFSで頂点間の距離に矛盾が生じていないかを調べる。 $ L_i $ から $ R_i $ まで距離 $ D_i $ $ R_i $ から $ L_i $ まで距離 $ -D_i $ ただし、M個の入力から得られるグラフは連結していない場合が…

リキッドレイアウトで並べられたアイテムの特定行に差し込み要素を入れたい。 イメージ: 赤枠がアイテム、青枠が差込要素 リキッドレイアウトでは横幅によって1行に並ぶアイテム数が可変となる。 表示するウィンドウの横幅によっては1行3個の場合もあれば、1…

問題 D - Leaping Tak 解法 素直にDPで解けそうだが、愚直にnに対して全ての移動を試すと $ O(N{^2}) $ となり $ 2≤N≤2×10{^5} $ の制約下でTLEしてしまう。 // このコードはTLEする #include <bits/stdc++.h> using namespace std; #define COUT(x) cout<<(x)<<"\n" #defin</bits/stdc++.h>…

問題 C - Ubiquity 公式解説にある通り、包除原理を理解していれば数行で解ける問題。 包除原理にたどり着けず納得が行かなかったので公式解説動画で言及されていたDP解法で解いてみた。 DP解法 DPは [N][0を含んでいるかどうか][9を含んでいるかどうか] で…