AtCoder Beginner Contest 170 C

AtCoder Beginner Contest 170 C を Python で

AtCoder Beginner Contest 170 C を Python で解説していきたいと思います。twitter 界隈ではこの問題の解説が煽ってるなどなどと色々話題になっていましたが,どうなんでしょうか。確かに言っていることは間違っていないと思いますが,個人的にはもうちょっと配慮のある書き方をしても良かったのではないかと思います。
まぁそれは置いておいて,まずはいつも通り問題文から行きます。


C – Forbidden List


実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

整数 X と、長さ N の整数列 p1,…,pN が与えられます。

整数列 p1,…,pN に含まれない整数 (正とは限らない) のうち X に最も近いもの、つまり X との差の絶対値が最小のものを求めてください。そのような整数が複数存在する場合は、そのうち最も小さいものを答えてください。

制約

  • 1≤X≤100
  • 0≤N≤100
  • 1≤pi≤100
  • p1,…,pN はすべて異なる。
  • 入力中のすべての値は整数である。

入力

入力は以下の形式で標準入力から与えられる。

X N
p1 pN

出力

答えを出力せよ。


入力例 1

6 5
4 7 10 6 5

出力例 1

8

整数列 4,7,10,6,5 に含まれない整数のうち、最も 6 に近いものは 8 です。


入力例 2

10 5
4 7 10 6 5

出力例 2

9

整数列 4,7,10,6,5 に含まれない整数のうち、最も 10 に近いものは 9 と 11 です。このうち小さい方である 9 を出力します。


入力例 3

100 0

出力例 3

100

N=0 の場合、入力の 2 行目は空行となります。また、この場合のように、X 自身も答えとなりえます。


解説

与えられた整数列 p にない数のうち,X に最も近い最小の整数を出力せよという問題です。X 自身が答えになる場合にも注意しましょう。

ここでは,言われたとおりに X に最も近い数から順にその数が p にないかどうかを判定していけばよいでしょう。つまり
X,X-1,X+1,X-2,X+2,…
とこのような順で判定していけばよいのではないでしょうか。

ここでは変数 i を用いて,while ループ内でこの操作を行っていきます。毎回の while ループで行う処理は次のものです。最初に i は0で初期化しておきます。

  1. X-i が p にあるか判定し,なければ ans にその値を格納して break
  2. X+i が p にあるか判定し,なければ ans にその値を格納して break
  3. i に1を足す

この while 内の処理で先ほど述べた順々の判定が行えます。それでは,解答例に移ります。

解答例

x,n = map(int, input().split())
p = list(map(int, input().split()))

ans = -1
i = 0

while True:
    temp = x -i
    if temp not in p:
        ans = temp
        break
    temp = x + i
    if temp not in p:
        ans = temp
        break
    i += 1

print(ans)

いかがだったでしょうか。
愚直な処理で解ける問題でしたね。
もし何かあれば twitter で気軽にご連絡ください。
それでは!

他の問題も解説しているので,ぜひ見ていってください!
ABC 170 A
ABC 170 B
ABC 170 C