AtCoder Daily Training 2026/02/04 20:00start MEDIUM 復習
1問目
各家についてすでに太郎が存在しているかを更新していって判定。ちゃんとAの要素を1ずつマイナスして0-indexedにしておくことなど大事。
2問目
「ちゃんとパパッと計算量解析ができますか?」って問題。i_1,i_2の選び方がO(H^2)で、j_1,j_2の選び方がO(W^2)から全探索してもO((HW)^2)で間に合う。
3問目
1~3日目にそれぞれ何点取ったかは別にどうでも良く合計しとく。あとは、4日目に自分だけ300点とって他は0点でK位以内に入れるか調べるだけ。
3日目にすでにK位以内に入っているなら自明にOK。そうじゃない場合、自分だけ300点取ったと考えて、(自分の3日までの点数) + 300 >= (3日目にK位だった人の点数)であればOK。
これはもちろん、3日目時点でK位以内だった人たちは4日目は0点だとしている。
4問目
まず、sum(A)<＝Mの時、全額補助しても良いということなのでinfiniteを出力。以下はそうでない場合。
二分探索の匂いがする。というのも、「0円であれば確実に制約を満たし、INF円であれば上記から確実に制約に収まらず、どこかにある1つの閾値を境にずっと制約を満たさなくなるようになる」(=単調性)ので、完全に二分探索である。
めぐる式二分探索で書くとバグらなくて良い。
int main() {
ll n, m; cin >> n >> m;
vll a(n); cin >> a;
if(accumulate(all(a), 0LL) <= m) {cout << "infinite" << endl; return 0;}
ll l = -1, r = LINF;
while(r - l > 1) {
ll mid = l + r >> 1;
ll sum = 0;
rep(i, n) sum += min(mid, a[i]);
if(sum <= m) l = mid;
else r = mid;
}
cout << l << endl;
}
5問目
全然解けなかった。
選択した範囲に人が少なくなる場合と、多くなる場合があって、二分探索無理だと思ったが、結局二分探索は「単調性のあるものについて、基準を与えてあげればそこの閾値となる場所が出てくる」ので、「距離について二分探索して、範囲内にk個以上入っているかで判定」ということをすれば良いだけ。
つまり、「指定した距離範囲に『ちょうどK個』入っていなければならず、K個未満でもK個より多くても条件を満たさないから、単調性がなく二分探索を使えない」と考えるのではなく、「『範囲内にk個以上入っているか」の判定で二分探索すれば、単調性があるから、ちょうどK個になる距離を求めることができ、結果的にK個未満ではないという条件も満たせる」みたいな感じで考えれば良いということ。
「制約に単調性がない」と諦めるのではなく、「単調性があるような条件を自分で考えて(用意して)二分探索をできるようにしてあげる」と考えられるかどうかが重要かも。
こういう、「いかにも二分探索してね」みたいな問題に一見見えづらい問題も、「自分で単調性を満たすような条件を探して、二分探索を適用してあげる」みたいなことをできるようになる必要があるのかもしれない。
次に境界について。
while(r - l > 1) {
ll mid = l + r >> 1;
ll p = b - mid, q = b + mid;
auto v = upper_bound(all(a), p);
auto w = lower_bound(all(a), q);
if(w - v >= k) r = mid;
else l = mid;
}
cout << l << endl;
最初適当に書いてこれで通したが、これはおかしい。
なぜなら、今条件は『[p, q]の区間にAの要素がK個以上ある』ことなのに、これだと、[p, q]ではなく(p, q)になっている。あと、今は「>=k」が判定内容なので、OKがr、NGがlにならないとおかしいから、lを出力しているのもおかしい。
while(r - l > 1) {
ll mid = l + r >> 1;
ll p = b - mid, q = b + mid;
auto v = lower_bound(all(a), p);
auto w = upper_bound(all(a), q);
if(w - v >= k) r = mid;
else l = mid;
}
cout << r << endl;
これが正しい。閉区間や開区間、(l, r)のどちらがOKでどちらがNGかなど、ちゃんと考えながら実装しないといけないと感じた。
(最初のコードでACになっているのは、開区間,閉区間のズレとl,rのズレがうまく噛み合ったからだと思う)
二分探索をするとき、いつも変数名としてl, rを使っているが、ok, ngを使った方が良いかもなと感じた。
Discussion