AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の70問目である「070 – Plant Planning（★4）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【070 – Plant Planning（★4）】
問題概要
二次元平面上にN棟の工場が存在し、i番目の工場は座標(Xi,Yi) に位置しています。目的は、発電所を建設する最適な位置を選び、その位置での発電所から各工場までのマンハッタン距離の総和（不便さ）が最小となる値を求めることです。
考察
この問題を直感的に解くためには、まず1次元の問題として考えることがポイントです。なぜなら今回距離はマンハッタン距離で定義されているためです。
\(マンハッタン距離=∣x_1−x_2∣+∣y_1−y_2∣\)
マンハッタン距離の場合は、xとyはそれぞれ独立に計算することができるため、まずは考察を簡単にするために1次元(x)のみで考えてみます。
1次元での考察
工場が以下のように1次元上に存在する場合を考えます。
1 3 6 7
---------発電所の位置を a としたとき、a は3から6の間のどこかに置けば良いことがわかります。その理由は以下の通りです。
aの位置を3から4に移動すると、工場1と3の移動距離は1ずつ増えるが、工場6と7の移動距離は1ずつ減少する。結果的に全体の移動距離は変わらない。- しかし、
aの位置を3から2に移動すると、工場1の移動距離は1減少するが、工場3, 6, 7の移動距離は1ずつ増加する。全体の移動距離が増えてしまう。
この考察から、a の最適な位置は中央値（数列が偶数の場合は、N/2 と N/2+1 の間）であることがわかります。
2次元での考察
上記の1次元での考察をX座標とY座標にそれぞれ適用することで、2次元上での発電所の最適な位置を求めることができます。
典型解法：マンハッタン距離
コード
N = int(input())
X = []
Y = []
for i in range(N):
x,y = map(int, input().split())
X.append(x)
Y.append(y)
X.sort()
Y.sort()
x = X[N//2]
y = Y[N//2]
ans = 0
for i in range(N):
ans += abs(x-X[i]) + abs(y-Y[i])
print(ans)
コメント