D - Lazy Faith
はじめに
競技プログラミング、AtCoder Beginner Contest 119
D - Lazy Faith
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
東西方向に伸びる道路に沿ってA社の神社とB軒の寺が建っています。 西からi社目の神社は道路の西端からsiメートルの地点に、 西からi軒目の寺は道路の西端からtiメートルの地点にあります。 以下のQ個の問いに答えてください。 問i (1≤i≤Q): 道路の西端からxiメートルの地点から出発して道路上を自由に移動するとき 神社一社と寺一軒を訪れるのに必要な最小の移動距離は何メートルか？ (必要数を超えた数の寺社を通過してもよい。)
制約
・1≤A,B≤10^5 ・1≤Q≤10^5 ・1≤s1<s2<...<sA≤10^10 ・1≤t1<t2<...<tB≤10^10 ・1≤xi≤10^10 ・s1,...,sA,t1,...,tB,x1,...,xQはすべて異なる。 ・入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。 A B Q s1 : sA t1 : tB x1 : xQ
出力
Q行出力せよ。 i行目に問iへの答えを出力すること。
解き方
以下を参考にしています。
https://img.atcoder.jp/abc119/editorial.pdf
atcoder.jp
道路の西端からxiメートルの地点から出発して道路上を自由に移動するとき
神社一社と寺一軒を訪れるのに必要な最小の移動距離を考える。
Xiからの移動距離を最小にするにはどこを訪れればいいか
まずは神社で考えてみる。
訪れるのに最小の移動距離を出したいので
xiメートルの位置から訪れる可能性のある神社は
xiから東に進んで最も近い位置にある神社、
xiから西に進んで最も近い位置にある神社
のどちらかである。
西 ← 神社 神社 神社 Xi 神社 神社 → 東 ３ ２ １ ０ １ ２ ★ ★
上の図で言うと
Xiから西と東に
それぞれ1進んだ「★」がついている場所が
訪れる可能性のある場所である。
また、
上の神社の例では
西と東に進んだ最短距離の神社はどちらもXiから距離が「1」だが
この距離が例えば「1」と「2」のように異なっていたとしても
西と東でそれぞれ一つずつ、計2つの候補を考えておく必要がある。
それは、
神社だけではなく寺も訪れなければならないからである。
出力しなければいけない答えは
神社と寺を一つずつ訪れた際の最短距離なので
神社と同じように寺も西と東それぞれ最短距離のものに
訪れる可能性がある。
神社から考えると
寺が西と東、どちらのものに訪れれば
最短距離になるのか分からないので西と東の候補が必要
寺から考えると
神社が西と東、どちらのものに訪れれば
最短距離になるのか分からないので西と東の候補が必要
ということである。
神社の場合 西 ← 神社 神社 神社 Xi 神社 神社 → 東 ４ ３ ２ １ ０ １ ２ ３ ★ ★ ↑ ↑ 寺？ 寺？
寺の場合 西 ← 寺 寺 Xi 寺 → 東 ５ … ２ １ ０ １ ２ ３ ★ ★ ↑ ↑ 神社？ 神社？
訪れる可能性のある
神社の西と東でそれぞれ1つずつ、計2つ
寺の西と東でそれぞれ1つずつ、計2つの
組み合わせを考えると以下のようになる。
①Xi→西の神社→西の寺 ②Xi→西の神社→東の寺 ③Xi→東の神社→西の寺 ④Xi→東の神社→東の寺 ⑤Xi→西の寺→西の神社 ⑥Xi→東の寺→西の神社 ⑦Xi→西の寺→東の神社 ⑧Xi→東の寺→東の神社
この8つの中で距離が最短のものを出力すればよい。
西と東でXiから最短の神社と寺をどうやって求めるか
しかし、
ここで問題となるのは
どうやってXiから最短の神社と寺を求めるかである。
単にループを回すだけではタイムアウトするので
二分探索で高速に求める。
また、
二分探索で西と東のものをそれぞれ求める必要はなく
西か東、どちらかが求められれば
もう片方は次のインデックスとなるので
片方だけを求めればいい。
（例えば、
神社の位置を格納した配列を保存しておいて
Xiから西に進んで一番近い神社だけを二分探索で求め
仮にインデックスが「2」と返ってきたとき
Xiから東に進んで一番近い位置にある
神社のインデックスは「3」である。）
西 ← … 神社 Xi 神社 神社 … → 東 ｲﾝﾃﾞｯｸｽ … ２ ３ ４ … ★ ★
二分探索の方法については以下
ja.wikipedia.org
以下では、
Xiから西に進んだときに
最も距離の近い神社（寺）のindexを返すようにしている。
//二分探索
static long GetFirstIndex(long[] array, long startPlace)
{
//配列の長さが1以下なら必ずindexは0
if (array.Length <= 1) return 0;
//二分探索の右端
var top = array.Length - 1;
//二分探索の左端
var bottom = 0;
//bottom,startPlace,topの並びになったらおしまい
while (bottom + 1 != top)
{
//中央
var middle = (top + bottom) / 2;
//中央より大きい
if (array[middle] < startPlace) bottom = middle;
//中央より小さい
else if (startPlace < array[middle]) top = middle;
}
//西のindexが欲しいので左端を返す
return bottom;
}
引数は「long array, long startPlace」となっているが
これは
「long array」→神社（寺）の位置が入っている配列
「startPlace」→Xiの位置
である。
そして、まず
//配列の長さが1以下なら必ずindexは0
if (array.Length <= 1) return 0;
配列の長さが1以下ならば
神社（寺）は一つしかなく
必ずそこを訪れることになるので
決まりで「0」を返している。
次に
二分探索は探索範囲をだんだんと狭めていく
探索方法なので
一番初めは渡した配列を丸ごと探索範囲としている。
//二分探索の右端
var top = array.Length - 1;
//二分探索の左端
var bottom = 0;
そして、whileで
「bottom + 1 != top」
すなわち
bottom,startPlace,topの並びになるまでループを回している。
この並びは
「西に進んだときに最も近い位置にある神社、Xi、東に進んだときに最も近い位置にある寺」
の並びである。
内部の動きはそのまま二分探索で
//中央
var middle = (top + bottom) / 2;
//中央より大きい
if (array[middle] < startPlace) bottom = middle;
//中央より小さい
else if (startPlace < array[middle]) top = middle;
配列の中で中央を出して、
startPlace（Xi）が中央よりも大きければ
bottom（探索対象の左端）を中央にずらし、
startPlace（Xi）が中央よりも小さければ
top（探索対象の右端）を中央にずらしている。
これを繰り返すことに依って
範囲が段々と狭まり答えが出てくる。
最後は
Xiから西に進んだときに最も近い位置にあるindexが欲しいので
bottomを返している。
最短距離を出す
そして、
二分探索をして返ってきた
indexをもとにXiから東に進んだときに最も近い位置にあるindexを出し、
もう片方（先に神社を出していれば寺、そうでなければ神社）も
Xiから西に進んだときに最も近い位置にあるindexを取得して
それをもとにXiから東に進んだときに最も近い位置にあるindexを出し、
この4つから
全8パターンの中で最も最短距離で行けるものを出力する。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Cmondai
{
static void Main()
{
var abq = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
var A = abq[0];
var B = abq[1];
var C = abq[2];
//神社
var shrineArray = new long[A];
//寺
var templeArray = new long[B];
for (int i = 0; i < A + B + C; ++i)
{
if (i < A + B)
{
if (i < A) shrineArray[i] = Int64.Parse(Console.ReadLine());
else templeArray[i - A] = Int64.Parse(Console.ReadLine());
}
else
{
//スタート地点
var startPlace = Int64.Parse(Console.ReadLine());
//スタート地点から西に進んだときに最も近い位置にある神社のインデックス
var shrineFirstIndex = GetFirstIndex(shrineArray, startPlace);
//スタート地点から西に進んだときに最も近い位置にある寺のインデックス
var templeFirstIndex = GetFirstIndex(templeArray, startPlace);
//答えを入れる変数を用意
var ans = long.MaxValue;
//神社の西と東、計2つ
for (int j = 0; j < 2; ++j)
{
//神社が1つしかないなら、2つ目については考えないのでcontinueする
if (shrineArray.Length <= 1 && j == 1) continue;
//寺の西と東、計2つ
for (int k = 0; k < 2; ++k)
{
//寺が1つしかないなら、2つ目については考えないのでcontinueする
if (templeArray.Length <= 1 && k == 1) continue;
//神社と寺の距離
var distance = Math.Abs(shrineArray[j + shrineFirstIndex] - templeArray[k + templeFirstIndex]);
//スタート地点から神社と寺、どちらから行く方が早いか
var fast = Math.Min(Math.Abs(startPlace - shrineArray[j + shrineFirstIndex]), Math.Abs(startPlace - templeArray[k + templeFirstIndex]));
//距離が短いほうを採用
distance += fast;
//もしここで出た距離が現在の最短距離として保存してあるものよりも
//小さかったらアップデートする
if (distance < ans) ans = distance;
}
}
Console.WriteLine(ans);
}
}
}
//二分探索
static long GetFirstIndex(long[] array, long startPlace)
{
//配列の長さが1以下なら必ずindexは0
if (array.Length <= 1) return 0;
//二分探索の右端
var top = array.Length - 1;
//二分探索の左端
var bottom = 0;
//bottom,startPlace,topの並びになったらおしまい
while (bottom + 1 != top)
{
//中央
var middle = (top + bottom) / 2;
//中央より大きい
if (array[middle] < startPlace) bottom = middle;
//中央より小さい
else if (startPlace < array[middle]) top = middle;
}
//西のindexが欲しいので左端を返す
return bottom;
}
}
