ABの二完。Cを考えているうちに寝てしまった。Cは一応自力で解けたけど、寝なかったら解き終っていたかというと微妙なところ。
No.3050 Prefix Removal
自力AC。
もし、Aの要素全てを使い切るとすると、満足度の変化は、
・最初の操作で全てのiに対して+A[i]
・選ぶpより大きい全てのiに対して+A[i]
のようになる。
これを最大化するためには、Aの後ろからの累積和を取って、大きい方から選んでいけば良い。ただし、最初に0を必ず選ばなくてはいけないことに注意。
ここまで分かったら、後はAのうち何個使うか？ という部分。
これがなかなか思いつかなかったのだが、heapqを使えば全探索できることに気付いた。やや思いつきにくいし面倒ではあるけれど、何度もしたことがある方法だった。
上手くやれば全探索できるのでは？ と考えてみなくてはいけないねぇ。
No.3051 Make All Divisible
テストケースは見たけど、一応自分で考えてAC。
まず、
・sum(A)がkで割り切れる
・max(A)<=sum(A)/k
のとき、この操作で全てを0にすることが可能（ということは考えているうちに思い出した）。
なので、各A_iをA_i%kに置き換えた数列でこの条件を満たせば一番良い。
そして、満たさない時は、現在のAの中で最も小さい数で、かつ、+kしても最初のAの値以下であるようなものに+kして、条件を満たすかを見ていく。
計算量は分からなかったが、この方法でACできた。
0 件のコメント:
コメントを投稿