Skip to content

Instantly share code, notes, and snippets.

@dekosuke
Created July 29, 2011 13:38
Show Gist options
  • Save dekosuke/1113812 to your computer and use it in GitHub Desktop.
Save dekosuke/1113812 to your computer and use it in GitHub Desktop.
PFIの問題の解答(でこすけ)
#/usr/bin/python
# coding:utf-8
"""
PFIブログの問題
http://research.preferred.jp/2011/07/intern2011_problem/
の解答。アイディアとしては
・最大になる文字の候補を2つに絞る
・それぞれの候補に対して、候補が実際に文字列の半分以上あるか調べる
の2ステップで行う。
最初のステップは、ハッシュ「data」に
data[文字種] = その文字の今までの出現数
になるようにハッシュを作っていくことで行う。
ただし、ハッシュのキー数が2つを超えないように以下の工夫をしている。
文字を挿入した後に、キー数が3つ以上なら
data[ 1番出現数の少ない文字 ] を削除
data[ 2番目に文字出現数の少ない文字] から、先ほど削除したデータと同数だけ減らす
(つまり、2種類の文字の出現数をペアで同数だけ減らす)
問題の条件より、最大になる文字は全体の半分を超えている。
この作業で最大になる文字文字が候補から消えてしまったとすると、
少なくても同数のそのほかの文字が消えていることになるが、これは矛盾する。
よって背理法より一番出現数の多い文字は最後に必ず残る。
計算量などの評価:
計算量O(N)
外部メモリ量O(1)
"""
strings = ["sasasas","sasbscs","aaabbbsssssss", "sasbsbsbsbsbsbs", "sbbbssass","ssssabc","sasbsscsd"]
data = {}
def push(achar):
global data
if data.has_key(achar):
data[achar]+=1
else:
data[achar]=1
if len(data.keys())>=3: #3要素以上になったらかならず1要素以上消すルーチン
data_sorted = sorted(data.items(), key=lambda x:x[1]) #(key,valu)の組リストを値の降順で作る
minval = data_sorted[0][1]
del(data[data_sorted[0][0]]) #1番valueの小さい要素を削除
if data_sorted[1][1]==minval:
del(data[data_sorted[1][0]]) #2番目と1番目のvalueが同じなら両方削除
else:
data[data_sorted[1][0]]-=minval #2番目に小さい要素から1番目と同じ分だけ削る
def find_max(astr):
global data
data = {}
for achar in astr:
push(achar) #メインルーチン。候補を最大2つに絞る
#print achar,data
for elem in data.keys(): #最大2つの候補から順番に、半分以上あるか調べる
count = 0
for achar in astr:
if achar==elem:
count+=1
if count>len(astr)/2:
print 'maximum char of "'+astr+'" is "'+elem+'"'
return
for string in strings: #実行例
find_max(string)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment