POH! Vol.2 Ruby模範解答

こちらではpaiza事務局側で作成したコードを随時掲載していきます。
更新日:2014年4月30日(水)

Ruby: paiza事務局作成コード Vol.3 動的計画法

得点:100点
通過テストケース数:7/7

h = 0
w = 0
line = gets.chomp
h, w = line.split.map(&:to_i)
display = Array.new(h).map{Array.new(w)}
h.times { |i|
  display[i] = gets.chomp
}
table = Array.new(310).map{Array.new(310, 0)}
dp =  Array.new(310).map{Array.new(310)}
310.times { |i|
  310.times { |j|
    dp[i][j] = 100100100
  }
}
h.times { |k|
  (h-k).times { |i|
    dp[i][0] = display[i+k][0] == '0' ? [dp[i][0], 1].min : 0
    1.upto(w-1) { |j|
      dp[i][j] = display[i+k][j] == '0' ? [dp[i][j], dp[i][j-1]+1].min : 0
    }
  }
  hist = Array.new(310, 0)
  (h-k).times { |i|
    (w-1).times { |j|
      if dp[i][j+1] == 0 && dp[i][j] >= 1
        hist[dp[i][j]] += 1
      end
    }
    if dp[i][w-1] > 0
      hist[dp[i][w-1]] += 1
    end
  }
  sum = 0
  w.times { |i|
    sum += hist[i+1]
  }
  w.times { |i|
    table[k+1][1] += (i+1)*hist[i+1]
  }
  2.upto(w) { |i|
    table[k+1][i] = table[k+1][i-1] - sum
    sum -= hist[i-1]
  }
}

n = gets.chomp.to_i
n.times { |i|
  line = gets
  s, t= line.split.map(&:to_i)
  puts table[s][t]
}

Ruby: paiza事務局作成コード Vol.2 O(H^2W^2)

得点:71点
通過テストケース数:5/7

h1 = 0
w1 = 0
line = gets
h1,w1 = line.split.map(&:to_i)
#puts h1, w1
display = Array.new(2500).map{String.new}
h1.times { |i|
  display[i] = gets.chomp
}
ss = Array.new(2500).map{Array.new(2500,0)}
h1.times { |i|
  w1.times { |j|
    ss[i+1][j+1] = ( (display[i][j] == '1') ? 1 : 0 )
  }
}
h1.times { |i|
  w1.times { |j|
    ss[i+1][j+1] += ss[i+1][j]
  }
}
h1.times { |i|
  w1.times { |j|
    ss[i+1][j+1] += ss[i][j+1]
  }
}
n = gets.chomp.to_i
#puts n
n.times {
  line = gets
  h2,w2 = line.split.map(&:to_i)
  #puts h2, w2
  cnt = 0
  ii = h1 - h2 + 1
  jj = w1 - w2 + 1
  ii.times { |i|
      jj.times { |j|
      dd = ss[i+h2][j+w2] - ss[i+h2][j] - ss[i][j+w2] + ss[i][j]
      if dd == 0
        cnt = cnt + 1
      end
    }
  }
  puts cnt
}

Ruby: paiza事務局作成コード Vol.1 O(H^3W^3)

得点:42点
通過テストケース数:3/7

# coding: utf-8
line = gets
h, w = line.split.map(&:to_i)
display = Array.new(2001).map{String.new}
h.times { |i|
  display[i] = gets.chomp
}
n = gets.chomp.to_i
n.times {
  line = gets
  s, t = line.split.map(&:to_i)
  a = h - s + 1
  b = w - t + 1
  cnt = 0
  a.times { |i|
    b.times { |j|
      if display[i][j] == '1'
        next
      end
      flag = true
      s.times { |ii|
        t.times { |jj|
          if display[i+ii][j+jj] == '1'
            flag = false
            break
          end
        }
        if !flag
          break
        end
      }
      if flag
        cnt = cnt + 1
      end
    }
  }
  puts cnt
}
ページの先頭へ戻る