問題 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を含んでいるかどうか] で…