トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

AtCoder Beginner Contest 038

[競技プログラミング,競プロ解説]

AtCoder Beginer Contest 038 - D

  解説

まずは解説通りに動的計画法でのアルゴリズムを考え、その後フェニック木(Binary Indexed Tree)での満点回答を作成していく

途中式 - 動的計画法でのアルゴリズム

サンプル1
入力値4つのデータについて、重複データがないので素直に解ける
4
2 5
3 3
4 5
6 6
  • なぜ昇順、降順を混ぜるのかというと、そうしないとうまく最長増加の記録が取れないからだ。解説にもそのような記述がある(そこで小一時間ハマった)。
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なので、これでは間に合わない。そこで、フェニック木の出番となる。

二分探索で解けてしまった。どうなってんだコラ。

二分探索でのアルゴリズム

やること

  • 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)
お名前: コメント: