Quiz https://atcoder.jp/contests/tkppc6-1/tasks/tkppc6_1_d AC https://atcoder.jp/contests/tkppc6-1/submissions/25307869 解説 区間を累積和で書き直す 累積和を各項Biとした配列Bをソートして、i, j (i<j) の全組み合わせについてBj - Biの和を取れば答え 以下の画像はN=4の場合 int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N; cin>>N; VI A(N); rep(i, N…</j)>

Quiz PAST7 J-終わりなき旅 AC https://atcoder.jp/contests/past202107-open/submissions/24415719 解法 グラフをトポロジカルソートする DAGじゃない時は失敗する DAGじゃない場合は閉路がある 計算量 トポロジカルソートの分の O(N+M)

上記画像は https://atcoder.jp/contests/abc174/tasks/abc174_f の解説放送から 2Dにプロットしてそれぞれ処理していくのだが、処理順をx軸またはy軸の順に滑らせる BIT, segtreeがお供？ 問題集 Range Set Query https://atcoder.jp/contests/abc174/tasks…

https://atcoder.jp/contests/abc186/tasks/abc186_e editorialを見ると、合同式の方程式を解く方法が知りたくなる。例えば ax ≡ b (mod m) これを満たすxを求めたいが、xは存在することもあるし、存在しないこともある gcd(a, m)の値が重要になる 高校の数A…

Quiz https://codeforces.com/contest/1557/problem/C AC https://codeforces.com/contest/1557/submission/125425375 解説 ビットごとに考える nが奇数の時 等号しか作れない nが偶数の時 大なりになる列iを全探索 code void solve(){ ll n,k;cin>>n>>k; if…

Quiz E-Magical Ornament https://atcoder.jp/contests/abc190/tasks/abc190_e AC https://atcoder.jp/contests/abc190/submissions/19830501 解法 K<=17と小さいので訪れる順番を全て試すbitDPをしたい 石の数が105と多いが、注目すべき石は17個に抑えられ…

B-123 Triangle https://atcoder.jp/contests/agc043/tasks/agc043_b AC https://atcoder.jp/contests/agc043/submissions/24728675 その他 自分で作ったのはTLEしたりギリギリACしたり、意外とLucasの定理は時間がかかるようだった algo-logicさんのを借り…