途中寝かけたせいもあり、D1まででした。
D2. Two Hundred Twenty One (hard version)
D1で、さらに取り除くindexを指定するもの。
D1で（証明しなかったけど）偶奇さえあっていれば答えが得られた。ということは、ある区間の長さが奇数ならば、一つ削除することで全体を0にすることができる。なので、区間が偶数で0でない場合は、どこでも一つ削除してから考えて良い。
あとは、立式することが重要。区間[l : r]からxを削除するとすると、Sを累積和として、
・S[l : x-1]+S[x]+S[x+1 : r]＝S[l : r]=kとする
・S[l : x-1]-S[x+1 : r]=0
となれば良いので、計算すると、
・A[x]=1のときS[l : x]=k/2+1
・A[x]=-1のときS[l : x]=k/2-1
となれば良いと分かる。
なので、Sが条件を満たすもののうち、区間[l, r]に含まれるものを探せば良い。これは二分探索を使えばOK。
なお、コンテスト終了間際に大体この考察には至っていたのだけど、その後ずっとACできなかったのは、「区間[l, r]に含まれるものを探す」という条件を忘れていたせいでした。[l, r]に含まれないものを出力して、なんでWAなんだろう……とずっと考えていた。ひどい。
0 件のコメント:
コメントを投稿