コンテンツにスキップ

DOJ Beginner Contest 9 D - Harvesting the Farm

サイト
DOJ
コンテスト
DOJ Beginner Contest 9
問題
D - Harvesting the Farm

RR 行 CC 列の農場の NN 個のマスに作物があり、ii 番目の作物は YiY_i 行 XiX_i 列にあります。

収穫機は 1 つの列の中で、連続するいくつかの行を占めます。最初は SrS_r 行 ScS_c 列の 1 マスだけを占めています。収穫機には次の 2 つの操作ができます。

  • 拡張:収穫機の上端か下端に 1 マス付け足す。
  • 移動:収穫機全体を左か右に 1 マスずらす。

操作のあと収穫機が占めるマスに作物があれば、すぐに収穫されます。収穫機が農場の外にはみ出してはいけません。すべての作物を収穫するのに必要な操作回数の最小値を求める問題です。

テストケースは T≤5×104T \le 5 \times 10^4 個あり、NN の総和は 10510^5 以下です。

作物と収穫機の最初の位置を合わせて、

  • 行の最小値を uu、最大値を dd
  • 列の最小値を ll、最大値を rr

とします。答えは

(d−u)+(r−l)+min⁡(Sc−l,r−Sc)(d - u) + (r - l) + \min(S_c - l, r - S_c)

です。

拡張は d−ud - u 回必要で、それで足りる

Section titled “拡張は d−ud - ud−u 回必要で、それで足りる”

収穫機は常に SrS_r 行を含み、拡張 1 回で 1 行ずつしか広がりません。uu 行と dd 行の作物を収穫するには、収穫機がどこかで uu 行と dd 行に届く必要があります。収穫機は縮まないので、最終的には uu 行から dd 行まで全部を占めることになり、拡張は少なくとも d−ud - u 回必要です。

逆に、最初に ScS_c 列で uu 行から dd 行まで広げてしまえば、あとはどの列に行っても、その列の作物はすべて収穫できます。

移動は (r−l)+min⁡(Sc−l,r−Sc)(r - l) + \min(S_c - l, r - S_c) 回必要で、それで足りる

Section titled “移動は (r−l)+min⁡(Sc−l,r−Sc)(r - l) + \min(S_c - l, r - S_c)(r−l)+min(Sc​−l,r−Sc​) 回必要で、それで足りる”

ll 列から rr 列までのすべての列に、収穫機が少なくとも 1 回は行く必要があります。ScS_c 列から始めて両端に行く最短の動き方は、近いほうの端に行ってから、反対の端まで行くことです。

  • 先に左端に行くと、(Sc−l)+(r−l)(S_c - l) + (r - l) 回
  • 先に右端に行くと、(r−Sc)+(r−l)(r - S_c) + (r - l) 回

なので、移動は (r−l)+min⁡(Sc−l,r−Sc)(r - l) + \min(S_c - l, r - S_c) 回です。

拡張を先に全部済ませてから移動すれば、両方の下限を同時に達成できます。

Python
for _ in range(int(input())):
R, C = map(int, input().split())
Sr, Sc = map(int, input().split())
N = int(input())
YX = [tuple(map(int, input().split())) for i in range(N)]
u = d = Sr
l = r = Sc
for y, x in YX:
u = min(u, y)
d = max(d, y)
l = min(l, x)
r = max(r, x)
ans = d - u
f = min(Sc - l + r - l, r - Sc + r - l)
print(ans + f)

ans が拡張の回数、f が移動の回数です。