ABC462 E - Alternating Costs

考え方

考察問題。
出力が経路でないとはいえ、実質的に経路作成をする構築問題でもある。

以下、$X$ 座標を増やす行為を 右、減らす行為を 左 と表記する。
同様に、$Y$ 座標を増やす行為を 上、減らす行為を 下 と表記する。

まず、対称性を利用して問題のパターンを減らす。
目標地点が $X<0$ である場合、まるごと左右反転することで $X>0$ の問題に帰着できる。
同様に、$Y<0$ である場合、まるごと上下反転することで $Y>0$ の問題に帰着できる。
さらに、$X<Y$ である場合、swap(X,Y) と swap(A,B) を同時に行う。
以上で、$Y=0$ や $X=Y$ の場合も含めて $0 \leq Y \leq X$ である場合だけ解けばいいことになる。

次に、経路構築の前に問題の分析をする。
格子点を縦横に $1$ つずつ移動するとなると、パリティで考察することができる。
すなわち、$(0,0)$ からのマンハッタン距離が偶数である点と奇数である点に分類する。
そうすると、可能な全ての移動が「偶数→奇数」または「奇数→偶数」になる。
つまり偶数と奇数を交互に移動することになるため、移動コストは、以下のように理解してよい。

• 「偶数→奇数」の移動では、左右移動コストが $A$、上下移動コストが $B$
• 「奇数→偶数」の移動では、左右移動コストが $B$、上下移動コストが $A$

また、経路構築する上で、いくつか「コストも目的地も不変な変更」を考えておく。

$1$ つめに、操作列1 右 操作列2 左 操作列3 は 操作列1 左 操作列2 右 操作列3 に変更可能。
これは、各移動が上下移動なのか左右移動なのかが変化せず、総移動量も変化しないため。
上下についても同様。

$2$ つめに、操作列1 右 右 上 操作列2 は 操作列1 上 右 右 操作列2 に変更可能。
これも、各移動を偶数マスから行うか奇数マスから行うかの回数が変化せず、総移動量も変化しないため。
上 上 右 や 上 上 左 なども同様。

これらを活用することで、コスト最小の操作列の $1$ つを貪欲に決めることができるようになる。

まず、$X>0$ である場合、操作列の中に 右 が必ずある。
もし最小コスト操作列の最初の 右 より前に 左 があるなら、それらを入れ替える。
それにより、最初の 右 より前に 左 が存在しない操作列に変化させられる。

同様に、$Y>0$ である場合、最初の 上 より前に 下 が存在しない操作列に変化させられる。

最後に、上 上 右 を 右 上 上 にしたり 右 右 上 を 上 右 右 にしたりする。
それにより、最初の $2$ つの片方が 上 でもう片方が 右 であるようにできる。

以上により、最小コストとなる操作列の中に、$2$ ターン後に必ず $(1,1)$ にいるものが存在する。
つまり、$2 \times \min(A,B)$ のコストで $(1,1)$ に行くことを貪欲に決めてしまってよい。
そしてこれを再帰的に繰り返すと、最終的に $Y$ 座標が目的地と一致するまで行える。
こうなると残りは $Y=0$ である問題に帰着される。

最後に、$Y=0$ の問題の解法を考える。
これは、実は以下の $2$ つを満たす経路だけ考えればよい。

• $0 \leq Y \leq 1$ 範囲から外に出ない
• $(0,0)$ から $(X,0)$ まで $X$ 軸上の点を全て経由する

前者の理由は単純で、そこから出る経路に対し、出入する $2$ 回の上下移動を入れ変えればよい。
それでもはみ出ている場合は再帰的に繰り返せば、だんだんはみ出している区間が短くなる。
そして、最終的にはみ出している区間の長さが $0$ になる。

後者の理由は以下。
$(0,0)$ から $(X,0)$ までに $X$ 軸上の点の中に通らない点があると仮定する。
その場合、そこを通る付近に 上 右をk回 下 $(k \geq 2)$ という操作列があるはず。
これを 上 右をk-2回 下 右 右 に変更することを再帰的に繰り返す。
すると、上 と 下 との間の 右 の個数を $0$ か $1$ にでき、$X$ 軸上の点をすべて通る操作列になっている。

ということで、$Y=0$ の問題は、単純に $1$ マスずつ右を目指せばよい。
つまり、右 か 上 右 下 かの $2$ 択を $X$ 回繰り返せばよい。
偶数からの移動は $\min(A,3B)$、奇数からの移動は $\min(B,3A)$ のコスト。
これで $(0,0)$ から $(X,0)$ まで最小コストでたどり着くことができる。

以上から、「可能な限り斜め移動した後で横移動」という経路を貪欲に選んでコストを計算すればよい。
同じ操作はまとめて計算することで、テストケースあたり $O(1)$ で答えられる。

入力例1での動作

入力例1の $5$ つめのテストケースで動作を確認する。

入力を受け取る。

a: 31
b: 9
x: -74
y: -60

対称性を利用して、目標地点の座標をともに非負にする。
今回は $|X|=74$, $|Y|=60$ で $X \geq Y$ なので、縦横の入れ替えは必要ない。

まず、横移動と縦移動を $1$ 回ずつ行う $2$ 手を $60$ 回繰り返し、$(0,0)$ から $(60,60)$ まで進む。
各 $2$ 手は、安い方のコストを両方の移動に使える順序を選べるので、$2\times \min(31,9)=18$ かかる。

したがって、ここまでのコストは $18 \times 60=1080$ である。
残りは、$(60,60)$ から $(74,60)$ まで横に $14$ マス進めばよい。

横に $1$ マス進む最小コストは、移動前のパリティによって次のようになる。

残り $14$ マスに必要なコストは $189+63=252$ である。
よって、最小コストは $1080+252=1332$ となる。

注意点

コストの値が大きいと、総和はあっさり int 型からはみ出る。
long long 型を用いること。

別解

特になし。