A - Circular Distance Editorial by maroonrk_admin
人 \(0\) を必ず選ぶことにした場合の答えがわかれば,それを \(L/N\) 倍することで本来の答えになります.
人 \(0\) を必ず選ぶことにします. 各 \(D=1,2,\cdots,\) について,コストが \(D\) 未満になるような選び方が何通りあるかが求まればよいです.
まず,人 \(D,\cdots,L-D\) は選べません.
次に,人 \(1,2,\cdots,D-1\) の中で誰を選ぶか考えます. これは互いに干渉せず,自由に選ぶことができます.
最後に,人 \(L-D+1,\cdots,L-1\) の中で誰を選ぶか考えます. 人 \(i\) を選ぶための条件は,人 \([i-L+D,i-D]\) を今までに選んでいないことです. ここで,この区間は基本的には \([1,D-1]\) 内に含まれます. \(2D \leq i\) の場合この区間をはみ出してしまいますが,はみ出た部分は \([D,L-D]\) に含まれています.この区間の人は選ばないことが最初にわかっているので,特に考慮する必要はありません.
\(W=L-2D+1\) とおきます. 人 \(L-D+1,\cdots,L-1\) から人を選ぶ操作を,人 \(1,\cdots,D-1\) の中で長さ \(W\) の区間を選ぶ操作とみなします.
すると考えるべきは,人 \(1,\cdots,D-1\) の中から人と区間を選び,それらが交わらないようにする(区間同士が交わるのは構わない)という操作です.
人を選ぶ操作で選んだ人を赤い人と呼ぶことにします.また,区間を選ぶ操作に対し,その区間の先頭の人を青い人と呼ぶことにします.
赤,青が入れ替わる回数を固定すると,選び方の総数は二項係数の式で記述できます. また,入れ替わる回数は高々 \(N/W\) 回です.
よってこの計算をそのまますべての \(D\) について行えば,計算量は \(O(N+N/2+N/3+\cdots)=O(N \log N)\) となり,十分高速です.
posted:
last update: