AtCoder のコンテストには制限時間がある。その場でゼロから解き方を考えて、コードに反映させていたら間に合わない。だから、高得点を出すには予め糸口を知っておく必要がある。それは、二分探索であったり、動的計画法であったりする。知っている道具の数が多いほど、道具に習熟しているほど、問題に立ち向かう時間は節約できる。

道具を正確に使うのは難しい。たとえば、配列インデックスが間違っている。再帰計算の終了条件が間違っている。再利用すべきでないオブジェクトを再利用している。…このような色々なミスが起きる。事前にプログラムを書き、参考にできるコードを手元に持っておくのが良い。

道具を学ぶにあたって AtCoder の模範解答が役立つ。ただし、そこから知らないことを全部吸収するのはとても難しい。背景にある数学やコンピュータサイエンスを知るのに、時間がかかりすぎる。だからまずは問題を解くのに必要な知識だけ抑えていくのがいいだろう。 Qiita で NTT データの人が書いた記事で学んでいくのが良さそうだ。

Exhaustive Search 全探索

すべての可能性を検討して要求された解を求めることを全探索という。データサイズが十分小さい場合はシンプルなループで実現できる。組み合わせを問う問題は each で計算できるが permutation, combination を利用すればより簡単。 C - One-stroke Path はグラフの経路探索だがノード数が少ないので permutation で検査できる。 D - カード並べは combination が役に立つ問題。

bit 全探索

C - たくさんの数式 / Many Formulas は全探索を要求する問題。長さ最大 10 の文字列に対して、隙間に + を詰める or 詰めないのパターンをすべて網羅する必要がある。全探索を素朴なループで表現することが難しい。このような場合には bit 全探索が役に立つ。 bit 全探索では、整数 B をカウントアップしていき、B をバイナリでみたときの桁をフラグとみなす。たとえば 4 つのフラグを全部試したいなら 0000, 0001, 0010, 0011, ... 1111 を試す。

Ruby で n 桁目の bit を参照するには [] メソッドを利用すればいい。これを踏まえたプログラムの例は下記の通り。

FLAG_SIZE = 4
(2**FLAG_SIZE).times do |flags|
  FLAG_SIZE.times do |i|
    if flags[i] == 1
      # フラグが立っているときの処理
    else
      # フラグが落ちているときの処理
    end
  end
end

repeated_parmutation を使う方法もある。

[true, false].repeated_permutation(FLAG_SIZE).each do |flags|
  flags.each do |flag|
    if flag
      # フラグが立っているときの処理
    else
      # フラグが落ちているときの処理
    end
  end
end

こちらは bit を意識させないので書き味が良い。ただし、性能を求められる場面では配列を介さない bit 全探索のほうが優秀である。 C - All Green はアレンジが必要でかなり難しい。 Matrix Reducing にも bit 全探索を使う解法がある。

グラフの探索

問題がグラフ構造を持っているとき、ほとんどの場合は単純なループ文で探索を実現できない。下記の探索アルゴリズムを手に馴染ませておかないと太刀打ちできない。

DFS(depth-first search) 深さ優先探索

グラフの探索は配列の探索と違って、単純なループ文で書くことができない。 DFS はグラフのすべてのノードを効率よく訪問するためのアルゴリズム。このアルゴリズムは大まかな方針しか示していないので具体的な実装はデータ構造によって変わる。

def search(node, visited = {})
  visited[node] = true

  node.children.each do |child|
    unless visited[child]
      search(child, visited)
    end
  end
end

深さ優先探索は、ノードの子要素を優先的に探索することに由来する。木構造ではないグラフ（ループを持つグラフ）でも正常に機能する。実際の課題では node.children のような構造的なメソッドは定義されてない事が多い。たとえば AtCoder の典型的例題では、グリッド迷路を表現する 2 次元配列データ構造が与えられる。

s####
....#
##.##
#...g

1 つのマスが 1 つのノードであり、隣接するマス同士が接続されたエッジだと考えれば DFS が利用できる。

ROWS = H.times.map { gets.chomp.chars }
VISITED = H.times.map { Array.new(W) }

def search(i, j)
  return if i.negative? || i >= H ||
            j.negative? || j >= W ||
            ROWS[i][j] == '#' ||
            VISITED[i][j]

  VISITED[i][j] = true

  ROWS[i][j] == 'g' ||
    search(i + 1, j) ||
    search(i - 1, j) ||
    search(i, j + 1) ||
    search(i, j - 1)
end

Do use hexagon grid は、グリッドの色を塗られた連結を観察する問題。これはグリッドの 1 つのマスをノードとするグラフとして考えるとうまくいく。

BFS(breadth-first search) 幅優先探索

これも全探索手法の 1 つ。 BFS は DFS と違って、解の空間から最小値を探すことができる。そのため最小値を求めるような問題を効率よく実行できる。先入れ先出し FIFO(First-In-First-Out) のキューを使って実現できる。代表的な問題として C - 幅優先探索のように、迷路の最短経路を求めるときに役立つ。キューを実現するには Array の shift, pop を使うと良い。 Ruby の shift は高速に動くので linked list を実装する必要はない。実装例は下の通り。

