Snippets

cia_rana オフラインリアルタイムどう書く E08 の問題 - 白黒陣取りゲーム

Updated by cia_rana
View revision

File benchmark.cia_rana.nochunk.txt Modified

  • Ignore whitespace
  • Hide word diff 
-11,7,0.000159637
-1,1,4.3265e-05
-4,4,5.8617e-05
-12,4,0.00010898
-12,1,0.000120518
-4,1,0.000167838
-4,4,5.9447e-05
-6,6,7.7128e-05
-8,8,9.1288e-05
-10,10,0.000115824
-12,12,0.000138163
-14,14,0.000167381
-17,17,0.000220088
-19,19,0.000524627
-22,22,0.000348413
-25,25,0.000405551
-28,28,0.000447799
-30,30,0.000506894
-33,33,0.000599457
-36,36,0.000680671
-39,39,0.000774482
-42,42,0.000876983
-45,45,0.000980206
-52,52,0.001324458
-55,55,0.001394893
-62,62,0.001755296
-65,65,0.002072566
-72,72,0.002648005
-76,76,0.002785717
-79,79,0.00305539
-83,83,0.003596223
-6,1,5.6712e-05
-1,6,7.192e-05
-360,1,0.017432863
-19,19,0.000259506
-38,38,0.00081821
-57,57,0.001550149
-76,76,0.002574366
-95,95,0.003866277
-114,114,0.005385396
-133,133,0.00711243
-152,152,0.009146312
-171,171,0.011545126
-180,181,0.052261002
-341,1,0.015121719
-24,1,0.000218398
-8,1,0.000106299
-12,1,0.000120091
+11,7,0.189656
+1,1,0.041712000000000006
+4,4,0.079292
+12,4,0.116462
+12,1,0.10450799999999999
+4,1,0.120716
+4,4,0.08022
+6,6,0.086673
+8,8,0.114474
+10,10,0.13575600000000002
+12,12,0.152947
+14,14,0.177476
+17,17,0.5033880000000001
+19,19,0.253688
+22,22,0.412523
+25,25,0.304814
+28,28,0.404913
+30,30,0.399841
+33,33,0.43719
+36,36,0.48485500000000004
+39,39,0.5115719999999999
+42,42,0.535525
+45,45,0.6034299999999999
+52,52,0.696812
+55,55,0.900013
+62,62,0.947094
+65,65,1.083618
+72,72,1.378324
+76,76,1.416036
+79,79,1.446415
+83,83,1.7318259999999999
+6,1,0.06839100000000001
+1,6,0.078642
+360,1,4.073995
+19,19,0.325011
+38,38,0.5848169999999999
+57,57,0.867746
+76,76,1.252337
+95,95,1.539331
+114,114,1.878531
+133,133,2.376281
+152,152,2.758667
+171,171,3.072449
+180,181,17.201593000000003
+341,1,2.893757
+24,1,0.18324
+8,1,0.081898
+12,1,0.100533
Updated by cia_rana
View revision

File e08.rb Modified

  • Ignore whitespace
  • Hide word diff 
 
 def calc_area friends_xc, friends_yc, enemies_xc, enemies_yc
   area_unit = Set.new
