AtCoder Regular Contest 066 E - Addition and Subtraction Hard
過去問。
なんかやけにあっさり解けて、順位表見たら通してる人が意外と少なく、ついに僕も覚醒したか？ と思ったらXor Sum回だった
解法
正符号の後ろから括弧を開始するのは明らかに無意味です。ある負符号から何項かを括弧で括ることを考えます。（この括弧を外括弧と呼ぶことにします）
ここで、外括弧内の項はなるべく最終的に正にしてやりたいです。
このように負符号を区切りとして括るようにすると、与式において正符号が続く最初の何項かを除いて全部正にできることがわかります。
この最初の何項かというのは、外括弧の開始位置を固定して意味のある括り方をしようとすると必ず巻き込まれてしまいます。（必要な犠牲）
外括弧内の後ろの方は正にできるので、終了位置は与式の一番最後にするとよさそうです。外括弧は1つでよいこともわかります。
最終的に負となってしまうのは、開始位置からの何項かと、開始位置より前にあるもとから負だった項です。
ここまでわかれば、あとは与式を前から見ていって開始位置を動かしながら、なるべく大きくなるような答えを探せばよいです。
反省
正の項しかない場合の処理を忘れて1WA食らったものの、ほとんど解法に書いた道筋通りに考察を進め、スムーズに解くことができました。
コンテスト本番でもかくありたいものです。
AtCoder Regular Contest 101 D - Median of Medians
解けませんでした。そろそろ本番で700点問題を通せるようになりたい。
解法
答えを二分探索します。「の中央値が
以上かどうか」が判定できれば、それを満たす最大の
が答えとなります。
「の中央値が
以上かどうか」というのは、「
の中の区間のうち、
以上の要素が半数以上を占める区間が半数以上かどうか」と言い換えられます。
そのような区間の数を知るには、中の各要素を
以上ならば
、
未満ならば
と置き換え、その累積和の転倒してない数を求めてやればよいです。
全体の計算量はとなります。
反省
まず「の中央値が
かどうか」を求めようとしました。
を
で置き換えたやつの累積和の転倒してない数を求めればよさそうだと思いましたが、これをやるのに
かかるので、
を各
について試すとなると厳しいです。
を小さい要素から順に見て、差分を計算する……など考えましたが、うまくいきませんでした。
条件を緩くして二分探索に落とすという発想が一切出なかったところに頭の弱さを感じます。数え上げの問題などにも似たようなのがあるので慣れなきゃダメですね。
コンテスト直後ナーバスになって弱音を吐く僕↓
答えを二分探索する系の問題一生慣れる気がしない
— ウォンバット (@wombat_packer) 2018年8月25日
