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も手戻りが無いため)