-  time = 0
   friends_yc.each{|self_y, self_xs|
     self_xs.each.with_index(1){|self_x, i|
       flg = false
Updated by cia_rana
View revision

File e08.rb Modified

  • Ignore whitespace
  • Hide word diff 
 AREA_SIZE = 18
 AREA_DIGIT_SIZE = 10 ** Math.log(AREA_SIZE).to_i # 10^(エリア１辺の長さの桁数)
 
-def calc_area friends, friends_xc, friends_yc, enemies, enemies_xc, enemies_yc
+def calc_area friends_xc, friends_yc, enemies_xc, enemies_yc
   area_unit = Set.new
-  
-  # →
+  time = 0
   friends_yc.each{|self_y, self_xs|
     self_xs.each.with_index(1){|self_x, i|
       flg = false
       self_xs[i..-1].each{|opp_x|
         next unless opp_ys = friends_xc[opp_x]
         next unless opp_ys = opp_ys[opp_ys.index(self_y)+1..-1]
-        #p [self_y, self_x, opp_ys, opp_x]
         opp_ys.each{|opp_y|
           next unless friends_xc[self_x].include?(opp_y)
-          next if enemies.find{|u, f| self_y <= u && u <= opp_y && self_x <= f && f <= opp_x }
+          next if enemies_yc.find{|enemies_y, enemies_xs|
+            self_y <= enemies_y && enemies_y <= opp_y && enemies_xs.find{|enemies_x| self_x <= enemies_x && enemies_x <= opp_x}
+          }
           
           # エリアの面積を計算
           # self_y: top-y, self_x: top-x, opp_point[0]: bottom-y, opp_point[1]: bottom-x
 end
 
 def solve input
-  w, w_xc, w_yc, b, b_xc, b_yc = input.split(?,).map{|e|
+  w_xc, w_yc, b_xc, b_yc = input.split(?,).map{|e|
     sorted_input = e.scan(/\d+/).map(&:to_i).zip(e.scan(/[a-z]/).map(&:ord))
       .sort_by{|r,_|r}
       .sort_by.with_index{|(_,c),i|[c,i]}
     [
-     sorted_input,
      sorted_input.chunk{|_,x|x}.map{|k,v|[k,v.map(&:first)]}.to_h,
      sorted_input.sort_by.with_index{|(r,_),i|[r,i]}.chunk{|y,_|y}.map{|k,v|[k,v.map(&:last)]}.to_h
     ]
   }.flatten(1)
-  [calc_area(w, w_xc, w_yc, b, b_xc, b_yc), calc_area(b, b_xc, b_yc, w, w_xc, w_yc)] * ?,
+  [calc_area(w_xc, w_yc, b_xc, b_yc), calc_area(b_xc, b_yc, w_xc, w_yc)] * ?,
 end
 
 class TestCaces < Test::Unit::TestCase
   def test_run data
     expected, input = data
     assert_equal expected, solve(input)
-    #puts solve(input)
   end
 end
Updated by cia_rana
View revision

File e08.rb Modified

  • Ignore whitespace
  • Hide word diff 
 AREA_SIZE = 18
 AREA_DIGIT_SIZE = 10 ** Math.log(AREA_SIZE).to_i # 10^(エリア１辺の長さの桁数)
 
-def get_opposite_angle friends, enemies, i, y, x
-  r, c = friends[i-1]
-  friends[i..-1].each{|s, d| 
-    y.each{|t|
-      # y座標が一致しなければスキップ
-      next unless t == s
-      x.each{|e|
-        # x座標が一致しなければスキップ
-        # x, y座標が一致しても自分の駒とエリアを構成する対角の駒との間に敵の駒があってもスキップ
-        if e == d && !enemies.index{|u, f| r <= u && u <= t && c <= f && f <= e }
-          return [t, e]
-        end
+def calc_area friends, friends_xc, friends_yc, enemies, enemies_xc, enemies_yc
+  area_unit = Set.new
+  
+  # →
+  friends_yc.each{|self_y, self_xs|
+    self_xs.each.with_index(1){|self_x, i|
+      flg = false
+      self_xs[i..-1].each{|opp_x|
+        next unless opp_ys = friends_xc[opp_x]
+        next unless opp_ys = opp_ys[opp_ys.index(self_y)+1..-1]
+        #p [self_y, self_x, opp_ys, opp_x]
+        opp_ys.each{|opp_y|
+          next unless friends_xc[self_x].include?(opp_y)
+          next if enemies.find{|u, f| self_y <= u && u <= opp_y && self_x <= f && f <= opp_x }
+          
+          # エリアの面積を計算
+          # self_y: top-y, self_x: top-x, opp_point[0]: bottom-y, opp_point[1]: bottom-x
+          (AREA_DIGIT_SIZE*self_y).step(AREA_DIGIT_SIZE*(opp_y-1), AREA_DIGIT_SIZE) {|i|
+            (self_x...opp_x).each {|j|
+              area_unit << i + j
+            }
+          }
+          
+          flg = true
+          break
+        }
+        break if flg
       }
     }
   }
-  return []
-end
-
-def calc_area_c friends, friends_xc, friends_yc, enemies, enemies_xc, enemies_yc
-  friends.each_with_object(Set.new).with_index(1){|((row, column), area_unit), index|
-    next unless y = friends_xc[column]
-    y = y[y.bsearch_index{|e|row<=>e}+1..-1]
-    next if y.empty?
-    next unless x = friends_yc[row]
-    x = x[x.bsearch_index{|e|column<=>e}+1..-1]
-    next if x.empty?
-    
-    # 自陣営の中から上で集めたx,y座標と一致する駒を抜き出す
-    z = get_opposite_angle friends, enemies, index, y, x
-    next if z.empty?
-    
-    # エリアの面積を計算
-    # row: top-left, column: top-right, z[0]: bottom-left, z[1]: bottom-right
-    (AREA_DIGIT_SIZE*row).step(AREA_DIGIT_SIZE*(z[0]-1), AREA_DIGIT_SIZE) {|i|
-      (column...z[1]).each {|j|
-        area_unit << i + j
-      }
-    }
-  }.size
-end
-
-def calc_area friends, enemies
-  friends.each_with_object(Set.new).with_index(1){|((row, column), area_unit), index|
-    # 自陣営の全ての駒の対角となりうる駒を集める
-    # 自分のy座標より大きいy座標の値を持ち、かつ同じx座標を持つ自陣営の駒を集める
-    next unless y = friends[index..-1].select{|_,d|d == column}.map{|s,_|s}
-    # 自分のx座標より大きいx座標の値を持ち、かつ同じy座標を持つ自陣営の駒を集める
-    next unless x = friends[index..-1].select{|s,_|s == row}.map{|_,d|d}
-    
-    # 自陣営の中から上で集めたx,y座標と一致する駒を抜き出す
-    z = get_opposite_angle friends, enemies, index, y, x
-    next if z.empty?
-    
-    # エリアの面積を計算
-    # row: top-left, column: top-right, z[0]: bottom-left, z[1]: bottom-right
-    (AREA_DIGIT_SIZE*row).step(AREA_DIGIT_SIZE*(z[0]-1), AREA_DIGIT_SIZE) {|i|
-      (column...z[1]).each {|j|
-        area_unit << i + j
-      }
-    }
-  }.size
+  area_unit.size
 end
 
 def solve input
-  sorted_input = input.split(?,).map{|e|
-    e.scan(/\d+/).map(&:to_i).zip(e.scan(/[a-z]/).map(&:ord))
+  w, w_xc, w_yc, b, b_xc, b_yc = input.split(?,).map{|e|
+    sorted_input = e.scan(/\d+/).map(&:to_i).zip(e.scan(/[a-z]/).map(&:ord))
       .sort_by{|r,_|r}
       .sort_by.with_index{|(_,c),i|[c,i]}
-  }
-  
-  if sorted_input.map(&:size).inject(:+) > 40
-    w, w_xc, w_yx, b, b_xc, b_yc = sorted_input.map{|e|
-      [e, e.chunk{|_,x|x}.map{|k,v|[k,v.map(&:first)]}.to_h, e.sort_by.with_index{|(r,_),i|[r,i]}.chunk{|y,_|y}.map{|k,v|[k,v.map(&:last)]}.to_h]
-    }.flatten(1)
-    [calc_area_c(w, w_xc, w_yx, b, b_xc, b_yc), calc_area_c(b, b_xc, b_yc, w, w_xc, w_yx)] * ?,
-  else
-    w, b = sorted_input
-    [calc_area(w, b), calc_area(b, w)] * ?,
-  end
+    [
+     sorted_input,
+     sorted_input.chunk{|_,x|x}.map{|k,v|[k,v.map(&:first)]}.to_h,
+     sorted_input.sort_by.with_index{|(r,_),i|[r,i]}.chunk{|y,_|y}.map{|k,v|[k,v.map(&:last)]}.to_h
+    ]
+  }.flatten(1)
+  [calc_area(w, w_xc, w_yc, b, b_xc, b_yc), calc_area(b, b_xc, b_yc, w, w_xc, w_yc)] * ?,
 end
 
-class TestSaces < Test::Unit::TestCase
+class TestCaces < Test::Unit::TestCase
   data(
     "1" => ["5,3", "d3d4e3e4d9h7h9j3j4j7j9,f4f6g4g5g6h5h6"],
     "2" => ["0,0", "a1,s19"],
     "47" => ["25,0", "a1a6b3b4c2c5d2d5e3e4f1f6,l9"],
   )
   def test_run data
-    expected, actual = data
-    assert_equal expected, solve(actual)
+    expected, input = data
+    assert_equal expected, solve(input)
+    #puts solve(input)
   end
 end
Updated by cia_rana
View revision

File e08.rb Modified

  • Ignore whitespace
  • Hide word diff 
   return []
 end
 
-def calc_area friends, friends_xc, friends_yc, enemies, enemies_xc, enemies_yc
+def calc_area_c friends, friends_xc, friends_yc, enemies, enemies_xc, enemies_yc
   friends.each_with_object(Set.new).with_index(1){|((row, column), area_unit), index|
     next unless y = friends_xc[column]
     y = y[y.bsearch_index{|e|row<=>e}+1..-1]
   }.size
 end
 
+def calc_area friends, enemies
+  friends.each_with_object(Set.new).with_index(1){|((row, column), area_unit), index|
+    # 自陣営の全ての駒の対角となりうる駒を集める
+    # 自分のy座標より大きいy座標の値を持ち、かつ同じx座標を持つ自陣営の駒を集める
+    next unless y = friends[index..-1].select{|_,d|d == column}.map{|s,_|s}
+    # 自分のx座標より大きいx座標の値を持ち、かつ同じy座標を持つ自陣営の駒を集める
+    next unless x = friends[index..-1].select{|s,_|s == row}.map{|_,d|d}
+    
+    # 自陣営の中から上で集めたx,y座標と一致する駒を抜き出す
+    z = get_opposite_angle friends, enemies, index, y, x
+    next if z.empty?
+    
+    # エリアの面積を計算
+    # row: top-left, column: top-right, z[0]: bottom-left, z[1]: bottom-right
+    (AREA_DIGIT_SIZE*row).step(AREA_DIGIT_SIZE*(z[0]-1), AREA_DIGIT_SIZE) {|i|
+      (column...z[1]).each {|j|
+        area_unit << i + j
+      }
+    }
+  }.size
+end
+
 def solve input
-  w, w_xc, w_yx, b, b_xc, b_yc = input.split(?,).map{|e|
-    sorted = e.scan(/\d+/).map(&:to_i).zip(e.scan(/[a-z]/).map(&:ord))
-    .sort_by{|r,_|r}
-    .sort_by.with_index{|(_,c),i|[c,i]}
-    [sorted, sorted.chunk{|_,x|x}.map{|k,v|[k,v.map(&:first)]}.to_h, sorted.sort_by.with_index{|(r,_),i|[r,i]}.chunk{|y,_|y}.map{|k,v|[k,v.map(&:last)]}.to_h]
-  }.flatten(1)
-  [calc_area(w, w_xc, w_yx, b, b_xc, b_yc), calc_area(b, b_xc, b_yc, w, w_xc, w_yx)] * ?,
+  sorted_input = input.split(?,).map{|e|
+    e.scan(/\d+/).map(&:to_i).zip(e.scan(/[a-z]/).map(&:ord))
+      .sort_by{|r,_|r}
+      .sort_by.with_index{|(_,c),i|[c,i]}
+  }
+  
+  if sorted_input.map(&:size).inject(:+) > 40
+    w, w_xc, w_yx, b, b_xc, b_yc = sorted_input.map{|e|
+      [e, e.chunk{|_,x|x}.map{|k,v|[k,v.map(&:first)]}.to_h, e.sort_by.with_index{|(r,_),i|[r,i]}.chunk{|y,_|y}.map{|k,v|[k,v.map(&:last)]}.to_h]
+    }.flatten(1)
+    [calc_area_c(w, w_xc, w_yx, b, b_xc, b_yc), calc_area_c(b, b_xc, b_yc, w, w_xc, w_yx)] * ?,
+  else
+    w, b = sorted_input
+    [calc_area(w, b), calc_area(b, w)] * ?,
+  end
 end
 
 class TestSaces < Test::Unit::TestCase
  2. 1
  3. 2
  4. 3
  5. 4
  6. 5
  7. 6
  8. 7
  9. 8
HTTPS SSH

You can clone a snippet to your computer for local editing. Learn more.