オムロンプログラミングコンテスト2026 （AtCoder Beginner Contest 479）F,G問題メモ

オムロンプログラミングコンテスト2026 （AtCoder Beginner Contest 479）

F - Narrow Passage

問題文

$N$ 人の人が数直線上に立っています。
人 $i$ は、はじめ座標 $S_i$ にいて、座標 $T_i$ に行きたいです。
- ただし、$S_i$ 同士、$T_i$ 同士はそれぞれ相異なります。
あなたは、以下の操作を繰り返し行うことができます。
- 人を $1$ 人選ぶ。その人が現在いる座標を $x$ としたとき、$x - 1$ または $x + 1$ に移動させる。ただし、移動先に人がいる場合は、移動先にいる人を同時に座標 $x$ に移動させる。
各人 $i$ が希望の位置にいる状態になるまでの操作回数として考えられる最小値を求めてください。

制約

$1 \leq N \leq 2 \times 10^5$
$0 \leq S_i, T_i \leq 10^9$
$i \neq j$ のとき $S_i \neq S_j$ かつ $T_i \neq T_j$
入力される値はすべて整数

WA解法

なんとなく、以下で上手くいきそうに見えたが、、、これはWAとなる。

■WA解法
M=Σ|Si-Ti| とする。ここから調整する。
  1. S用とT用に、座標を上下に2つ並べて書く。
  2. 各人の Si と Ti を結ぶ。
3-1. 違う方向に交差する点1つにつきコスト1節約できる。
3-2. 同じ方向に交差する点1つにつきコスト1余分にかかる。

  1  2  3  4  5    2→4と5→1、2→4と4→3の違う方向の交差が2つ
   ,-\----/---'    5→1と4→3の同じ方向の交差が1つ
  /   `--/-,       M=7 から、差し引き1節約できて、答えは6
  1  2  3  4  5

何故かというと、本当は距離 $1$ など少ししか移動しなくてよい人が、違う方向の人大勢とすれ違っても、その分だけコストが節約できることにはならない（むしろ増える方向に作用する）から。

多分この方向性でも解けると思うが、人ごとに左右からの交差で打ち消し合う分を考慮するなど、もう少し細かな考察が必要となる。

解法

$S_i,T_i$ に出現しないのも含め、全ての座標に人がびっしりいると考えると見通しが良くなる。この場合、操作は「隣接した人のswap」に言い換え可能となる。

出現しない座標にいるとした人を「仮想人」と呼ぶことにする。仮想人同士はswapする必要は無いので、$S$ における左から $j$ 番目の仮想人の行き先を、 $T$ における左から $j$ 番目の仮想人の位置にすればよい。

すると、問題は以下のようになる。

$T$ の並び順で、人（仮想人を含む）に $0,1,2,...$ と番号を振りなおす。
$S$ を、対応する新番号に置き換えた数列の、転倒数を求めよ。

S [0][1] 2 [3] 4  5      人 2→4, 4→3, 5→1 に対し、
       ,-\----/---'      仮想人は 0→0, 1→2, 3→5 が補完される。
      /   `--/-,         S を、T に対応した番号に置き換えた
T [0] 1 [2] 3  4 [5]     (0,2,4,5,3,1) の転倒数が答えとなる。

しかし、制約では座標は $10^9$ までの範囲を取り得るため、そのままでは転倒数は計算できない。

そこで、人/仮想人のペア毎に転倒数を分類してそれぞれで考える。

（仮想人,仮想人）のペアは、転倒は発生しない。

（人,仮想人）のペアは、$|(Sで人の左にいる仮想人の数)-(Tで人の左にいる仮想人の数)|$ だけ発生する。これはつまり、$i$ が $S,T$ の中でそれぞれ何番目に小さいかを $P_i,Q_i$ として、各人に対する $|(S_i-P_i)-(T_i-Q_i)|$ の和として、$O(N)$ で計算できる。

（人,人）のペアは、仮想人を除外し、人だけで転倒数を求めることで計算できる。

Python3

from atcoder.fenwicktree import FenwickTree


def solve(n, sss, ttt):
    sorted_sss = sorted(sss)
    mapping = {s: i for i, s in enumerate(sorted_sss)}
    sorted_ts = sorted((t, s) for s, t in zip(sss, ttt))

    ans = 0
    fwt = FenwickTree(n)
    for j, (t, s) in enumerate(sorted_ts):
        i = mapping[s]
        ans += abs((s - i) - (t - j))
        ans += fwt.sum(i, n)
        fwt.add(i, 1)

    return ans


n = int(input())
sss = list(map(int, input().split()))
ttt = list(map(int, input().split()))
ans = solve(n, sss, ttt)
print(ans)

