torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

AtCoder Beginner Contest 170, C : Forbidden List

問題概要

 整数 $X$ と長さ $N$ の整数列 $\{ p_i \}$ が与えられる.$p$ に含まれない整数であって,$X$ との差の絶対値が最も小さいものを求めよ.答えが複数ある場合は,値が最も小さいものを答えよ.

制約

  • $1 \leq X \leq 100$
  • $0 \leq N \leq 100$
  • $1 \leq p_i \leq 100$

解法

 $p_i$ の制約から,$0$ 以下の整数および $101$ 以上の整数は禁止されておらず,また,$X$ は $1$ 以上 $100$ 以下なので,答えは $0$ 以上 $101$ 以下の整数です.この範囲で禁止されていない整数全てについて $X$ との差を計算するなどすれば答えが求まります.
 実装テクとしては,各整数 $i$ について $( | X - i |, i )$ というペアを作ってソートしてから先頭を参照すると楽だと思います.

コード (Haskell)

readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine

main = do
	[ x, n ] <- readInts
	ps <- readInts
	print $ snd $ head $ sort $ do
		i <- [ 0 .. 101 ]
		guard $ not $ i `elem` ps
		return ( abs ( i - x ), i )