問題ページ まず，各ケーブルについて爆弾 のスイッチを反転するという形に書き換えておきます． 爆弾のスイッチについて差分XORを取っておくと，区間に一様にXORするという操作は2点にXORを行う操作に帰着できます．この操作を繰り返し行ったときに，値を全…

問題ページ 36 を支払うときに価値1の紙幣を使う枚数は「6枚」か「0枚で価値10の紙幣1枚を支払ってお釣りで価値1を4枚もらう」の二択です．このように，各価値の紙幣を使う方法はぴったり同じ枚数を用いるか，一つ上の価値の紙幣を使ってお釣りをもらうかの…

問題ページ 番目の数が 以上か？という判定問題に単調性が存在することから，こうした問題では 番目の数を決め打つ二分探索を行うのが常套手段です． 「 番目の数が 以上か？」という問題は「 未満の数が 個以下か？」と言い換えることができます． を固定し…