Codeforces Round #799 (Div. 4) in Ruby

概要

ロシアの競技プログラミングサイト Codeforces のコンテスト「Codeforces Round #799 (Div. 4)」を Ruby で解いたので解説します。

A - Marathon

問題文（意訳）

ティムールと他 $3$ 人がマラソンのコースを走っています。ティムールのスタート地点からの距離は $a$ で、他の $3$ 人のスタート地点からの距離は $b, c, d$ です。ティムールよりも先を走っている人の数を答えてください。
ただし、 $a, b, c, d$ は互いに異なります。

解説

$b, c, d$ のうち、 $a$ よりも大きいものが何個あるか数えます。

コード

t = gets.to_i
t.times do
  # b, c, d をまとめて xs とした
  a, *xs = gets.split.map(&:to_i)
  puts xs.count { _1 > a }
end

B - All Distinct

問題文（意訳）

ショウは $n$ 個の整数からなる配列 $a$ を持っています。ショウは、この配列から $2$ つの異なる位置にある要素を選び、削除する、という操作ができます。この操作を何度か行って、配列に同じ要素が複数ないようにしたときの、配列の長さの最大値を答えてください。

ヒント

$2$ 種類の要素がそれぞれ $x, y$ 個あるときの答えがどうなるかを考えてみると良いです。

解説

まず、それぞれの値について、要素がいくつあるか集計します。このとき、値 $x$ の要素が $c_x$ 個あるとすると、少なくとも $\sum_x (c_x - 1)$ 個を削除する必要があります。
削除するべき要素が偶数個なら、削除するべき要素同士でペアにできるので、 $n$ からこれを引いたものが答えになります。
しかし、削除するべき要素が奇数個のときは、ペアを作るために、消すべき要素以外から一つ追加で消す必要があるため、ここに注意が必要です。

コード

t = gets.to_i
t.times do
  n = gets.to_i
  a = gets.split.map(&:to_i)
  # 削除するべき要素の個数
  double = a.tally.each_value.sum { |count| count - 1 }
  puts n - (double + 1) / 2 * 2
end

C - Where's the Bishop?

問題文（意訳）

$8 \times 8$ のチェス盤の端でない位置にビショップが置かれています。ビショップが $0$ 手または $1$ 手でたどり着ける位置が模様として与えられるので、ビショップがどこにいるか答えてください。

ヒント

ビショップが端に置かれることがない場合、あなたにとってどういう良いことがあるでしょうか？

解説

端に置かれないことから、必ず以下の模様が含まれることがわかります。この模様が含まれる位置を探すと良いです。

#.#
.#.
#.#

さらに言うと、この模様が含まれるときのみ、 $3 \times 3$ マスの中の # が $5$ 個になります。

コード

