PFIのサマーインターンの問題を考えてみた

Ruby

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

長さnの文字列中で出現回数が最大の文字をO(n)時間で答えるプログラムを書いてください。
但し、出現回数が最大の文字の出現回数はn/2より大きいとします。
条件として、文字列以外に利用できるバッファサイズはnに依存しない定数であり、文字種類数は可変（最大n)であるとします。

元のブログでも言われているように条件があるので

  • 単純に各文字毎に頻度を数えるのにはバッファサイズが定数ですので記録できません
  • 文字をソートするのもO(n log n)時間必要

ということになります。

私がこの問題で気にしたのはこれ。

  • 出現回数が最大の文字の出現回数はn/2より大きい

この条件から発展させてみる。

  1. 出現回数が最大の文字は少なくとも (n/2) + 1 回出現する
  2. (n/2) はInt型の割り算のように小数点以下は切り捨て
  3. n が偶数のとき、どこかに出現回数が最大の文字のペアが少なくとも1回現れる
  4. n が奇数のとき、出現回数が最大の文字のペアが現れる、現れなければ末尾の文字が出現回数が最大である。

3,4に関しては正直なところ経験的に考えたものです*1。
反例はないかなーと言われましたが、できても腑に落ちないところ*2。

実際にRubyで書いたコードが以下のものです。

# compare two char of input, 
# and keep the number of times when 2 char is equal
def compare2chars(str)
  eql_count = 0
  now_char = 0
  lambda do |n|
    if str[n] == str[n+1]
      if str[n] == now_char
        eql_count += 1
      else
        if eql_count == 1
          now_char = 0
          eql_count -= 1
        elsif eql_count == 0
          now_char = str[n]
          eql_count += 1
        else
          eql_count -= 1
        end
      end
    end
    return now_char, eql_count
  end
end

# search the char that appears most
def search_char(str)
  now_char = 0
  eql_count = 0
  compare_chars = compare2chars(str)
  str_size = str.size
  count = 0

  if (str_size == 2 && str[0] == str[1]) || str_size == 1
    return str[0].chr

  elsif str_size % 2 == 0
    0.step(str_size - 1, 2) do |n|
      now_char, eql_count = compare_chars.call(n)
    end

  elsif str_size % 2 == 1
    0.step(str_size - 2, 2) do |n|
      now_char, eql_count = compare_chars.call(n)
    end

    if eql_count == 0
      now_char = str[str_size-1]
    end

  else
    return nil
  end

  str.each_char do |ch|
    count += 1 if ch == now_char.chr
  end
  
  if count > str_size / 2
    return now_char.chr
  else
    return nil
  end
end

if ARGV[0]
  p search_char(ARGV[0])
else 
  p search_char(STDIN.gets.chomp)
end

変数

  • now_char: 仮の出現回数が最大の文字
  • eql_count: 仮の出現回数が最大の文字によるペアが等しい回数

動作

奇数、偶数の場合に分けて2文字ずつ判定(compare2chars)

  • 2文字が等しくeql_countが0のとき、その文字をnow_charとしeql_countをインクリメント
  • now_charと違うペアが来たら回数をデクリメント

偶数・奇数ともに返ってきたnow_charが出現回数が最大の文字

  • ただし奇数の場合で、eql_countが0のときは末尾文字が出現回数が最大の文字である

最後にnow_charが本当に (n/2) 回より多く出現しているかチェック

step文で O(n/2)、最後のチェックで O(n) なので O(n) の条件は満たしているはず。

最後に

色々書いたわけですが、選考は落ちました*3。
精進します。。

*1:面接で詰まったところ

*2:証明方法を知りたいです

*3:自分の技能や考えが曖昧だったのが大きそうです