Kattis電話リスト、時間制限は、問題の

Question

説明超え：私はfast-rubyを使用

# get phone list and return true if list consistent or false if not 
def consistent?(phone_list) 
    index = 0 
    last_phone = phone_list.last 
    phone_list.each do |phone| 
    index += 1 
    unless last_phone == phone 
     return true if phone.length == last_phone.length 
     return false if phone_list.drop(index).find { |ph| ph.start_with? phone } 
    end 
    end 
    true 
end 
# read file and parse settings 
input = File.open('phone.in', &:read).split("\n") 
# input = STDIN.read.split("\n") 
settings = input.slice!(0, 2).map(&:to_i) 

error_t = 'Testcase numbers need to be in range 1 to 40.' 
error_n = 'Phone numbers need to be in range 1 to 10000.' 
error_p = 'Phonenumber is longer than 10 digits or less then 1.' 
error_u = 'Phonenumbers set is not uniq' 

STDERR.puts(error_t) if settings[0] < 1 || settings[0] > 40 

# iterate throw input and agregate results to output 
settings[0].times do 
    STDERR.puts(error_n) if settings[1] < 1 || settings[1] > 10_000 
    phone_set = input.slice!(0, settings[1]) 
    STDERR.puts(error_u) unless phone_set.uniq.length == phone_set.length 
    result = consistent?(phone_set.sort_by do |phone| 
    STDERR.puts(error_p) if phone.length > 10 || phone.empty? 
    phone.length 
    end) 
    puts result ? 'YES' : 'NO' 
    settings[1] = input.slice!(0).to_i 
end 

：link

私のソリューションを。ハマった。あなたのアルゴリズムを改善する助けをするなら、私は非常に感謝します。

Answer 1

ボトルネックはRubyではなく、アルゴリズムです。 TLEの理由は次のコードのためです。

return false if phone_list.drop(index).find { |ph| ph.start_with? phone } 

電話番号の長さはO（L）であると想定し、電話番号がNであり、その後、前のコードの時間複雑度は、O（NL）は、アルゴリズムの全体的な複雑さはO（N^2L）でありますNが10000であるため、大きなテストに失敗します。

---

あなたはTrieは良いオプションです、この問題のために、いくつかの文字列データ構造を試してみてください。

最初の並べ替えの電話番号が数字の場合は1つずつ挿入します。ではなくという新しいツリーノードを作成すると、接頭辞を見つけて偽を返し、そうでない場合はtrueを返します。複雑さをO（NlogN + NL）に減らします。 Lが10以下の問題によれば、問題の時間制限に適合しなければならない。

Answer 2

到達不能番号は、次のように識別できます。

TO_DELETE = "()-" 

def unreachables(phone_list) 
    phone_list.permutation(2).each_with_object([]) do |(f,s),arr| 
    fd, sd = f.delete(TO_DELETE), s.delete(TO_DELETE) 
    arr << f if fd[0,sd.size] == sd 
    end 
end 

phone_list = ["213-749-6317", "(911) 749-6317", "12 37 63 21", "123", "911"] 
unreachables phone_list 
    #=> ["(911) 749-6317", "12 37 63 21"] 

手順は次のとおりです。

enum1 = phone_list.permutation(2) 
    #=> #<Enumerator: ["213-749-6317", "(911) 749-6317", "12 37 63 21", "123", "911"] 
    # :permutation(2)> 

我々は、配列に変換することにより、この列挙子によって生成される要素を見ることができます：

enum1.to_a 
    #=> [["213-749-6317", "(911) 749-6317"], ["213-749-6317", "12 37 63 21"], 
    # ["213-749-6317", "123"],   ["213-749-6317", "911"], 
    # ["(911) 749-6317", "213-749-6317"], ["(911) 749-6317", "12 37 63 21"], 
    # ["(911) 749-6317", "123"],   ["(911) 749-6317", "911"], 
    # ["12 37 63 21", "213-749-6317"], ["12 37 63 21", "(911) 749-6317"], 
    # ["12 37 63 21", "123"],    ["12 37 63 21", "911"], 
    # ["123", "213-749-6317"],   ["123", "(911) 749-6317"], 
    # ["123", "12 37 63 21"],    ["123", "911"], 
    # ["911", "213-749-6317"],   ["911", "(911) 749-6317"], 
    # ["911", "12 37 63 21"],    ["911", "123"]] 

継続、

enum2 = enum1.each_with_object([]) 
    #=> #<Enumerator: #<Enumerator: ["213-749-6317", "(911) 749-6317", "12 37 63 21", 
    # "123", "911"]:permutation(2)>:each_with_object([])> 

あなたは上記の戻り値からわかるようにenum2は、「化合物」列挙子と考えることができる。この最後のステップで

enum2.to_a 
    #=> [[["213-749-6317", "(911) 749-6317"], []], 
    # [["213-749-6317", "12 37 63 21"], []], 
    # [["213-749-6317", "123"], []], 
    # ... 
    # [["911", "123"], []]] 

enum2.each do |(f,s),arr| 
    fd, sd = f.delete(TO_DELETE), s.delete(TO_DELETE) 
    arr << f if fd[0,sd.size] == sd 
end 
    #=> ["(911) 749-6317", "12 37 63 21"]  

（平行又は複数割当によって）ブロックに渡され、ブロック変数に割り当てられるenum2の最初の要素は

(f,s),arr = enum2.next 
    #=> [["213-749-6317", "(911) 749-6317"], []] 
f 
    #=> "213-749-6317" 
s 
    #=> "(911) 749-6317" 
arr 
    #=> [] 

ブロック演算でありますしたがって、

fd = f.delete(TO_DELETE) 
    #=> "2137496317" 
sd = s.delete(TO_DELETE) 
    #=> "9117496317" 
arr << f if fd[0,sd.size] == sd 
    # arr << f if fd[0,10] == "9117496317" 
    # arr << f if "2137496317" == "9117496317" 
    # arr << f if false 
    #=> nil 
arr 
    #=> [] 

so "213-749-6317"はarrに追加されません。計算は、ブロックに渡されたenum2の他の要素についても同様です。