AtCoder ABC301
またも3完。緑に上がった。
今回も簡単だった。Bluetoothキーボードの不調がなければ3問10分は余裕で切っていたであろう。問題の難易度に差がありすぎでは。
N = K = D = 100
なので三次元探索、DPなのは予想がついていたが、すぐには思いつかず、
あと一歩のE問題に時間を取られて、解けず。
本番後に30分程考えて、とりあえず二次元のDPを実装するもAC10、TLE19。
・N, Dのループ
・vector<pair<int, long long>>で手数と最大値を保持
結局、解説が三次元のDPなのを確認し、DPを考えてAC。
到達できないところ
-1で初期化しておいて、-1であれば使わない
A_iの総和より多きい-10^9*109で初期化しておいて、max()の作用で落としていく
のどちらでもACできる。
負の大きい数で初期化する方法は計算中には条件分岐しなくて便利だが、
最後はできない場合-1を表示しなければならないので、負の数なら-1を表示するという条件分岐が必要。
M個の数のうち、小さいK個を入れておくs_smallと、大きいM-K個を入れておくs_bigを用意し、
古いA_iをどちらかから消去し、新しいA_M+iをどちらかにつっこんでいく。セット間で移動も起きる。
・値に重複があるのでsetではなくmultisetを使用し、erase(値）ではなくerase(イテレータ)で一つだけ消去する必要がある。
・Nループの中でlog(最大M)の操作（erase(), insert()）を行うので、O(N log(M))
本番中は、AC20、TLE1で一時間どはまり。
K = 1やM = K = 1でmutlisetが空になった時の処理を加えて、やっとAC。