G - Tuning

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N), B=(B_1,B_2,\dots,B_N)$ が与えられます。
長さ $N$ の有理数の列 $c=(c_1,c_2,\dots,c_N), d=(d_1,d_2,\dots,d_N)$ であって、以下の条件を満たすものを考えます。
- 全ての $1 \le i,j \le N$ について、 $(A_i+c_i)(B_j+d_j)=(A_j+c_j)(B_i+d_i)$
$\displaystyle \sum_{i=1}^{N} \left ( |c_i|+|d_i| \right )$ としてありうる最小値を求めてください。
本問題の答えは、分母が正・分子が非負である既約分数 $p/q$ としてただ一通りに表現できることが証明できます。この $p,q$ を出力してください。

制約

入力は全て整数
$2 \le N \le 2 \times 10^5$
$|A_i|, |B_i| \le 10^6$

解法

問題文は何を言ってるんだ？と読み取りづらいが、要は、「$A$ を $c$、$B$ を $d$ で調整することで、全ての $i$ について比 $A_i:B_i$ を等しくせよ」と言っている。

更に言い換えると、以下のようになる。

平面上に $N$ 点 $(A_i,B_i)$ がある。
原点を通る1本の直線を上手く引いて、各点と直線とのマンハッタン距離の総和を最小にせよ。
- ※ $x$ 軸方向の距離が $c$、$y$ 軸方向の距離が $d$ に相当する。

点と直線の“ユークリッド距離”なら垂線を下ろすなどちょっと面倒くさい計算が必要になるが、 “マンハッタン距離”は簡単で、「点からまっすぐ左右に移動して直線にぶつかるまでの最短距離」と「同、上下に移動」の近い方となる。しかも左右と上下のどちらが近いかは直線の傾きによって決まっていて、全ての点において直線の傾きの絶対値が $\ge 1$ なら左右、$\lt 1$ なら上下が近くなる。

つまり、$c$ か $d$、いずれかは全て $0$ だとしてよい。 $A$ と $B$ を入れ替えて2回解くことにすれば、$c$ が全て $0$ で、 $d$（$y$ 座標）を調整すると決め打ってよい。
以下、点と直線の「距離」というと、$y$ 座標の距離を指すとする。

原点を通る任意の直線に対し、$(A_i,B_i)$ と $(-A_i,-B_i)$ の距離は変わらないので、以下、$A_i \ge 0$ とする。
点は、第1と第4象限に位置することになる。

原点を通る直線の傾きを $-\infty～\infty$ まで、ぐるりんと変化させていくことをイメージする。この時、既に通過した点との距離は広がる一方で、まだ通過していない点との距離は縮まる。具体的には、傾きを $\epsilon$ 増やした時の距離の総和の変化量は以下のように $A$ の重み付き和の線形で表現できる。

$\displaystyle \left ( \sum_{i \in 通過}A_i - \sum_{i \in 未通過}A_i \right ) \epsilon$

最初は“未通過”の方に全ての点が入っていて、点を通過するたびに“通過”の方に移っていく。
はじめて $\sum_{通過}A_i \ge \sum_{未通過}A_i$ となるような点を通過した瞬間が最小値となる。

つまり、点を偏角ソートした上で、 $A$ の総和を $T$ として、$A_i$ の累積和が $\dfrac{T}{2}$ 以上となる最初の点が該当する。

直線が決まれば、各点に対し距離を求めれば答えとなる。

偏角ソートの際には $A_i=0$ の点があるとゼロ除算となるが、このような点は傾きによらず距離は固定値 $B_i$ なので、直線を決定する際は除いて、最後に足すことにしてよい。

Python3

from math import gcd


def solve(n, aaa, bbb):
    def sub(aaa, bbb):
        """ 上下方向に近づけるとして解く """
        points = []
        sum_a = 0
        for i in range(n):
            a = aaa[i]
            b = bbb[i]
            if a == 0:
                continue
            if a < 0:
                a, b = -a, -b
            points.append((b / a, a, b))
            sum_a += a
        if not points:
            return 0, 1  # 全点が y 軸上 → 距離 0

        points.sort()
        half = (sum_a + 1) // 2
        acc = 0
        ak = bk = 0
        for _, ak, bk in points:
            acc += ak
            if acc >= half:
                break
        p = sum(abs(bi * ak - ai * bk) for ai, bi in zip(aaa, bbb))
        q = ak
        g = gcd(p, q)
        return p // g, q // g

    p1, q1 = sub(aaa, bbb)
    p2, q2 = sub(bbb, aaa)
    if p1 * q2 <= p2 * q1:
        return p1, q1
    else:
        return p2, q2


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
print(*solve(n, aaa, bbb))

目次

オムロンプログラミングコンテスト2026 （AtCoder Beginner Contest 479）F,G問題メモ

F - Narrow Passage

問題文

制約

WA解法

解法

G - Tuning

問題文

制約

解法