paiza POH Vol.3 霧島京子攻略
解答
#!/usr/bin/env ruby file = $stdin lines = file.readlines file.close m = lines[0].to_i n = lines[1].to_i companies = lines[2, n].map{|x| x.split.map{|y| y.to_i}} companies.sort!{|a, b| b[0] <=> a[0]} map_q_to_r = {} map_q_to_r[0] = 0 left_q_sum = companies.inject(0){|sum, x| sum + x[0]} for q,r in companies new_map_q_to_r = {} for sq, sr in map_q_to_r next if sq + left_q_sum < m new_map_q_to_r[sq] = sr end for sq, sr in map_q_to_r if new_map_q_to_r.has_key?(sq + q) new_map_q_to_r[sq + q] = [map_q_to_r[sq + q], sr + r].min else new_map_q_to_r[sq + q] = sr + r end end map_q_to_r = new_map_q_to_r left_q_sum -= q end min_cost = -1 for sq, sr in map_q_to_r if sq >= m if min_cost < 0 min_cost = sr else min_cost = [min_cost, sr].min end end end puts min_cost
解説を読んでのメモ
- 霧島さんの水着壁紙が素晴らしい。
Bootstrap のメモ
テーブルを固定幅にする
- td に .span をつけることでグリッドシステムが使える。12 等分より細かい位置調整は div を併用してネストする。
- ただし、テキストが長い場合は word-break:break-all (あるいは word-wrap:break-word, overflow-wrap:break-word) を忘れずに。
Ajax とキャッシュについて
paiza POH Vol.2 木野さん攻略
解答
#!/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
コードの覚え書き
解説を読んでのメモ
- 定石を知らなかった。累積和を使って書き直す必要がある。
paiza POH Vol.1 野田さん攻略
解答
#!/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 + 事前ソート)
Google chrome で1年以内の検索をデフォルトにする
{google:baseURL}search?q=%s&tbs=qdr:y&{google:RLZ}{google:originalQueryForSuggestion}{google:assistedQueryStats}{google:searchFieldtrialParameter}{google:bookmarkBarPinned}{google:searchClient}{google:sourceId}{google:instantExtendedEnabledParameter}{google:omniboxStartMarginParameter}ie={inputEncoding}元のやつに tbs=qdr:y を追加する。
