Preferred Research サマーインターン2011問題を解いてみた

http://research.preferred.jp/2011/07/intern2011_problem/

基本方針: 異なる種類の文字同士を見つけて消去して、最後に残った文字の種類を出力する。

出現回数が最大の文字をaと呼ぶことにする. aの出現回数はn/2より大きい、別の言い方をすれば、a以外の文字の出現回数の合計はaの出現回数よりも小さい。そのため、異なる種類の文字同士を見つけて消去していくと、仮に消去の組み合わせの一方が全てaだったとしても、文字種が1種類になるときには必ずaが残る。

文字列をstrとすると、回答は以下:

i = 0
j = 1
while j != n
  if str[i] == str[j]
     j += 1
  else
     str[i] = ILLEGAL_VALUE
     str[j] = ILLEGAL_VALUE 
     while str[i] == ILLEGAL_VALUE 
    //while str[i] != ILLEGAL_VALUE 6/29 10:08追記 逆でした
       i += 1
     end
     j = MAX(i +1, j+1)
  end
end
return str[i]

使用しているバッファ量: 2 * log_2(n)
計算量 O(n) (iもjも手戻りが無いため)