ARC 101-200/ARC198A - I hate 1 - 競技プログラミング用 知識集積所

---

問題

ARC198A

必要知識

簡単な内容は省略

考え方

要素数を上からと下からでそれぞれ評価する。

まず上から。
連続する2つの整数を両方採用することはできない。
また、1を他の数と同時に採用することはできない。
よって、大きい方から2つずつ区切ったときにそれぞれの組から片方しか多くとも1つしか採用できないことを考えると、偶数の場合はその半分、奇数の場合は半分（切り捨て）が上限となる。

今度は下から。
n以下の偶数全部を詰め込んでみる。
偶数同士で割り算した場合、余りは絶対に偶数であり、1にはならない。
つまり、この集合は良い集合である。
よって、偶数の場合はその半分、奇数の場合は半分（切り捨て）が下限となる。

つまり、最大要素数は、偶数の場合はその半分、奇数の場合は半分（切り捨て）。
中身は、n以下の全ての偶数。
これを出力すればいい。

ただし、1つだけ罠がある。
1は、他の数と同時に採用することはできないが、単独なら採用できる。
よって、n=1の場合は1だけ採用したものが答えとなるので、別枠で答える必要がある。

解答例

解答例

注意点

コーナーケースに注意。

考え方のところ参照。

別解