B - Light It Up@エイシングプログラミングコンテスト2022(AtCoder Beginner Contest 255)の解法
はじめに
表題のプログラミング課題に取り組んだので備忘までに解法を記録する。
課題
問題文は下記を参照。
2次元座標に明かりを持った人と持っていない人が何人かずつ点在しており、後者に明かり届けるのに最低限必要な明かりの強さを求める問いである。明かりは全て同じ強さであり、明かりがあると半径 の範囲内を照らせるという舞台設定である(この が明かりの強さ)。
考え方
以下の手順で明かりの強さを求められる。
- 明かりを持っていない人が誰の明かりにあたるべきかを特定する
- 各明かりにどれだけの強さが必要かを求める
- で求めた明かりの強さの中で最大のものが問いの答えとなる
1. 明かりを持っていない人が誰の明かりにあたるべきかを特定する
明かりの強さを最低限にするには明かりを持っていない人は一番近くの明かりにあたってもらうことになる。
例えば次の図のように人々が点在しているとする。
分かりやすさ重視で「左」「中央」「右」の3エリアに明かりを持つ人と持たない人が偏在するようにしている*1。この場合、各エリアの明かりを持たない人は、同じエリア内の明かりにあたってもらうことになる。別エリアの明かりにあたる輩がいると、その分明かりを強くしなければならなくなるためである。
これで明かりを持たない人がどの明かりにあたるべきかを特定できた。
2. 各明かりにどれだけの強さが必要かを求める
次に、明かりを持つ人から見て、自身の明かりにあたる人の中で一番遠くの人までの距離を求める。
先の図で考えると、各エリアの明かりから〇で囲まれた人までの距離がそれである。
各エリアの明かりにはこの人を照らせるだけの強ささえあれば十分である。これで各エリアの明かりに必要な強さが分かった。
3. 2. で求めた明かりの強さの中で最大のものが問いの答えとなる
もはや99%答えは出ているが、2. で各明かりに必要な強さは分かったので、その中で最大のものが問いへの答えとなる。
解法
以上の手順を愚直に実装すればよい。AC(全てのテストをクリア)の Python コード例は下記の通り。 atcoder.jp
以上
*1:どのような配置でも考え方は変わらないはずである