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できた。
No.3052 Increasing Sliding Window Minimum
解説AC。
二乗DPになりそうなのは分かる。
DP[i][j]を、左からindex iまで埋め、使っていない数字の個数がj個のときの個数としてできそう、と思いかなり長いこと取り込んだがWAが取れず解説を見た。
すると、小さい数字から埋めて行くのが正解だった。
考え方は似ていたが、それだと、次の数字がどこのindexにまで入れていい、ということが分かるため、最初から分かっている数字を扱いやすい。
DP[i]をindexいまで置くことが可能なときの個数、と定義してやったが、この定義の仕方が悪く、n=2のときに例外処理をしなくてはいけない実装になってしまったが、無事AC。
DP[i]を、今までの数字で一番右に置いたindexがiのときの個数、とすべきだったか。
0 件のコメント:
コメントを投稿