🌷
AtCoder Beginner Contest 419 C - King's Summit

2025/08/28に公開
テーマ「フリーテーマ」
 AtCoder Beginner Contest 419 C - King's Summit問題はこちら

 問題を解く時の思考の流れN 人の人にとって一番都合のいいマスがわかると嬉しい
1 を求めるためには、全探索だとマスの数だけかかり、グリッドの大きさは 10^9 行 10^9 列のため間に合わなさそう
そもそも2次元で複雑な気がするので、1次元で考えてみたい
1次元の場合で考えてみる
a. x 軸上に M 人の人がおり、はじめ i 人目はマス x_i にいるとする
b. この場合、都合のいいマスは、「みんなにとっての中心っぽい」場所にありそう
c. b をより具体的に考えてみると、一番離れている人たちの真ん中が都合のいいマスになりそう
d. 具体的には、x = [5, 1, 3, 6, 9, 2] のような場合、マス 1 にいる人とマス 9 にいる人の真ん中が最適な場所になりそう。これは、マス 1 と 9 以外の場所にいる人は、マス 1 や 9 にいる人よりも早く最適な場所へ移動できるから。
1次元の場合はうまくいきそうだけど、2次元の場合も同じように考えられるか。 x 軸と y 軸は独立して考えられそうなので、それぞれの軸方向に対して 4 と同じことを考えれば良さそう。 8 近傍のマスへ移動できるので、どちらの軸方向にも同時に 1 マス動ける。
つまり、答えは x 軸の最小値と最大値の差と、 y 軸の最小値と最大値の差の大きい方を 2 で割ったものになりそう。
5 において、2 で割り切れなかった場合はどうなるだろうか。 2 で割り切れる場合は真ん中を全員が集まるマスとして、一番離れている人がそのマスまで移動にかかる時間を出力すればいいが、 2 で割り切れない場合は下記具体例のようになる。
<具体例>
再度一次元で考えてみると、一番離れている人がマス 1 とマス 6 にいた場合、全員が集まるマスとしてはマス 3 かマス 4 が選ばれる。マス 3 が選ばれた場合は、マス 1 にいた人は時刻 2 にマス 3 についているが、マス 6 にいた人は時刻 3 にマス 3 に到着する。一方、マス 4 が選ばれた場合は、マス 1 にいた人は時刻 3 にマス 4 についているが、マス 6 にいた人は時刻 2 にマス 4 に到着する。
このように、最適なマスに集まる時間がズレるので、 2 で割るのではなく、 2 で切り上げ除算をする必要がある。

 実装慣例に則り、問題文中で大文字となっている変数名も全て小文字にしているので注意してください。
n = int(input())
r = [0 for _ in range(n)]
c = [0 for _ in range(n)]
for i in range(n):
    tmp_r, tmp_c = map(int, input().split())
    r[i] = tmp_r
    c[i] = tmp_c

tmp = max(max(r) - min(r), max(c) - min(c))
# 切り捨て除算
if tmp % 2 == 0:
    print(tmp // 2)
else:
    print(tmp // 2 + 1)

 教訓理想の状態から考えてみる
次元を落として考えてみる

 おまけ移動できるマスが、 8 近傍ではなく、上下左右に隣接するマスのみの場合を考えてみる。厳密には、現在いるマスをマス (i, j) として、マス (i, j), (i+1, j), (i-1, j), (i, j+1), (i, j-1) のうち存在するマスのいずれかに移動する。
この場合は、いずれか片方の軸方向にしか同時には移動できないので、答えは x 軸の最小値と最大値の差と、 y 軸の最小値と最大値の差をそれぞれ 2 で切り上げ除算し、その和を求めれば良い。
n = int(input())
r = [0 for _ in range(n)]
c = [0 for _ in range(n)]
for i in range(n):
    tmp_r, tmp_c = map(int, input().split())
    r[i] = tmp_r
    c[i] = tmp_c

ans = 0
tmp_r = max(r) - min(r)
if tmp_r % 2 == 0:
    ans += tmp_r // 2
else:
    ans += tmp_r // 2 + 1

tmp_c = max(c) - min(c)
if tmp_c % 2 == 0:
    ans += tmp_c // 2
else:
    ans += tmp_c // 2 + 1

print(ans)
おまけが間違ってたら連絡ください🙏
AtCoder Beginner Contest 419 C - King's Summit

問題を解く時の思考の流れ

実装

教訓

おまけ

Discussion