def bf_search(map, start_i, start_j, goal_i, goal_j)
  queue = [[start_i, start_j]]
  steps = H.times.map { Array.new(W, -1) }
  diffs = [[0, 1], [0, -1],[1, 0], [-1, 0]]

  until queue.empty?
    i, j, step = queue.shift

    return step if (i == goal_i) && (j == goal_j)

    diffs.each do |k, l|
      i2 = i + k
      j2 = j + l

      next if i2 < 0 || i2 >= H ||
              j2 < 0 || j2 >= W ||
              steps[i2][j2] > -1 ||
              map[i2][j2] == '#'

      steps[i2][j2] = step[i][j] + 1
      queue << [i2, j2]
    end
  end

  false
end

上のコードでは探索キューに入れる前に探索すべきかどうかの条件判定をしている。これをやめ、キューから取り出したときに条件判定すると、計算コストが増加する。これは避けたほうがよい。なぜなら、概算でセル数が4倍になったのと同程度の計算が必要になるため。たとえばセル数 500x500 の迷路が課題として与えられたとする。これを上記の非効率な探索をすると 500x500x4 の探索になり AtCoder では時間切れになる。

Greedy algorithm 貪欲法

問題領域が広く、全探索で解決できない場合は問題領域を狭めて探索する必要がある。最小値や最大値の求める問題では、貪欲法が最適解を求めるのに役立つことがある。貪欲法はまず、問題を分解して、小さな問題に対して部分解を求める。そして、評価値の高い順に部分解を結合したものを、解とする。

A - おつりは貪欲法が最適解となる問題。この問題ではお釣りを作ることができる硬貨の組み合わせは有限なので、全探索して、枚数が最小となるものを選択してもいい。貪欲法を知らずとも、問題に合わせて素直に解を求めるアルゴリズムを作ると貪欲法になっている事が多い。

Interval Scheduling Problem 区間スケジューリング問題

B - Robot Arms が代表的な問題。おそらく、解放を知っていないと解けない。区間の終端でソートし順次採用判定をする貪欲法を利用する。

2 点間の距離・チェビシェフ距離（チェス盤距離）

2点間距離の最大値 (The longest distance) は 2 点間の距離を求める問題。 $\sqrt{(x_2 - x_1)^2 +(y_2 - y_1)^2}$ の計算は、Ruby では Math.hypot を使うとよい。

p1 = { x: 1, y: 1 }
p2 = { x: 2, y: 2 }
Math.hypot(p2[x] - p1[x], p2[y] - p1[y]) #=> 1.4142135623730951
Math.hypot(p1[x] - p2[x], p1[y] - p2[y]) #=> 1.4142135623730951 逆でも同じになる

直角三角形の斜辺（hypotenuse）の長さに由来するとのこと。

Nice Grid の問題では 2 点間の距離は使えない。代わりに、下記の式で定義されるチェビシェフ距離 $L$ を使う。

$L = max(|x2 - x1|, |y2 - y1|)$

Binary Search 二分探索

ダーツや Iroha and Haiku (New ABC Edition) は二分探索を使う問題。二分探索はソートされた配列に対して条件を満たす値を $O(log n)$ で検索するアルゴリズム。 Ruby ではビルトインメソッド bsearch 及び bsearch_index により実装されている。

bsearch は２つのモードが有る。find-minimum は下記のブロックを引数に取る。

探す値 x がブロックパラメータと一致するか、それより大きい値のとき true
そうでないとき false

例は下記の通り。

[1,3,5,7,9].bsearch {|x| x >= 7 } #=> 7
[1,3,5,8,9].bsearch {|x| x >= 7 } #=> 7以上の領域での最小値 = 8 が答えとなる

添字が知りたいときは bsearch の代わりに bsearch_index を使えば良い。 find-any モードについては省略。

幾何学

あとで内積・外積を勉強する。

http://www.deqnotes.net/acmicpc/2d_geometry/products

数列の部分和

Index × A(Continuous ver.) は数列の和を使う問題。数列 $A = A_0, A_1, ... A_{n-1}$ が与えられたとき、補助的な数列 $S$ を下記のように構成する。

\begin{aligned} S_0 &= 0 \\ S_1 &= A_0 \\ S_2 &= A_0 + A_1 \\ S_3 &= A_0 + A_1 + A_2 \\ &\vdots \\ S_n &= A_0 + A_1 + A_2 + \cdots + A_{n-1} \\ \end{aligned}

この数列の生成は $O(n)$ の計算で実行可能である。すると、任意の部分和は $O(1)$ で計算できる。なぜならば下記が成り立つからである。

\begin{aligned} S &= S_{y+1} - S_{x} \\ &= (A_0 + \cdots + A_{y}) - (A_0 + \cdots + A_{x-1}) \\ &= A_x + \cdots + A_{y} \end{aligned}

Ruby の実装例は下記の通り。

class PartialSum
  def initialize(array)
    @array = array
    @memo = [0]

    @array.each_with_index do |value, i|
      @memo[i + 1] = @memo[i] + value
    end
  end

  def get(start_index, end_index)
    @memo[end_index + 1] - @memo[start_index]
  end
end

ps = PartialSum.new([1,2,3,4,5,6])
ps.get(0, 0) #=> 1
ps.get(1, 3) #=> 2 + 3 + 4 = 9

get(x, y) は array[x..y].sum よりも高速に動作する。ただし PartialSum は初期化コストが $O(n)$ かかるのに対してビルトインメソッド sum は初期化不要であることに注意。