AtCoder Beginer Contest 038 - D
解説
まずは解説通りに動的計画法でのアルゴリズムを考え、その後フェニック木(Binary Indexed Tree)での満点回答を作成していく
途中式 - 動的計画法でのアルゴリズム
- サンプル1
- 入力値4つのデータについて、重複データがないので素直に解ける
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}]
ここからは動的計画法にて、一番左側に配置する箱を1~Nまで全て試す。もし「左側の箱<右側の箱」ならば連続して置くことができるので、左の箱の最長増加+1する。
- 行=1番左側にある箱のインデックス
- 列=最長増加の記録
の二次元の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)