2020-10-26から1日間の記事一覧
こういうことをしたくなります。 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(M2(N+M)) になります。 j は解を更新する可能性がある範囲しか調べなくてい…
こういうことをしたくなります。 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(M2(N+M)) になります。 j は解を更新する可能性がある範囲しか調べなくてい…