公式

B - Hamming Distance is not 1 解説 by vwxyz

ヒント
ヒント 1 $2$ 進数表記で $1$ 桁しか異ならないような $2$ 整数の組があれば、そのどちらかしか $S$ に含めることができません。
ヒント 2 $2n$ と $2n+1$ のうち一方しか $S$ に含めることはできません。
ヒント 3 $L$ 以上 $R$ 以下の整数のうち、"およそ"半分しか $S$ に含められないことがわかりました。 "およそ"半分を $S$ に含めるような上手い構成がないか考えてみましょう。
ヒント 4 $L$ と $R$ の偶奇によっては、半分よりも少し多く $S$ に含められる可能性があります。ヒント 3 で考えた構成を条件を崩さない範囲で修正できないか考えてみましょう。
ヒント 5 $L$ が奇数で $R$ が偶数の場合は半分より多くの要素を $S$ に含められる場合があります。 小さい方の $L,R$ について実験するなどして、その条件を予想してみましょう。
ヒント 6 ヒント 5 で予想した条件下で構成方法を考えてみましょう。また、その条件を満たさないときに構成しようとするとどうなるか考えてみましょう。

投稿日時:
最終更新: