変なしゃくとり法 - 模擬国内2020E

こういうことをしたくなります。

ans = 0
for i = 1, ..., m:
  for j = i, ..., m:
    if [i, j] がSAT:
      ans = max(ans, j - i + 1)
    else:
      break

SATの判定が O(N+M) なので、全体で O(M²(N+M)) になります。

j は解を更新する可能性がある範囲しか調べなくていいので i+ans から始めても良いです。

ans = 0
for i = 1, ..., m:
  for j = i+ans, ..., m:
    if [i, j] がSAT:
      ans = max(ans, j - i + 1)
    else:
      break

ただの定数倍改善に見えますが、よくみると計算量が改善していて O(M(N+M)) になっています。 SAT判定を呼ぶ範囲が計算量削減の本質で、これがしゃくとり法のような動きをします。（厳密にはしゃくとり法よりSAT判定を呼ぶ回数が少ない。）