AtCoder Beginer Contest 038 - D
解説
- AtCoder Beginner Contest 038 解説
- とりあえず、これはパラメータが２つある最長増加部分列問題であると見てよい
- 普通の最長増加部分列と比べて、配列は２つあり、それぞれw(=width), h(=height)のような形だ
まずは解説通りに動的計画法でのアルゴリズムを考え、その後フェニック木(Binary Indexed Tree)での満点回答を作成していく
途中式 - 動的計画法でのアルゴリズム
- サンプル1
- 入力値４つのデータについて、重複データがないので素直に解ける
4 2 5 3 3 4 5 6 6
- まず、w(=width), h(=height)をWを昇順、Hを降順で並べる
- Rubyのsort_byについては → 複数キーのソート Enumerable#sort （昇順・降順のみ、昇順・降順混在）
- なぜ昇順、降順を混ぜるのかというと、そうしないとうまく最長増加の記録が取れないからだ。解説にもそのような記述がある（そこで小一時間ハマった）。
lines = <<'EOS'
4
2 5
3 3
4 5
6 6
EOS
#lines = $stdin.read
array = lines.split("\n")
N = array[0].to_i
boxes = array[1..N].map do |str|
arr = str.split(" ").map(&:to_i)
Hash[*arr]
end.sort_by do |e|
key,val = e.first
[key,-val]
end
出力
[{2=>5}, {3=>3}, {4=>5}, {6=>6}]
ここからは動的計画法にて、一番左側に配置する箱を１～Nまで全て試す。もし「左側の箱＜右側の箱」ならば連続して置くことができるので、左の箱の最長増加＋１する。
- 行＝１番左側にある箱のインデックス
- 列＝最長増加の記録
の二次元のDPを定義する。ここは動的計画法がわかってないとキツいので、理解がなければ動的計画法 - コイン問題などを参照してください
dp = Array.new(N).map{Array.new(N, 0)}
# dp[i]:=max(dp[j])+1
# if boxes[i] > boxes[j]
for row in 0...dp.length
for col in row...dp.length
bef = boxes[col-1]
cur = boxes[col]
# puts "bef #{bef}"
# puts "cur #{cur}"
if bef.keys.first < cur.keys.first and bef.values.first < cur.values.first
dp[row][col] = [dp[row].max, dp[row].max + 1].max
end
end
end
for idx in 0...dp.length
puts "[#{idx}] #{dp[idx]}"
end
出力
[0] [0, 0, 1, 2]
[1] [0, 0, 1, 2]
[2] [0, 0, 1, 2]
[3] [0, 0, 0, 1]
3
ただし、問題の制約にもあるように1≦N≦10^5なので、これでは間に合わない。そこで、フェニック木の出番となる。
二分探索で解けてしまった。どうなってんだコラ。
二分探索でのアルゴリズム
- このコードを元に作成した -> 提出 #2739642 by fumiphys
やること
- dpをINFで埋めて番兵とする
- ソート済み配列を処理する（Wを昇順、Hを降順で並べる、逆でもよい）
- 箱を0~Nまで走査する際に
- 二分探索で現在の箱を超える大きさのものがあるかどうかチェック
- あればそれをdp[i]に設定
- 答えを出すとき
- 全部INFでないならば→全部入れ子にできる箱→答えはN
- 途中でINFが混じる→INFまでの個数が答え
dp = Array.new(N,INF)
#p boxes
boxes.each_with_index do |m,i|
k,v = m.first.to_a[0],m.first.to_a[1]
idx = dp.bsearch_index do |h|
v < h+1
end
if not idx.nil?
dp[idx] = v
end
end
#p dp
ans = dp.bsearch_index{|h| h == INF}
ans ||= N
puts ans
備考 - フェニック木でのアルゴリズム
以下は解説の通りに調査をしたが、結局二分探索で解けてしまったので無意味となった…悲しい
大部分が解説から引用。
BITは区間の和を持つ方法が最も基本的だが、列で 1番目からk番目の最小値を求める操作と列の値の 更新の操作も行うことができる
- ここ、たぶん資料のミス
- （誤）1番目からk番目の最小値を求める操作 → （正）1番目からk番目の最大値を求める操作
- そしてセグメント木の類題見つけちゃった → LIS using Segment Tree
BITで扱う列のi番目を最も外側の箱の横の長さがiとなる入れ子の数の最大値とする ・ query(i)で列のうちi番目まで最大値(を更新) ・ update(i,a)を列のi番目をaで更新 とすると 以下のような感じ
for i from 1 to N dp[i]:=bit.query(wi-1)+1 bit.update(wi, dp[i])
最終的に、dp[i]のうち最大値が答え
Ruby風に疑似コード書くと、こうでは？解答のコードはなにか省略しているのだろうか
a = []
dp[0]=1
fw = FenwickTree
fw.add(1, a[0])
for i in 1...N
if fw.max(i-1) <= a[i]
dp[i] += dp[i-1] + 1
else
dp[i] = dp[i-1]
end
fw.add(i+1, a[i])
end
頭が悪いので具体的な遷移がないとわからない…表を作成する。→やっとわかった
- 元データ
4 (=N) 2 5 (=w,h) 3 3 (=w,h) 4 5 (=w,h) 6 6 (=w,h)