[Java]ABC134の[B,E]の反省
ABCがABCDEFになってからかなり易化したのに緑パフォ出しちゃったのでこれはマズい。
B - Golden Apple
想定解だと(N+2D)/(2D+1)を出力してO(1)。
自分は左から一人ひとり監視員を置いていくシミュレーションを行ったO(N)。
シミュレーションを行った理由は数式で提出するとコーナーケースが漏れそうな気がするからだけど、変に気合入った設問でN<=10^10とかだったとすると多分躓く。早急に改善したいところ。
C - Exception Handling
最大値AmaxとなるAが二つ以上あると、どのAを取り除いたとしても最大値はAmax。
最大値が一つの時その最大値を取り除いた時の最大値は数列A1,A2,...の中で二番目に大きい数。
よってAの中で一番目に大きいものとそのインデックス、二番目に大きいもの、の3つを一回の精査で見つけておけばいい。
自分がリアルタイムでやった時は2番目に大きいものを見つけるためにソートしてて無駄が多い。ここも精進ポイント。
D - Preparing Boxes
i番目の箱にボールの数をBiとして考える。
よく考えると箱の後半部分の(∀i>n/2)でAi=Biであることが分かる。
次に箱の前半部分を考えると、i<=n/2のAi=Sum(Bj,j=i,2i,3i...)(mod 2)=>Bj=Ai+Sum(Bj,j=2i,3i...)(mod 2)なので、Biを降順を降順に求めることで全部求めることができる。
コンテスト後にTwitter見てるとこの計算量で躊躇してる人が多かったっぽい。
N+N/2+N/3+...ってのは何か大学受験した時の数学思い出して懐かしかった。（小並感）
E - Sequence Decomposing
解けなかった。これ千人通すのくっそ怖い。
とりあえず対偶取ったとこまでは良かったと思う。
最初にぱっと思いついたのが転倒数。
次に考えたのがLISのDPを変形してAの数列を増加部分列にうまく分割する方法で、それをずっと考えてた。
対偶取ったとこから素直にAi>=Ajを考えてれば減少部分列を思いついたかもしれない。猛省だ。
