競技プログラミング用 知識集積所
ABC409B - Citation
最終更新：
sport_programming
-
view
問題
必要知識
A問題レベルのものは省略
考え方
条件を満たす最大値を答えるものなので、大きい方から順に全探索する。
答えの可能性があるのが0以上n以下の整数なので、nから順に下降方向へ1つずつ条件に合うか調べ、合うものを見つけた時点でループを抜ければよい。
答えの可能性があるのが0以上n以下の整数なので、nから順に下降方向へ1つずつ条件に合うか調べ、合うものを見つけた時点でループを抜ければよい。
解答例
注意点
別解
vectorを使って全部の個数を一気にカウントする
毎回個数チェックにループを回すのは計算時間がかかりそうなので、そこを高速化することができる。
Aの中身が10^9まであるので普通にやると計算量がとんでもないことになるが、nを超える値は全てn+1に書き換えてしまって問題ないことを使えば対応できる。
Aの中身が10^9まであるので普通にやると計算量がとんでもないことになるが、nを超える値は全てn+1に書き換えてしまって問題ないことを使えば対応できる。
sortして答える
実はaの順番は無関係であると考えると、aが小さい順か大きい順に並んでいれば個数が数えやすいと判断できる。
毎回二分探索（未作成）するか、上手に前から順に判断していくか、どちらでも。
後者の場合、番兵法（未作成）の考えで最後に-1を足しておくとコードを書きやすい。
毎回二分探索（未作成）するか、上手に前から順に判断していくか、どちらでも。
後者の場合、番兵法（未作成）の考えで最後に-1を足しておくとコードを書きやすい。
もっとも、これはB問題なのでこんなに苦労して高速化する意味は何もない。
もしこれがC問題だった場合、O(n*logn)解法なのでN=10^6くらいでも対応できるという意味で知っておきたい解法ではある。
解答例
もしこれがC問題だった場合、O(n*logn)解法なのでN=10^6くらいでも対応できるという意味で知っておきたい解法ではある。
解答例
