【AtCoder】ABC 462 E - Alternating Costs

2026-06-14

AtCoder/ABC/E問題 AtCoder/ABC/450点問題 AtCoder/水Diff AtCoder/NoviSteps/1D AtCoder/偶奇を考える AtCoder/丁寧な場合分け AtCoder/対称性を利用する競技プログラミング

E - Alternating Costs

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 1226 / NoviSteps: 1Q / 配点: 450 点

問題概要

二次元平面上にコマが置かれており、はじめコマは座標 $(0,0)$ にある。

これから、以下の操作を $0$ 回以上何回でも行うことができる。

今コマがある座標を $(x,y)$ として、座標 $(x-1,y),(x+1,y),(x,y-1),(x,y+1)$ のいずれかにコマを移動させる。

$k$ 回目に行う操作にかかるコストは $k$ の偶奇によって異なり、それぞれ以下の通り。

$k$ が奇数のとき：今コマがある座標を $(x,y)$ として、座標 $(x-1,y),(x+1,y)$ に移動させる場合のコストは $A$ 、座標 $(x,y-1),(x,y+1)$ に移動させる場合のコストは $B$ である。
$k$ が偶数のとき：今コマがある座標を $(x,y)$ として、座標 $(x-1,y),(x+1,y)$ に移動させる場合のコストは $B$ 、座標 $(x,y-1),(x,y+1)$ に移動させる場合のコストは $A$ である。

コマを座標 $(X,Y)$ に移動させるために必要なコストの総和の最小値を求めよ。 $T$ 個のテストケースが与えられるので、それぞれについて答えを求めること。

制約

$1\le T\le 2\times 10^5$
$1\le A,B\le 10^9$
$-10^9\le X,Y\le 10^9$
入力される値は全て整数

考察

対称性より、 $x = |X|, \, y = |Y|$ として考えてよい。

まずは斜めに進む

手数の偶奇で移動コストが変わるのが面倒くさいので、まずは2手セットで考えると、

横 + 縦: $A + A = 2A$
縦 + 横: $B + B = 2B$

となるので、2手で斜め方向に1マス進むときの最小コストは $\min(2A, 2B) = 2 \min(A, B)$ である。

この移動方法で、できる限り目的地 $(x, y)$ に近づきたい。 $m = \min(x, y)$ とすると、 $m$ 回斜め移動を行って $(m, m)$ まで到達でき、その時の移動コストは $2m \min(A, B)$ である。

残りは縦か横に進む

残りの距離は $d = |x - y|$ である。ここでも、縦 or 横方向に2マスずつ進むことを考える。

横方向に2マス進む場合、例えば以下の2通りの移動方法が考えられる。

横 + 横: $A + B$
斜め右上 + 斜め右下: $2 \min(A, B) + 2 \min(A, B) = 4 \min(A, B)$

これは縦方向に2マス進む場合も同様である。

したがって、縦 or 横方向に2マス進むときの最小コストは $\min(A + B, 4 \min(A, B))$ である。

この移動方法を使えるのは、 $\left\lfloor \frac{d}{2} \right\rfloor$ 回であり、そのときの移動コストは $\left\lfloor \frac{d}{2} \right\rfloor \cdot \min(A + B, 4 \min(A, B))$ である。

$d$ が奇数のときは最後に1マス進む

$d$ が偶数であればこれで議論は終わりなのだが、奇数の場合は最後にもう1マス進む必要がある。

ここで、「横1マスなら $+ A$ 、縦1マスなら $+ B$ 」と安易にしてはダメ(自戒)。

例えば、 $(0, 0) \to (1, 0)$ に横に1マス進むときの移動方法は以下の2通りある。

普通に横に1マス進む: $A$
$(0, 0) \to (0, 1) \to (1, 0) \to (1, 0)$ : $B + B + B = 3B$

したがって、横に1マス進むときの最小コストは $\min(A, 3B)$ である。

同様に、縦に1マス進むときの最小コストは $\min(3A, B)$ と書ける。

以上をまとめると、求める最小コストは以下のように計算できる。

2 \min(A, B) \times \min(x, y) + \min(A + B, 4 \min(A, B)) \times \left\lfloor \frac{|x - y|}{2} \right\rfloor \\ + \begin{cases} \min(A, 3B) & ((|x - y| が奇数) かつ (x > y)) \\ \min(3A, B) & ((|x - y| が奇数) かつ (x < y)) \\ 0 & (|x - y| が偶数) \end{cases}

実装例

実装時はlong long型で計算する必要があることに注意。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.using ll = long long;
5. 
6.// ======================================== //
7. 
8.ll solve() {
9.    ll A, B, X, Y;
10.    cin >> A >> B >> X >> Y;
11. 
12.    ll x = abs(X), y = abs(Y);
13. 
14.    ll diagonal = 2 * min(A, B);
15.    ll axis = min(A + B, 4 * min(A, B));
16. 
17.    ll cost = diagonal * min(x, y) + axis * (abs(x - y) / 2);
18.    if (abs(x - y) % 2 == 1) {
19.        if (x > y) cost += min(A, 3 * B);
20.        else if (x < y) cost += min(3 * A, B);
21.    }
22. 
23.    return cost;
24.}
25. 
26.int main()
27.{
28.    int T;
29.    cin >> T;
30. 
31.    while (T--)
32.    {
33.        cout << solve() << endl;
34.    }
35. 
36.    return 0;
37.}