AtCoderのコンテストに遅刻してはいけない理由

AtCoderをやりはじめた当初、21時〜22時40分に開催される「ABC（AtCoder Beginner Contest）」に参加するにあたって、私は普通に遅刻して参加していました。

当時の参加スタイルはこんな感じです。 だいたい20分から40分くらい遅刻して参加。そこから1時間くらいかけてC問題まで解いて、D問題を見て「うーん、難しそうだからやめとこ」と諦めるパターン。

それで、ずっとパフォーマンス（※1）が低空飛行でした。

「ああ、茶色（※2）になるにはD問題も解けないといけないのかなぁ」と思っていました。

というか、パフォーマンス399とか、あと1ポイントで茶色！みたいなスコアを出しつつ停滞していたんです。

※1 パフォーマンス：そのコンテストで自分がどれだけの成績を出したかを示す数値。これがレーティング（強さの指標）に直結します。 

※2 茶色：レーティング400〜799の層。初心者を脱して、基本的な処理が書けるレベルの証ともいわれます。

二分探索（バイナリサーチ）は、あらかじめ昇順または降順にソート（整列）されたリストの中から、特定の値を高速に探し出すためのアルゴリズムである。

日常的な例でいうと、辞書で「こんぱす」という単語を調べるとき、最初のページから1ページずつめくる（線形探索）のではなく、まず真ん中あたりを開き、そこが「さ行」なら「もっと前だな」、「た行」なら「もっと後ろだな」と判断して探す範囲を狭めていく。この直感的な探し方こそが「二分探索」の正体である。

1. 二分探索の仕組み（例示）

例えば、次のように昇順にソートされた9個の要素を持つリストから、ターゲットとなる数値 23 を探すケースを考える。

リスト: [3, 8, 12, 17, 23, 29, 35, 42, 50] (要素数 $N = 9$)