🌳

[ABC189 C] Mandarin Orange

2024/02/05に公開

Ruby

大きい順に木を作る問題。

問題を理解する

みかんをたくさん食べたいなら全部の皿をさらって食べたらよさそうだが、

食べていい個数は手をつけた皿に乗っているみかんの数以下

のルールが急激に話をややこしくする。

たとえば 9 1 を全部食べようとすると 1 1 の2個しか食べちゃいけないってことなので 9 で我慢した方が賢い選択になる。また、9 5 の場合は 9 で我慢するより 5 5 とした方が 10 個食べることができて得になる。

考察

まず、たくさんみかんが乗った皿から手をつけた方がいいのはわかる。だから、2 9 5 だったら 9 から手をつけた方がいい。次に領土を広げていけばいいように思える。

その領土はどういう基準で横に広げればよいか。2 9 5 の真ん中の 9 は、左の 2 よりも右の 5 に広げた方がよさそうな気はする。2 9 2 なら、広げない方がいい。

このように、どちらの方向に広げた方が得なのか、もくしくは、広げない方が得なのかの判断が難しいのだけど、そこはとりあえず、広げられるなら広げて個数を求め、そのいちばん良かった個数、すなわち最大値だけを見るようにする。

また「領土を広げる」については個数が多い順に見ていけば自然と広がっていくので、どこかを中心にして再帰的に広げていくようなイメージは捨てる。

具体的な流れ

個数に位置を添えた配列を用意し、個数の大きい順に並び換える
「位置」と「その位置の左右」で素集合森を作る
個数×「位置が属する木の大きさ」を計算する

左右の要素は「開いているものだけを対象」として連結する
2〜3を配列要素分繰り返す
繰り返し処理の中でその位置に「開いた」フラグをつける
(3) の最大値が答え

シミュレーション

個数に位置を添えた配列を用意する。

個数	位置
2	0
4	1
4	2
9	3
4	4
9	5

個数の大きい順に並び換える。

個数	位置
9	3
9	5
4	1
4	2
4	4
2	0

「位置」と「その位置の左右」で素集合森を作り、個数×「位置が属する木の大きさ」を出す。

個数	位置	0 1 2 3 4 5	位置が属する木	木の大きさ	個数×木の大きさ	最大
9	3	2 4 4 9 4 9	3	1	9	9
9	5	2 4 4 9 4 9	5	1	9	↓
4	1	2 4 4 9 4 9	1	1	4	↓
4	2	2 4 4 9 4 9	1-2-3	3	12	12
4	4	2 4 4 9 4 9	1-2-3-4-5	5	20	20
2	0	2 4 4 9 4 9	0-1-2-3-4-5	6	12	↓

太字は「開いた」を意味する。

こうして 4 4 9 4 9 をさらった場合にもっとも多く 20 個食べることができる。

コード (AC)

N = gets.to_i                               # => 6
A = gets.split.collect(&:to_i)              # => [2, 4, 4, 9, 4, 9]
a = A.collect.with_index { |c, i| [c, i] }  # => [[2, 0], [4, 1], [4, 2], [9, 3], [4, 4], [9, 5]]
a = a.sort_by { |c, _| -c }                 # => [[9, 3], [9, 5], [4, 1], [4, 2], [4, 4], [2, 0]]
opened = {}
max = 0
ds = DisjointSet.new(0...N)
a.each do |c, i|
  [-1, 1].each do |sign|
    if opened[i + sign]
      ds.unite(i, i + sign)
    end
  end
  if $0 == "-"
    ds.groups[ds.root(i)]                   # => [3], [5], [1], [1, 2, 3], [1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5]
    ds.size(i)                              # => 1, 1, 1, 3, 5, 6
  end
  v = c * ds.size(i)                        # => 9, 9, 4, 12, 20, 12
  max = [max, v].max                        # => 9, 9, 9, 12, 20, 20
  opened[i] = true
end
p max                                       # => 20

参考

https://atcoder.jp/contests/abc189/submissions/19919111