リアル女子大生とペアプロできないのはどう考えても俺が悪い 第二話

12056 ワード
paiza paiza テキストリンク

この画面に対して

1000
1101
1001
1111
1111
1111
1111

下記のように変換することで比較回数は（理論上）√(H * W)になるなーというやつでテスト4は通ったけどあとは全然ダメだった。

0321
0010
0210
0000
0000
0000
0000

あと動的計画法でどうにかなるらしいと聞いたけどやる時間がなかった。

テストパターンを思いついてテストファイルを作れるかどうかがとりあえず問題だなーという感想。

とりあえず最後のコードはこれ。メモ化しようとしてた途中なので、答えが合うかどうか怪しい。

require 'pp'
FIELD="0"
BLOCK="1"


module Kernel
  extend self
  def scani(re)
    gets.scan(re).map(&:to_i)
  end
end

class Cell
  attr_accessor :width, :height
  def initialize(width,height)
    @width = width
    @height = height
  end
end

def walk_width(s)
  i = 0
  a = s.inject([]) do |r,x|
    case x
    when FIELD
      r.unshift Cell.new(i += 1,1)
    when BLOCK
      r.unshift Cell.new(i = 0,0)
    end
  end
  a
end

def walk_vert(cur,pre)
  pre.each_with_index do |x,i|
    if cur[i].width > 0
      cur[i].height = x.height + 1
    end
  end
end

($mx,$my) = scani(/\d+/)

$memoize = []
$mem = []
pre = nil
$mx.times do
  line = walk_width(gets.scan(/./))
  $mem.unshift line
  if pre
    walk_vert(line, pre)
  end
  pre = line
end

#pp $mem

def find_memoize(v,h) 
  pat = 4 
  $memoize[v] ||= []
  pat.times do |i|
    i=(i+1)*v
    if $memoize[i]
      pat.times do |j|
        j=(j+1)*v
        if $memoize[i][j]
          return $memoize[i][j]
        end
      end
    end
  end
  nil
end

def count(vert,horz)
  count = 0
  $mx.times do |x|
    $my.times do |y|

      m = find_memoize(vert, horz)
      return m if m

      if vert > horz
        next unless $mem[x][y].width >= horz
        cells = $mem[x][y,horz]
        allowed = cells.all?{|c| c.height >= vert}
      else
        next unless $mem[x][y].height >= vert
        cells = $mem[x,vert].map{|z|z[y]}
        allowed = cells.all?{|c| c.width >= horz}
      end 
      if allowed
        count += 1
      end
    end
  end
  $memoize[vert][horz] = count
  p count
end

widgets = gets.to_i

widgets.times do
  count(*(scani(/\d+/)))
end
Python二級等試験知識点整理——高教版Python言語プログラム設計スパート試験用紙(二)
c++におけるデータ型変換