日本情報オリンピック 第3回 女性部門

2023年1月24日
情報オリンピック日本委員会

解説

解説担当：山縣龍人

小課題 1

小課題 1 では，鐘が 1 つしかないため，座標 x で聞こえる鐘の音の強さは max{ K - |x - A₁|, 0 } である．

これをそれぞれの家の座標ごとに求め，出力すれば良い．時間計算量は Θ(M) である．

小課題 2

小課題 2 では，鐘が複数になるため，最も強く聞こえる鐘を探す必要がある．

i = 1, 2, …, N のそれぞれについて max{ K - |x - A_i|, 0 } を求め，これの最大値を取れば，座標 x で聞こえる鐘の音の強さが分かる．

これをそれぞれの家の座標ごとに求め，出力すれば良い．時間計算量は Θ(NM) である．

小課題 3

小課題 3 では，Θ(NM) 時間の解法では間に合わないため，最も強く聞こえる鐘を効率的に探す必要がある．

ここで，鐘の音の強さの定義から，「最も強く聞こえる鐘」とは「最も近くにある鐘」であることが分かる．すなわち，それぞれの家ごとに，その家に最も近い鐘を見つければ良い．

これは，二分探索によって家ごとに Θ(log N) 時間でできるから，全体で Θ(N + M log N) 時間で解ける．

また，B をソートして尺取り法によって最も近い鐘を見つける方法もあり，この場合は Θ(N + M log M) 時間で解ける．