AtCoder Beginner Contest 170 - C問題 "Forbidden List" の解説

自分は参加していなかったのですが、先日開催されたAtCoder Beginner Contest 170のC問題"Forbidden List"の解説がなかなか不親切ということで、自分のTwitterのタイムラインでは少し話題になっていました(→PDF)。解説の内容は「ある1点だけ注意すれば、あとは問題文の通りに実装するだけ。詳しい内容は省略! 実質はB問題レベルだよ」というもので、とくに「B問題レベル」というのを煽りの一種にとらえた人もいるようでした。個人的にはそこまで攻撃的なニュアンスには思えなかったものの、Beginner向けを打ち出しているコンテストにしてはやや不親切かなと。そもそもC問題が解けないから、解説を読んで理解しようとしているわけです。にもかかわらず、そこで解説が省略されて困っちゃうという人はいると思います。

ちなみにYouTubeの解説動画ではC問題についてもわかりやすく説明されていたので、ちゃんと理解したい人はそちらを視聴しましょう(→動画)。ただ動画を再生できる環境がなかったり、聴覚障害などの影響で音声解説だと困ったりと、各々事情があると思うので、わたしなりに解説を書いてみたいと思います。自分自身も競技プログラミングで遊ぶなかで、さまざまな人が書いたBlog記事にずいぶんと助けられてきたので、その恩返しというか恩送りの気持ちもあります。

atcoder.jp

以下の順番に調べていって、初めて配列 $P$ に含まれていないものが答えになります。

$X$
$X-1$
$X+1$
$X-2$
$X+2$
$X-3$
$X+3$
$X-4$
$X+4$
(以下同じように続く)

たとえば入力例1の場合 ( $X=6, P=[4,7,10,6,5$ ])は以下のようになるはずです。

$X=6$ → $P$ に含まれる
$X-1=6-1=5$ → $P$ に含まれる
$X+1=6+1=7$ → $P$ に含まれる
$X-2=6-2=4$ → $P$ に含まれる
$X+2=6+2=8$ → $P$ に含まれないのでこれが答え

たとえば $X+100000000000000000$ とかが答えだった場合、 $X→X-1→X+1...$ とひとつづつチェックしていくと、さすがにTLEしてしまうのでは……と不安になるかもしれませんが、実はその心配はありません。問題の制約を見ると、 $X$ は $1$ 以上 $100$ 以下、 $P$ の長さは $1$ 以上 $100$ 以下で、その中身も $1$ 以上 $100$ 以下であることが保証されています。この制約下でやばそうなケースを考えてみると、以下のようなものが思いつきます。