Preferred Infractractureサマーインターン2011問題

• サマーインターン2011問題 | Preferred Research

↑が面白そうだったので考える．
O(n)の計算量で配列中に最も多い要素(ただしn/2回以上出現)を見つける．
記憶に使っていい容量はc log n bits．

1つ目

• 参考:API Only - Stack Exchange

1. 現在の文字と同じ文字ならカウントを1足す
2. 違う文字なら
   1. カウントが1以上なら1減らす
   2. カウントが0なら現在の文字を入れ替えて1足す

given = "abcadbeca"

count = 0
cur = given[0]
for c in given:
	if cur == c:
		count += 1
	else:
		if count == 0:
			cur = c
			count += 1
		else:
			count -= 1

print cur

2つ目

乱択アルゴリズムかなあ？と思うけど微妙．

3つ目

思いつかない．動的計画法とか分割統治法とか使いたくなるけど……．

文字列の中央値を求めればいいようです．
クイックソートライクのアルゴリズムで最悪でも線形時間で求められるとのこと．

• 参考:PFIサマーインターン2011問題 - pepshisoの日記
• 参考:選択アルゴリズム - Wikipedia

その他の方の解答

はてなブックマーク - サマーインターン2011問題 : Preferred Researchの「このエントリーを含む日記」にすごい人の解答があるはず