考察

今回、問題文の条件を整理すると、

• 「各人から距離 \(L\) 未満は旗を置くことができない」
• 「各人から距離 \(R\) 以下に旗を \(1\) 本以上置かなければならない」

となります。

特に各人から距離 \(L\) 未満は旗を置くことができないことに注目します。旗が置ける座標の集合 \(S\) は、 \(\mathbb{Z}\) を整数全体の集合として、

\[ \begin{aligned} S = \mathbb{Z} \backslash \bigcup_{i=1}^N (A_i - L, A_i + L) \end{aligned} \]

となります。今、旗をいくつか置いたとし、置いた旗たちの座標の集合を \(F\) とします。このとき、 \(F \subset S\) です。

「各人から距離 \(R\) 以下に旗を置かなければならない」という条件によって、 \(I_i = S \cap [A_i - R, A_i + R]\) とすると、

\[F \cap I_i \ne \emptyset\]

という条件がつきます。 \(I_i = S \cap [A_i - R, A_i + R]\) は値がとびとびになっている可能性がありますが、 \(S\) の中の区間（すなわち、\(l, r \in I_i\)、\(x \in S\)、\(l\le x\le r\) なら \(x \in I_i\)）としてみなすことができます。このもとで、次の問題に帰着することができます。

区間がいくつか与えられます。旗を出来るだけ少ない本数立てて、すべての区間はその中に \(1\) 本以上の旗を含むようにしてください。

これは区間スケジューリングの双対問題そのものです。よって、この問題が解けました。しかし、このままだと実装が複雑です。

満点解法の実装方針

区間スケジューリング問題の解法に思いを馳せると、旗を置くことがありえる座標は、各区間の左端と右端になっているものしかありません。そして、特にそれらは

\[S \cap \left(\bigcup_{i=1}^N \{A_i-L\} \cup \{A_i+L\} \cup \{A_i-R\} \cup \{A_i+R\} \right)\]

の \(4N\) 点しかありません。ある座標が \(S\) に入っているかどうかは、二分探索を用いることで \(O(\log N)\) で判定することができます。そして、これらの座標に圧縮して区間スケジューリングの双対問題を解くことによって、比較的実装が楽になります。この問題が \(O(N)\) または \(O(N \log N)\) で解くことができました。

部分点解法

\[S \cap \left(\bigcup_{i=1}^N \{A_i-L\} \cup \{A_i+L\} \right)\]

の高々 \(2N\) 個をすべて置くと、最小化はされませんが条件をすべて満たします。