尺取り法

AtCoder abc246 参加メモ

AtCoder Beginner Contest 246 - AtCoder の参加メモ C - Coupon greedy。 クーポンでX円値引きできる商品はクーポンを使えるだけ使って良い。 X円未満しか値引きできない商品だけ残ったときは、降順にソートして値段が高いものから順番にクーポンを使ってい…

atcoder ABC 098 D - Xor Sum 2

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