paiza POH Vol.2 木野さん攻略

procon paiza ruby

解答

#!/usr/bin/env ruby

file = $stdin
lines = file.readlines
file.close

H, W = lines[0].split.map{|x| x.to_i}
screen = lines[1, H].map{|x| x.strip}.join
N = lines[H + 1].to_i
widgets = lines[H + 2, N].each_with_index.map{|x, i| x.split.map{|y| y.to_i} + [i]}

sorted_widgets = {}
for widget_h, widget_w, index in widgets
  if not sorted_widgets.has_key?(widget_h)
    sorted_widgets[widget_h] = []
  end
  sorted_widgets[widget_h] += [[widget_h, widget_w, index]]
end

count_map = Array.new(W * H, 0)
results = Array.new(N, 0)

(0..H - 1).reverse_each do |y|
  (0..W - 1).reverse_each do |x|
    pos = y * W + x
    sign = count_map[pos] = screen[pos] == "0" ? +1 : -1
    if x < W - 1 and count_map[pos + 1] * sign > 0
      count_map[pos] += count_map[pos + 1]
    end
  end
end

def get_left_most(x, y, n, count_map)
  while x < W
    left_min = (0..n - 1).map{|i| count_map[(y + i) * W + x]}.min
    if left_min > 0
      return x, left_min
    end
    x += -left_min
  end
  return x, 0
end

sorted_widgets.each{|widget_h, values|
  for y in 0..H - widget_h
    x = 0
    while x < W
      new_x, width = get_left_most(x, y, widget_h, count_map)
      if new_x == W
        break
      end
      for widget_h, widget_w, i in values
        if width >= widget_w
          results[i] += width - widget_w + 1
        end
      end
        x = new_x + width
    end
  end
}

puts results

結果

コードの覚え書き

  • 横方向に何個空白が続くか、あるいは壁が続くかを事前に計算してマップ化
  • 縦幅でウィジェットを事前にグループ化
  • 画面の縦幅 y でループ
    • ウィジェットの縦幅 h でループ
      • マップを用いることで、座標 y での縦幅 h の長方形の空白が左から順番に求まる。
      • 各空白にグループ内の横幅 w の各ウィジェットが何個入るかも計算で求まる。

解説を読んでのメモ

  • 定石を知らなかった。累積和を使って書き直す必要がある。

paiza POH Vol.1 野田さん攻略

procon paiza ruby

解答

#!/usr/bin/env ruby

file = $stdin
lines = file.readlines
file.close

N, D = lines[0].split.map{|x| x.to_i}
p = lines[1, N].map{|x| x.to_i}
m = lines[N + 1, D].map{|x| x.to_i}

p.sort!

def calc(th, p)
  i = 0
  j = p.length - 1
  max_total = 0
  while i < j
    total = p[i] + p[j]
    if total == th
      return total
    elsif total < th
      max_total = [max_total, total].max
      i += 1
    elsif total > th
      j -= 1
    end
  end
  return max_total
end

results = []

for th in m
  p_selected = p.select {|x| x <= th - p.first}
  results += [calc(th, p_selected)]
end

puts results

結果

コードの覚え書き

  • 必ず 2 つの商品を購入してその合計金額ということだったので、商品をソートして並べて、2 つのマーカーを移動させて探索する。
  • キャンペーン数でループ
    • マーカーを移動させて探索
      • 最高額(最右) p[j] と最低額(最左) p[i] の組み合わせで、すでにキャンペーン金額 (th) を越えているのなら、高額商品 p[j] を下げるしかない。
      • キャンペーン金額内の最高額の商品 p[j] が確定したら、低額商品 p[i] の方を目一杯高額なものを選択する。
    • もしかしたら高額商品を別のを選択することで、合計金額はより高いものがあるかもしれない。
    • しかし、その場合は低額商品 p[j] はより高いものになる。
      • なぜならば過去に p[i] + p[j] <= th が成立しているならば、単に高額側の商品を下げた p[i] + p[j - 1] は (ソートしてあるため) p[i] + p[j - 1] < p[i] + p[j] <= th が成立して最大候補ではない。
  • 計算量
    • キャンペーン日数 D のループ * 商品点数 N の移動量 = O(DN + 事前ソート)

解説を読んでのメモ

  • 当初、入出力周りがボトルネックになっていることに気づかなかった。
  • 解説の O(NlogN + DN) で紹介されているアルゴリズムの説明おかしくないか? p[i] を安い商品にして、p[k] を降順にするならば、p[k] は下端ではなく上端では。
  • 結果発表で紹介されているコードは、コメントを読むと集計用のテストケース以外では正しくないことがあるらしい。ただこれはバグではなく、実は商品数が膨大なテストケースではキャンペーン設定値を決め打ちで返しているため。確率的に考えると多くのテストケースでそうなるらしい。

Hackintosh で輝度コントロール

osx

configuration が不十分で、起動の度に輝度が MAX にリセットされてしまい、またキーによる制御もできないため、Apple script を書いた。

tell application "System Events" to repeat 5 times
     key code 107
     delay 0.1
end repeat

これで 5 段下がるので、Automator でアプリ化して、Login items に加えれば起動時に実行される。

tar で tar: Error exit delayed from previous errors

ubuntu 
$ tar ... &> log.txt

などとして、"tar:" で検索すれば分かるが、大概はパーミッションの問題でアクセスできないファイルやフォルダが含まれている。ファイルならば r、フォルダならば x もついているかも確認する。

$ sudo chown -R user:group *
$ chmod -R oug+r *
$ find . -type d -print0 | xargs -0 chmod +x