https://codeiq.jp/ace/yuki_hiroshi/q432 に対する回答(今は問題が読めませんが)

answer2.txt

24689222839,0
ENV: Ruby

※締め切り後に調べた内容で解説を再編集しています。

Binary Indexed Treeとか知りませんでした(汗
インデックスの振り方が大変独特ですね。。。
https://twitter.com/debiru/status/374400678182928384
から
プログラミングコンテストでのデータ構造
(http://www.slideshare.net/iwiwi/ss-3578491)
あたりが専門用語の勉強になりました。多謝。

以下、
1. 単純消去(20min)
2. 単純消去の高速化(1.6sec)
3. セグメント木(1.6sec)
4. セグメント木を改良したもの(1.3sec)
の順に簡単な説明とコードを並べてます。
()内の時間はあるPC上での大体の値です。

セグメント木を改良したもので高速なPCでは1sec切る程度ですが、
他のコードについてはそちらで実行してないので、
比較のため、この値を使っています。
------------------------------------
1. 単純消去(20min)

無限に続く配列から、ファイルで順次示されて
いく番号が作っている光線を交点を考えながら
取り除いて行く方法を検討。
始点側はfind_indexで自分が左側から何番目かがわかりますが、
終点側は一番左に位置しているので、左側に始点があるはすべて
交差していると、考えられます。
この数を数えたら、光線の始点と終点を取り除きます。
そうすると、次の終点はやはり、一番左に位置しているので・・・
と続きます。

番号が何番まであるか、最初はわからなくて実行できるように
next_numというのを導入してますが、後に問題ファイルを最初に
全部読み切った方が(今回は)速いということが判明します。
残念。。。
巨大な配列に対して素のfind_indexとdelete_atを使っていて
ここが遅いです。その結果20分ほど。

def crossing(io)
  next_num=1
  buff=[]
  cross=0
  io.each{|line|
    num = line.to_i
    if next_num <= num
      buff.concat (next_num .. num).to_a
      next_num = num+1
    end
    idx = buff.find_index(num)
    buff.delete_at(idx)
    cross += idx
  }
  cross
end
puts crossing(ARGF)

------------------------------------
2. 単純消去の高速化(1.6sec)

配列に対するfind_indexとdelete_atが遅いので、
配列を分割していくつかの塊でリスト構造にする
いわゆるChunk構造にして高速化。(バケット法？)
リストでつないでしまっているのでこの時点では
細かく分割しすぎると、そちらの走査が重過ぎる
事になります。こっちの走査はメモ化で少しだけ
凌ぎました。

チャンクサイズについては今回問題にあわせて
適当にセットしてしまいました。
このあたりで、そろそろ真面目にアルゴリズムを
考えていきます。

追記：
このコードはRange#bsearchを使用しているため
Ruby2.0以降で実行する必要があります。

class NumChunk
  def initialize(chunk_size = 1000)
    @chunk_size = chunk_size
    @arys=[]
    @ary_base = (0...@chunk_size).to_a
    @sum_cache=[0]
  end
  def get_index_and_delete(num)
    index1,num = (num-1).divmod(@chunk_size)
    @arys << @ary_base.dup while index1 >= @arys.size
    ary = @arys[index1]
    #cnt1 = @arys[0,index1].inject(0){|r,i| r+i.size}
    until cnt1 = @sum_cache[index1]
      @sum_cache << @sum_cache[-1] + @arys[@sum_cache.size-1].size
    end
    cnt2 = (0...ary.size).bsearch {|i| ary[i] >=num }
    @arys[index1].delete_at(cnt2)
    @sum_cache[(index1+1)..-1]=[]
    cnt1+cnt2
  end
end
def crossing(io)
  buff=NumChunk.new(8000)
  cross=0
  io.each{|line|
    end_num = line.to_i
    idx = buff.get_index_and_delete(end_num)
    cross += idx
  }
  cross
end
puts crossing(ARGF)

------------------------------------
3. セグメント木(1.6sec)

数え上げなら木構造で出来るだろうということで
完全二分木の葉に番号を割り当てた木でマークと
マーク数の数え上げを行うようにしました。
セグメント木(と言うらしい)です。
k番目をマークした時に0からk-1番目の合計を計算するために、
右側の子供だった時に左側の子供の合計を加算していきます。

たとえば12番目だと 11番目+(9～10番目の合計)+(1～8番目の合計)
を計算することになります。

細かい点では、最内ループでの演算を少しでも減らすために、
配列の添え字を0スタートではなく1スタートで扱っています。
(0スタートだと親をたどるのがidx = (idx-1) / 2 になる)

class MarkTree
  def initialize(num)
    internal_nodes = 2 ** Math.log2(num).ceil - 1
    @tree = Array.new(internal_nodes + num+1){0}
    @offset = internal_nodes+1
  end
  def getsum_and_mark(num)
    idx = @offset + num
    sum = 0
    while idx > 1
      @tree[idx]+=1
      sum += @tree[idx-1] if  idx % 2 == 1
      idx /= 2
    end
    sum
  end
end
def crossing(io)
  lines = io.readlines
  nodes = lines.size
  mt = MarkTree.new(nodes)
  cross = 0
  lines.each{|i|
    num = i.to_i - 1
    cross += num - mt.getsum_and_mark(num)
  }
  cross
end
puts crossing(ARGF)


------------------------------------
4. セグメント木を改良したもの(1.3sec)

上のコードでは右の子のノードの内容が使われていなかったため、
そこを圧縮しました。左右の子供合わせて1つのノードみたいな
感じです。
Binary Indexed Tree と似てるっぽいですが、なんだろう・・・
メモリ使用量と最内ループでの合計の代入回数が大体半分に
なるため、3番目のコードより高速になってます。

class MarkTree
  def initialize(num)
    num=(num+1)/2
    internal_nodes = 2 ** Math.log2(num).ceil - 1
    @tree = Array.new(internal_nodes + num+1){0}
    @offset = internal_nodes+1
  end
  def get_and_mark(num)
    idx = @offset*2 + num
    sum = 0
    while idx > 1
      mod = idx % 2
      idx /= 2
      if mod == 1
        sum += @tree[idx]
      else
        @tree[idx]+=1
      end
    end
    sum
  end
end
def crossing(io)
  lines = io.readlines
  nodes = lines.size
  mt = MarkTree.new(nodes)
  cross = 0
  lines.each{|i|
    num = i.to_i - 1
    cross += num - mt.get_and_mark(num)
  }
  cross
end

puts crossing(ARGF)

--------------------------------------
以上