t = gets.to_i
t.times do
  gets
  grid = Array.new(8) { gets.chomp }
  (1 .. 6).any? do |i|
    (1 .. 6).any? do |j|
      # (i, j) が中心にくる 3x3 の正方形の中に、「#」がいくつあるか数える（ 5 個ならそこが答え）
      if (i - 1 .. i + 1).sum { |i2| (j - 1 .. j + 1).count { |j2| grid[i2][j2] == ?# } } == 5
        puts "#{i + 1} #{j + 1}"
	true
      else
        false
      end
    end
  end
end

D - The Clock

問題文（意訳）

$24$ 時間形式の時刻（ $H_1 H_2 : M_1 M_2$ ）のうち、 $H_1 = M_2$ かつ $H_2 = M_1$ であるようなものを、「回文である」と呼ぶことにします。
ある時刻 $h_1 h_2 : m_1 m_2$ と正整数 $x$ が与えられます。ヴィクターは、最初にこの時刻に時計を見、それから $x$ 分おきに時計を見る、ということを無限に繰り返します。ヴィクターが見る時刻のうち、異なる回文であるものがいくつあるか答えてください。

解説

愚直にシミュレーションをし、同じ時刻が $2$ 回目に出現したら終了すればよいです。鳩ノ巣定理より、シミュレーションの回数は $1440$ 回以下であることが言えます。

コード

require "set"
t = gets.to_i
t.times do
  time, _x = gets.split
  h = time[0, 2].to_i
  m = time[3, 2].to_i
  x = _x.to_i
  i = h * 60 + m
  visited = [false] * (24 * 60)
  ans = 0
  until visited[i]
    visited[i] = true
    h, m = i.divmod(60)
    h1, h2 = h.divmod(10)
    m1, m2 = m.divmod(10)
    ans += 1 if h1 == m2 and h2 == m1
    i = (i + x) % (24 * 60)
  end
  puts ans
end

E - Binary Deque

問題文（意訳）

スラヴィックは $0, 1$ からなる長さ $n$ の配列を持っています。スラヴィックはこの配列に対して、先頭の要素または末尾の要素のどちらかを $1$ つ削除する、という操作ができます。配列の要素の総和を $s$ にするために必要な操作の最小回数を求めてください。

解説

配列の累積和をとっておくことで、先頭からいくつ消し、末尾からいくつ消すかを決めたときの総和を $O(1)$ で求められるようになります。
先頭からいくつ消すかを決め打ちし、末尾からいくつ消すかを二分探索すると解けます。

コード

t = gets.to_i
t.times do
  n, s = gets.split.map(&:to_i)
  a = gets.split.map(&:to_i)
  
  if a.sum < s
    puts -1
    next
  end
  
  prefix_sum = [0]
  a.each do |x|
    prefix_sum << prefix_sum[-1] + x
  end
  
  ans = n
  (0 .. n).each do |head|
    tail = (0 .. n).bsearch { |tail| n - (prefix_sum[head] + prefix_sum[n] - prefix_sum[N - tail]) <= s }
    ans = head + tail if ans > head + tail
  end
  puts ans
end

F - 3SUM

問題文（意訳）

正の整数からなる長さ $n$ の配列が与えられます。この配列から $3$ つの異なる位置にある要素を選んだとき、和の下 $1$ 桁が $3$ になることはあるか答えてください。

ヒント

$10$ で割ったあまりが $3$ になるかどうかです。

解説

まず、 $x + y + z \equiv 3 \pmod 10$ となる $0 \le x \le y \le z \le 9$ の組み合わせを列挙し、その組み合わせを作るのに必要な数の個数を覚えておきます。
これらの組み合わせのうち、入力から作れるものがあるかどうか判定することで、答えることが可能です。

コード

# 和が 3 になる 0 <= x <= y <= z <= 9 の組み合わせを列挙
combinations = []
[* 0 .. 9].repeated_combination(3) do |a|
  if a.sum % 10 == 3
    counts = [0] * 10
    a.each do |x|
      counts[x] += 1
    end
    combinations << counts
  end
end

t = gets.to_i
t.times do
    n = gets.to_i
    a = gets.split.map(&:to_i)
    
    counts = [0] * 10
    a.each do |x|
        counts[x % 10] += 1
    end
    
    # 3 になる組み合わせのうち、入力から作れるものがあるか
    ans = combinations.any? { |counts2| (0 .. 9).all? { |x| counts[x] >= counts2[x] } }
    puts ans ? "YES" : "NO"
end

G - 2^Sort

問題文（意訳）

$n$ 個の正整数からなる配列が与えられます。長さ $k + 1$ の連続部分列であって、最初から順に $2^0, 2^1, 2^2, \ldots$ を掛けていったら単調増加になるようなものがいくつあるか求めてください。

ヒント

条件は、隣り合う要素に関する条件に言い換えることができます。

解説

どの隣り合う要素についても、前の要素が次の要素の $2$ 倍よりも小さいならその部分列は条件を満たします。
ここで、隣り合う要素のペアそれぞれについて、条件を満たすなら $1$ 、満たさないなら $0$ とします。この値で累積和を取ることで、ある部分列について $O(1)$ で判定できます。
長さ $k + 1$ の部分列は $O(N)$ 個なので、この問題を解くことができました。

コード

t = gets.to_i
t.times do
  n, k = gets.split.map(&:to_i)
  a = gets.split.map(&:to_i)
  b = a.each_cons.map { |x, y| (x < y * 2) ? 1 : 0 }
  prefix_sum = [0]
  b.each do |x|
    prefix_sum << prefix_sum[-1] + x
  end
  puts (0 ... n - k).count { |i| prefix_sum[i + k] - prefix_sum[i] == k }
end

H - Gambling

問題文（意訳）

マリアンはカジノにいます。このカジノでできるゲームはいくつかの次のような形式です。

• 毎ラウンド、プレイヤーは数を言う。次に、 $1$ から $10^9$ までの目があるサイコロが振られる。出た目と言った数が一致していれば掛け金が倍になるが、外れれば、掛け金は半分になる。（小数点以下は丸められない。例えば、 $1$ を半分にすると $\frac{1}{2}$ になる。）
  マリアンは予知能力者なので、カジノで出る目が完全にわかっています。
  ここで、マリアンは言う数 $a$ をひとつに固定し、 $l$ ラウンド目から $r$ ラウンド目までに出ることで、掛け金を最大化しようと考えました。掛け金が最大になるときの $a, l, r$ の組をひとつ答えてください。

解説

まず、それぞれの出目について、それが出るラウンドを記録します。
出目 $a$ がラウンド $t_1, t_2, \ldots, t_K$ に出るとします。このとき、 $(1, t_1 - t_2 + 1, 1, t_2 - t_3 + 1, \ldots, t_{K - 1} - t_{K}, 1)$ という数列を考えると、答えはこの数列上での区間和の最大値と言えます。例えば、 $x = (1, 2, 1, 1, 2)$ のとき、 $a = 1$ に対しては $t = (1, -1, 1, 0, 1)$ となり、 $a = 2$ に対しては $t = (1, -2, 1)$ となります。
これは Kadane's Algorithm を使うと、 $O(N)$ で（場所も含めて）求めることができます。

Kadane's Algorithm は、配列から和が最大になる区間を求めるアルゴリズムです。
コードで表すと、以下のようになります。

# [和の最大値, そのときの左端, そのときの右端] を返す（閉区間）
def kadane(array)
  left = 0
  sum = 0
  ans = [array[0], 0, 0]
  
  array.each_with_index do |x, right|
    if sum < 0
      left = right
      sum = x
    else
      sum += x
    end
    
    if ans[0] < sum
      ans = [sum, left, right]
    end
  end
  
  ans
end

コード

t = gets.to_i
t.times do
  n = gets.to_i
  x = gets.split.map(&:to_i)
  indices = {}
  x.each_with_index do |a, i|
    (indices[a] ||= []) << i
  end
  
  ans = 1
  ans_value = [x[0], 1, 1]
  indices.each do |a, row|
    b = [1]
    row.each_cons(2) do |i, j|
      b << (i - j + 1) << 1
    end
    
    l = 0
    sum = 0
    b.each_with_index do |x, r|
      if sum < 0
        l = r
        sum = x
      else
        sum += x
      end
      if sum > ans
        ans = sum
        ans_value = [a, row[l / 2] + 1, row[r / 2] + 1]
      end
    end
  end
  
  puts ans_value.join(" ")
end