Cまで三完。Dは難しい。
D. Reverse Sort Sum
解説AC。
コンテスト中は、A[i]=1となるindex iがあったとき、Cでプラスする箇所（n個）はどこか？ という方針でずっと考えていた。（この方針で解けるかは分からないが）解説の方針とは違っていた。
解説の方針は、問題文のようにシミュレーションしたのを逆から見る、という方法。B[i]が何か（プラスになるindexはどこか？）というのを調べていく。
ただ、この方針が取れれば簡単というわけでもなく、その後、A[i]=0ならB[i]が寄与するindexの最小値が一つ小さくなる、ということに気付かなくてはいけなかった。これも結構難しいと思う。
考察重視の問題で、ARCとかで出てもおかしくなさそうに見えた。（Ratedなコンテストで出てたら厳しかった）
0 件のコメント:
コメントを投稿