けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 330 B - Minimize Abs 1 (灰色, 200 点)

AtCoder AtCoder200点 ABC-B 灰色diff クエリ処理問題絶対値やminを扱う問題算数と数学 if文区間関数max() 数学(代数) 算数と数学:条件を筋よく整理する

問題の理解がちょっと大変。数学の素養がないと厳しいかもしれない。

問題へのリンク

問題概要

正の整数 $L, R$ ( $L \le R$ を満たす) が与えられる。

また、 $N$ 個の整数 $A_{1}, A_{2}, \dots, A_{N}$ が与えられるので、各 $i = 1, 2, \dots, N$ について、次の条件を満たす整数 $x$ を求めよ。

$L \le x \le R$ である
$L$ 以上 $R$ 以下の任意の整数 $y$ に対して、 $|x - A_{i}| \le |y - A_{i}|$ を満たす

制約

$1 \le N \le 2 \times 10^{5}$
$1 \le L, R, A_{i} \le 10^{9}$

考えたこと

まず、問題を理解するのが大変だ。こういうときは、具体例で掴んでみよう。たとえば、 $L = 4$ , $R = 7$ としてみよう。そして、いろんな $A$ を試してみて、 $x$ を求めてみる。そうすると様子が掴めてくる。

なお、 $|x - A_{i}|$ とは「数 $x$ と数 $A_{i}$ の差」を表すということに留意しておこう。

$A = 1$ のとき、 $4$ 以上 $7$ 以下の整数のうち、 $A$ との差が最も小さいものは $4$ である。よって、答えは 4。
$A = 2$ のとき、同じく、答えは 4・
$A = 4$ のとき、同じく、答えは 4
$A = 5$ のとき、 $4$ 以上 $7$ 以下の整数のうち、他でもない $5$ がその差を 0 にすることができて、最も小さい。よって、答えは 5。
$A = 6$ のとき、同じく、答えは 6
$A = 7$ のとき、同じく、答えは 7
$A = 8$ のとき、 $4$ 以上 $7$ 以下の整数のうち、 $A$ との差が最も小さいものは $7$ である。よって、答えは 7。
...

というように手を動かしてみよう。段々と次のことがわかってくるはずだ。

$A \lt L$ のときは、 $A$ との差が最も小さいのは $L$
$L \le A \le R$ のときは、 $A$ との差が最も小さいのは $A$
$A \gt R$ のときは、 $A$ との差が最も小さいのは $R$

これを実装すれば正解できる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, L, R;
    cin >> N >> L >> R;
    
    for (int i = 0; i < N; ++i) {
        long long A;
        cin >> A;
        
        if (A < L) cout << L << " ";
        else if (A > R) cout << R << " ";
        else cout << A << " ";
    }
    cout << endl;
}