🐢

[ABC380 C] Move Segment

2024/11/20に公開

Ruby

0 と 1 の塊に分けて部分的に入れ替える問題。

例1で問題を理解する

K = 3
S = "010011100011001"

が、来るので、

["0", "1", "00", "111", "000", "11", "00", "1"]
#      1          2             3           4

のように分けて、1 のグループの 3 番目を、

["0", "1", "00", "111", "11", "000", "00", "1"]
#                        ^^    ^^^

その前の 0 のグループと入れ替える。

どうやって塊に分けるか？

s = "010011100011001"
s.chars.chunk(&:itself).collect { |_, a| a.join }  # => ["0", "1", "00", "111", "000", "11", "00", "1"]
s.split(/(?<=0)(?=1)|(?<=1)(?=0)/)                 # => ["0", "1", "00", "111", "000", "11", "00", "1"]
s.scan(/((.)\2*)/).collect(&:first)                # => ["0", "1", "00", "111", "000", "11", "00", "1"]
s.scan(/0+|1+/)                                    # => ["0", "1", "00", "111", "000", "11", "00", "1"]

もうちょっといい方法があってよさそうだが思いつかない。

自力解答

358 ms

N, K = gets.split.collect(&:to_i)  # => [15, 3]
S = gets.strip                     # => "010011100011001"
G = S.scan(/0+|1+/)                # => ["0", "1", "00", "111", "000", "11", "00", "1"]
indexes = G.each_with_object([]).with_index do |(e, m), i|
  if e[0] == "1"
    m << i
  end
end
i = indexes[K - 1]                 # => 5
j = i - 1                          # => 4
G[i], G[j] = G[j], G[i]
G                                  # => ["0", "1", "00", "111", "11", "000", "00", "1"]
puts G.join

配列 G は 0 と 1 のグループが混在しているので、1 のグループの K 番目と言われてもすぐに参照できない。そう考えて K 番目にアクセスするための indexes を準備している。

公式の模範解答を参考にした最適化

236 ms

N, K = gets.split.collect(&:to_i)  # => [15, 3]
S = gets.strip                     # => "010011100011001"
G = S.scan(/0+|1+/)                # => ["0", "1", "00", "111", "000", "11", "00", "1"]
i = 2 * K.pred + 1                 # => 5
if S.start_with?("1")
  i -= 1
end
i                                  # => 5
j = i - 1                          # => 4
G[i], G[j] = G[j], G[i]
G                                  # => ["0", "1", "00", "111", "11", "000", "00", "1"]
puts G.join

0 のグループと 1 のグループは交互に並んでいるのだから 1 のグループの K 番目は 2 * K で求まるのだった。もし 1 のグループから並んでいれば 1 つずれるので調整すればいい。これで G のループをまるごと省けた。indexes なんかいらなかった。

Ruby で提出した他の方のコード

137 ms

N, K = gets.split.map(&:to_i)  # => [15, 3]
S = gets.strip                 # => "010011100011001"
a = S.scan(/0*1*/)             # => ["01", "00111", "00011", "001", ""]
a[K - 1].reverse!              # => "11000"
a                              # => ["01", "00111", "11000", "001", ""]
puts a.join

単に K 番目の 00011 を反転するだけとかもう天才か。

S.scan(/0*1*/).tap { |e| e[K.pred].reverse! } * ""  # => "010011111000001"

実質一行だった。