ABC409B - Citation
問題リンク : https://atcoder.jp/contests/abc409/tasks/abc409_b
解答リンク : https://atcoder.jp/contests/abc409/submissions/66585671
解法メモ
公式解説の通りなのだが、一部自分の勘違いによりWAとなってしまったのでメモを残す。
まずインプットとしてN、Aが与えられる。(簡単のためAは昇順にソート済みとする。)
非負整数xに対する命題P(x)を、「Aに、x以上の要素が重複を含めてx回以上現れる」こととして定義する。
自分がしてしまった勘違いは、以下である。
\max \{ x \mid x \in \mathbb{Z}_{\geq 0},\ P(x) \text{ が真} \}
\overset{?}{=}
\max \{ x \mid x \in A,\ P(x) \text{ が真} \}
要は非負整数に対して考えるところをAの要素に限定してしまったことが原因である。
これについて誤りであることを示していこう。
本番中は、以下を根拠として非負整数をAに限定してしまった。
A_i < x \leq A_{i+1}のとき、
P(x) \overset{?}{\Leftrightarrow} P(A_{i + 1})
しかしこれは、\Rightarrowが成立しない。
なぜなら、A_i < x \leq A_{i+1}にP(x)を仮定したとき、
x \leq \left| \left\{ j \mid j \in \mathbb{Z}_{\geq 0},\ A_j \geq x \right\} \right|
= \left| \{ i+1, \ldots, N \} \right|
= \left| \left\{ j \mid j \in \mathbb{Z}_{\geq 0},\ A_j \geq A_{i+1} \right\} \right|
となり、最右辺がx以上であることは示せても、A_{i+1}以上であることは証明できないからである。
例えばA = (1,\ 5,\ 5,\ 5)、x=2、i=1がその例に該当する。
補足
\Leftarrowは以下のように示せる。
A_i < x \leq A_{i+1}に対しP(A_{i + 1})としたとき、
\begin{aligned}
x & \leq A_{i + 1} \leq \left| \{ j \mid j \in \mathbb{Z}_{\geq 0}, A_j \geq A_{i + 1} \} \right| \\
& = \left| \{ j \mid j \in \mathbb{Z}_{\geq 0}, A_j \geq x \} \right|
\quad \left ( \because A_{i+1} \text{と} x \text{の間に} A \text{の要素は存在しない}) \right)
\end{aligned}
よってP(x)が成立する。
Discussion