20295


昨日質問した  
[同じ数同士線で結んだとき、交点ができるか否かの判定について](https://ja.stackoverflow.com/questions/20208/%E5%90%8C%E3%81%98%E6%95%B0%E5%90%8C%E5%A3%AB%E7%B7%9A%E3%81%A7%E7%B5%90%E3%82%93%E3%81%A0%E3%81%A8%E3%81%8D-%E4%BA%A4%E7%82%B9%E3%81%8C%E3%81%A7%E3%81%8D%E3%82%8B%E3%81%8B%E5%90%A6%E3%81%8B%E3%81%AE%E5%88%A4%E5%AE%9A%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6)  
の一般化を考えてみました。

ary1 = [1, 1, 2, 3, 3, 3, 2, 2, 1]  
を考えることにします。  
1と1を左から順番に飛ばさず上側で結びます。  
同様に2と2を、3と3を飛ばさず上側で結びます。  
（無理やり結んだ曲線を交差させないかぎり）  
交点は0個です。

一方  
ary2 = [1, 1, 3, 2, 3, 3, 2, 2, 1]  
を考えることにします。  
ary1 で行った操作を行うと  
交点ができます。

このように、  
ary の中に1～nまでの数字がk個ずつあり、  
同じ数字同士左から順番に飛ばさず上側で結んだとき、  
交点ができるか否かの判定をするには  
どうすればいいでしょうか？

とりあえず、  
[同じ数同士線で結んだとき、交点ができるか否かの判定について](https://ja.stackoverflow.com/questions/20208/%E5%90%8C%E3%81%98%E6%95%B0%E5%90%8C%E5%A3%AB%E7%B7%9A%E3%81%A7%E7%B5%90%E3%82%93%E3%81%A0%E3%81%A8%E3%81%8D-%E4%BA%A4%E7%82%B9%E3%81%8C%E3%81%A7%E3%81%8D%E3%82%8B%E3%81%8B%E5%90%A6%E3%81%8B%E3%81%AE%E5%88%A4%E5%AE%9A%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6)  
のunarist さんの回答を元に以下のようなコードを書いてみました。

[code]

    def test_intersect(ary, n, k)
      c_ary = Array.new(n, 0)
      stack = []
      ary.each{|i|
        if stack.last == i && c_ary[i - 1] == k - 1
          stack.pop
        else
          c_ary[i - 1] += 1
          stack << i if stack.last != i
        end
      }
      stack == []
    end
    
    p test_intersect([1, 3, 3, 2, 2, 1], 3, 2)
    p test_intersect([1, 3, 2, 3, 2, 1], 3, 2)
    p test_intersect([1, 1, 2, 3, 3, 3, 2, 2, 1], 3, 3)
    p test_intersect([1, 1, 3, 2, 3, 3, 2, 2, 1], 3, 3)
    p test_intersect([1, 1, 1, 2, 2, 3, 3, 3, 3, 2, 2, 1], 3, 4)
    p test_intersect([1, 1, 1, 2, 3, 2, 3, 3, 3, 2, 2, 1], 3, 4)
    
[/code]


CC BY-SA 3.0
2015-12-21T12:46:07.310
20262
2015-12-22T11:51:45.487
2017-04-13T12:52:39.113
-1
5363
question
ruby アルゴリズム
同じ数同士左から順に線で結んだとき、交点ができるか否かの判定について


残っている片割れの数だけ余分に積むようにすれば、`c_ary` でカウントする必要はなくなりますね。  
（そしてまたワンライナーに変形可能に）

[code]

    def test_intersect(ary, n, k)
      stack = []
      ary.each{|item|
        if stack.last == item
          stack.pop
        else
          stack.concat(Array.new(k - 1, item))
        end
      }
      stack == []
    end
    
[/code]


CC BY-SA 3.0
2015-12-22T11:51:45.487
20295
2015-12-22T11:51:45.487
8000
20262
answer